集合概览

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

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

  • 内部使用 ReentrantLockCondition 实现阻塞逻辑

LinkedBlockingQueue

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

  • 内部使用 ReentrantLockCondition 实现阻塞逻辑

ConcurrentLinkedQueue

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

  • 使用 CAS 修改链表节点

最后更新于