码云:
6.1 数据结构
1. 数据结构定义:
数据结构是指逻辑意义上的数据组织方式及其相应的处理方式;
1.1. 数据组织方式:
- 树: 二叉树, 三叉树, B+ 树等;
- 图: 有向图, 无向图;
- 队列: 先进先出的线性结构;
- 哈希: 根据某种算法直接定位的数据组织方式;
1.2. 数据处理方式:
在既定的数据组织方式上, 以某种特定的算法实现数据的增删改查和遍历. 不同数据处理方式存在巨大的性能差异;2. 数据结构分类
线性结构: 0至1个直接前继和直接后继;
包括顺序表、链表、栈、队列等,栈和队列是访问受限的结构;
栈是 LIFO (Last-In, First-Out), 队列是FIFO (First-In, First-Out);树结构: 0至1个直接前继和 0至n个直接后继(n大于或等于2);
结构稳定均衡;
图结构: 0 至n 个直接前继和直接后继（ n大于或等于2 ）;
哈希结构: 没有直接前继和直接后继;
通过某种特定的哈希行数将索引与存储的值关联起来; 查找效率非常高;
数据结构复杂度: 空间复杂度, 时间复杂度; 算法时间复杂度是衡量计算性能的指标
6.2 集合框架
6.2.1 List集合
- 线性数据结构; ArrayList和LinkedList;
- ArrayList 容量可变, 非线程安全集合;扩容问题(内部使用数组进行存储, 集合扩容时会创建更大的数组空间, 把原有的数据复制到新数组中); 插入删除数据慢(因为过程中可能需要移动其他元素), 但是索引数据快;
- LinkedList 是双向列表;相比ArrayList, 插入删除速度快, 随机访问速度慢;
6.2.2 Queue集合
队列是以中先进先出的数据结构; FIFO , 一端获取一端插入数据, 特殊线性表;
BlockingQueue (阻塞队列)
6.2.3 Map 集合
K-V键值对为存储元素实现的哈希结构; K 唯一,V 可重复;
keySet() 查看所有K, values() 查看所有V, entrySet() 查看所有K-V;
最早的Hashtable已经被淘汰(因性能瓶颈);
HashMap 线程不安全;
ConcurrentMap 线程安全(并发包);
TreeMap 是Key有序的Map集合
6.2.4 Set 集合
Set 不允许出现重复元素;
HashSet 从源码分析是使用HashMap事项, Value 固定为一个静态对象, Key 保证元素唯一, 不保证顺序;
TreeSet 由TreeMap实现; 树结构, 保证集合顺序;
LinkedHashSet 继承 HashSet; 内部使用链表维护元素插入顺序;
6.3 集合初始化
CollectionInitialization.Java
初始化通常进行内存分配、设置特定参数等工作;
ArrayList 默认为10个容量; 每次扩容调用Array.copyOf(), 创建新数组再复制;
创建对象就直接分配大小避免额外开销;/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;
HashMap 的 Capacity 决定了存储容量大小, 默认16; Load Factor 决定填充比例, 默认0.75;
基于这两个的乘积, HashMap 内部用threshold存储/* ---------------- Public operations -------------- */ /** * Constructs an empty HashMap with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } /** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
HashMap 容量不会在new的时候分配, 而是在第一次map后创建;
HashMap 容量大于2的幂;
6.4 数组与集合
数组是一种顺序表. 在Java体系中数组用于存储同一类型的对象; 一旦分配内存不可扩容;
NegativeArraySizeException;
对于动态大小的数组, 集合提供了 Vector (线程安全, 但性能较差, 已启用) 和 ArrayList (线程不安全);
数组遍历推荐jdk1.5引进的foreach方式; 也可使用jdk8 的lambda遍历;
针对数组对象操作的工具类: Arrays;
- 数组转集合:
Arrays.asList(); 适配器模式; 返回的是Arrays的内部类, 即修改(set)集合(list)元素, 原数组元素也随之改变 , 但没有实现修改集合个数(add/remove/clear)的相关方法, 抛出UnsuppotedOperationException;
public staticList asList(T... a) { // 此处 ArrayList 为Arrays的一个内部类, 并非java.util.ArrayList return new ArrayList<>(a); }
避免修改问题:
List
- 集合转数组: toArray(T[] array) ; 注意传入类型T一致 (数组长度小于集合长度问题)
6.5 集合与泛型
- List / List
- List<?> 通配符集合,赋值之后就不可以随便添加元素; 但是可以remove()和clear(); 一般作为参数来接收外部的集合, 或者返回一个不知道具体元素类型的集合.
- List 只能放置一中类型, 如果随意转换类型, 会造成 "破窗理论"
- List<? extends T>, 适合 Get First;
- List<? super T> , 适合Put First;