集合概览

List

ArrayList

• 内部使用 Object[] 保存元素

• 实现了 RandomAccess 接口

• 新扩容的数组长度 = 旧数组长度 + 旧数组长度 / 2

• 查询元素 O(1)，插入元素 O(n)

• 源码走读请见 Gist

LinkedList

• 使用双向链表保存内部元素

• 实现了 Deque 接口

• 查询元素 O(n)，插入元素 O(1)

• 源码走读请见 Gist

CopyOnWriteArrayList

• 内部使用 Object[] 保存元素

• 使用 volatile 修饰 Object[]：保证查询元素的可见性

• 实现了 RandomAccess 接口

• 使用 ReentrantLock 同步：修改元素时会锁定，查询元素时不会锁定

Vector

• 内部使用 Object[] 保存元素

• 实现了 RandomAccess 接口

• 使用 synchronized 同步：对内部元素的所有操作都会锁定

Stack

• 继承 Vector

• 实现 LIFO 操作：Last In，First Out

Set

HashSet

• 基于 HashMap 实现，Key 是 Set 集合元素，Value 是 new Object() 对象

• 不能保证顺序

LinkedHashSet

• 基于 LinkedHashMap 实现，Key 是 Set 集合元素，Value 是 new Object() 对象

• 可以保证插入顺序

TreeSet

• 基于 TreeMap 实现

• 支持排序操作

CopyOnWriteArraySet

• 基于 CopyOnWriteArrayList 实现

Map

HashMap

• 内部使用节点数组 + 链表/红黑树保存元素

• 使用 (table.lenth - 1) & (hashCode ^ (hashCode >>> 16)) 计算元素在数组内的下标位置

• 当链表长度大于 8 的时候，JDK8 中会将链表优化为红黑树

• 源码走读请见 Gist

LinkedHashMap

• 基于 HashMap 实现，继承重写 HashMap.Node 类为 双向链表

• 可以保证插入顺序

• 源码走读请见 Gist

TreeMap

• 基于红黑树算法实现

• 支持排序操作

红黑树是一种自平衡的二叉查找树，性质如下：

1. 节点是红色或者黑色

2. 根节点是黑色

3. 每个叶子节点都是黑色

4. 每个红色节点必须连接两个黑色子节点

5. 任意节点到它的叶子节点的所有路径都包含相同数目的黑色节点

HashTable

• 内部使用节点数组 + 链表保存元素

• 使用 (hash & 0x7FFFFFFF) % tab.length 计算元素在数组内的下标位置

• 不允许 key == null

• 使用 synchronized 同步：对内部元素的所有操作都会锁定

• 源码走读请见 Gist

ConcurrentHashMap

• 内部的数据结构和算法和 HashMap 类似：使用节点数组 + 链表/红黑树保存元素，使用 (table.lenth - 1) & hashCode 计算元素在数组内的下标位置

• 使用 CAS 同步节点数组，使用 synchronized 同步链表/红黑树：添加元素时会锁定，读取元素时不会锁定

WeakHashMap

• 内部使用 WeakReference 节点数组 + 链表保存元素

• 使用 (table.lenth - 1) & hashCode 计算元素在数组内的下标位置

Queue

ArrayBlockingQueue

• 有界阻塞队列，基于数组实现

• 内部使用 ReentrantLock 和 Condition 实现阻塞逻辑

LinkedBlockingQueue

• 无界阻塞队列，基于链表实现

• 内部使用 ReentrantLock 和 Condition 实现阻塞逻辑

ConcurrentLinkedQueue

• 无届非阻塞队列，基于链表实现

• 使用 CAS 修改链表节点