# 集合概览

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gitbook.fantasticmao.cn/tech/java/jdk/ji-he-gai-lan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.