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 修改链表节点