Collections Feature List

Abstract：Java 8 主要容器类特性一览

⭐️For more detailed soure-code analysis,check my github repo : Java-source-reading

⭐️以下特性均以jdk1.8为准

⚙️ General-purpose implementations^[1]

Interfaces	Hash table	Resizable array	Tree	Linked list	Hash table + Linked list
Set	⭐️HashSet		TreeSet		LinkedHashSet
List		⭐️ArrayList		LinkedList
Queue
Deque		⭐️ArrayDeque		⭐️LinkedList
Map	⭐️HashMap		TreeMap		LinkedHashMap

General feature

✔️ 支持clone、序列化

❌ 线程不安全:Thread unsafe

List Implementations

List	ArrayList	LinkedList
👉底层数据结构	数组	双向链表
✔️擅长的操作	大量随机访问	插入、删除
❌不擅长的操作	插入、删除	随机访问
🚢默认初始容量	0	0
🚧默认扩容规则	小于10则容量为10 大于等于10扩容1.5倍	+1
⭐️重要特性

备注：

• ArrayList数组为transisent修饰，重写了readObject()&writeObject()，因此只会序列化有元素的那部分
• modCount记录了结构变化的次数，如果在迭代&序列化过程中modCount发生了改变，那么将会抛出ConcurrentModificationException

Set Implementations

Set	HashSet	LInkedHashSet	TreeSet
👉底层数据结构	HashMap	链表+HashSet	红黑树
✔️擅长的操作	查找	查找	有序操作
❌不擅长的操作
🚢默认初始容量	8	8
🚧默认扩容规则	容量达到0.75*size时扩容2倍	同HashSet
⭐️重要特性	元素不可修改	维护了插入顺序，1.8桶链表尾部插入

Map Implementations

Map	HashMap	LInkedHashMap	TreeMap
👉底层数据结构	数组（桶）+链表（桶元素）+红黑树	同HashMap+双向链表	红黑树
✔️擅长的操作	查找	查找	有序操作
❌不擅长的操作			查找O(logN)
🚢默认初始容量	8	8
🚧默认扩容规则	容量达到0.75*size时扩容2倍	同HashMap
⭐️重要特性		维护了插入顺序，1.8桶链表尾部插入

Queue Implementations

List	PriorityQueue
👉底层数据结构	数组
✔️擅长的操作	维护最大/最小堆、TopK问题、查找
❌不擅长的操作
🚢默认初始容量	0
🚧默认扩容规则	容量小于64：每次+2 否则扩容1.5倍
⭐️重要特性	桶排序O(n)

Deque Implementations

List	ArrayDeque	LinkedList
👉底层数据结构	数组	参见List
✔️擅长的操作	维护最大/最小堆、TopK问题、查找
❌不擅长的操作
🚢默认初始容量	16
🚧默认扩容规则	容量小于64：每次+2 否则扩容1.5倍
⭐️重要特性	桶排序O(n)

⚛️ Concurrent implementations

General feature

✔️ 支持clone、序列化

⚛️ 线程安全:Thread safe

List Implementations

List	CopyOnWriteArrayList	Vector（不推荐)
👉底层数据结构	数组+ReentrantLock	数组+synchronized
✔️擅长的操作	大量随机访问
❌不擅长的操作	大量写操作，复制需要额外空间开销，读实时性
🚢默认初始容量	0
🚧默认扩容规则	同ArrayList
⭐️重要特性	读写分离，写时复制数组，不具备读实时性	略快于Collections.synchronizedList()

Map

ConcurrentHashMap

---

未完待续…

---

1. Trail: Collections ↩︎