> For the complete documentation index, see [llms.txt](https://gitbook.fantasticmao.cn/tech/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://gitbook.fantasticmao.cn/tech/java/jdk/ji-he-gai-lan.md).

# 集合概览

## List

### ArrayList

* 内部使用 `Object[]` 保存元素
* 实现了 `RandomAccess` 接口
* 新扩容的数组长度 = 旧数组长度 + 旧数组长度 / 2
* 查询元素 O(1)，插入元素 O(n)
* 源码走读请见 [Gist](https://gist.github.com/fantasticmao/68258d17fe0dead18b816b5a750ba28c)

### LinkedList

* 使用双向链表保存内部元素
* 实现了 `Deque` 接口
* 查询元素 O(n)，插入元素 O(1)
* 源码走读请见 [Gist](https://gist.github.com/fantasticmao/75b6cb284ff1dfd488627d83498585d8)

### 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](https://gist.github.com/fantasticmao/9c088055dab10cdd1247e007bde6c7e5)

### LinkedHashMap

* 基于 `HashMap` 实现，继承重写 `HashMap.Node` 类为 **双向链表**
* 可以保证插入顺序
* 源码走读请见 [Gist](https://gist.github.com/fantasticmao/2042aa3a1c62c02f734109a4081f9f43)

### TreeMap

* 基于红黑树算法实现
* 支持排序操作

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

1. 节点是红色或者黑色
2. 根节点是黑色
3. 每个叶子节点都是黑色
4. 每个红色节点必须连接两个黑色子节点
5. 任意节点到它的叶子节点的所有路径都包含相同数目的黑色节点

### HashTable

* 内部使用节点数组 + 链表保存元素
* 使用 `(hash & 0x7FFFFFFF) % tab.length` 计算元素在数组内的下标位置
* 不允许 key == null
* 使用 `synchronized` 同步：对内部元素的所有操作都会锁定
* 源码走读请见 [Gist](https://gist.github.com/fantasticmao/77a9752014c1e05860840e711627d474)

### ConcurrentHashMap

* 内部的数据结构和算法和 `HashMap` 类似：使用节点数组 + 链表/红黑树保存元素，使用 `(table.lenth - 1) & hashCode` 计算元素在数组内的下标位置
* 使用 CAS 同步节点数组，使用 `synchronized` 同步链表/红黑树：添加元素时会锁定，读取元素时不会锁定

### WeakHashMap

* 内部使用 `WeakReference` 节点数组 + 链表保存元素
* 使用 `(table.lenth - 1) & hashCode` 计算元素在数组内的下标位置

## Queue

### ArrayBlockingQueue

* 有界阻塞队列，基于数组实现
* 内部使用 `ReentrantLock` 和 `Condition` 实现阻塞逻辑

### LinkedBlockingQueue

* 无界阻塞队列，基于链表实现
* 内部使用 `ReentrantLock` 和 `Condition` 实现阻塞逻辑

### ConcurrentLinkedQueue

* 无届非阻塞队列，基于链表实现
* 使用 CAS 修改链表节点