[toc]
# 二、Java集合与数据结构
容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。
`List`是**有序队列**，List中可以*有重复*的元素
`Set`是**数学组集合**概念，*没有重复*元素
为了方便，抽象出了AbstractCollection抽象类，它实现了Collection中的绝大部分函数；这样，在Collection的实现类中，我们就可以通过继承AbstractCollection省去重复编码。AbstractList和AbstractSet都继承于AbstractCollection，具体的List实现类继承于AbstractList，而Set的实现类则继承于AbstractSet。
Collection中有一个iterator()函数，它的作用是返回一个Iterator接口。通常，我们通过Iterator迭代器来遍历集合。ListIterator是List接口所特有的，在List接口中，通过ListIterator()返回一个ListIterator对象。
## 1、概览
### 1.1、集合Collection
#### 1.1.1 Set
* `TreeSet`：基于**红黑树**实现，支持**有序性**操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
* `HashSet`：基于**哈希表**实现，支持*快速查找*，但*不支持有序*性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。
* `LinkedHashSet`：具有 HashSet 的查找效率，并兼顾**有序性**，且内部使用**双向链表**维护元素的插入*顺序*。
#### 1.1.2 List
* `ArrayList`：基于**动态数组**实现，支持***随机访问***，查找快，增删慢。
* `Vector`：和 ArrayList 类似，但它是*线程安全*的。
* `LinkedList`：基于**双向链表**实现，只能***顺序访问***，增删快，查找慢。不仅如此，LinkedList 还可以用作栈、队列和双向队列。
#### 1.1.3 Queue
* `LinkedList`：可以用它来实现*双向队列*。
* `PriorityQueue`：基于**堆结构**实现，可以用它来实现*优先队列*。
### 1.2、Map
* `TreeMap`：基于**红黑树**实现。
* `HashMap`：基于**哈希表**实现。
* `HashTable`：和 HashMap 类似，但它是*线程安全*的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用**ConcurrentHashMap** 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了*分段锁*。
* `LinkedHashMap`：使用**双向链表**来维护元素的*顺序*，顺序为*插入顺序*或者*最近最少使用（LRU）顺序*。
## 2、源码分析
### 2.1 ArrayList
因为 ArrayList 是基于**数组（Object[] elementData）**实现的，所以支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。
```java
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess,
Cloneable, java.io.Serializable
```
#### 2.1.1 添加元素及扩容
添加元素时使用 **ensureCapacityInternal()** 方法来保证容量足够，如果不够时，需要使用 *grow()* 方法进行扩容，新容量的大小为 `oldCapacity + (oldCapacity >> 1)`，也就是旧容量的 1.5 倍,如果新容量大于扩容后的容量，直接将新容量作为扩容的容量。
扩容操作需要调用 `Arrays.copyOf()` 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。
**以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10**
```java
/**
* 在此列表中的指定位置插入指定的元素。
* 先调用 rangeCheckForAdd 对index进行界限检查；
* 然后调用 ensureCapacityInternal 方法保证capacity足够大；
* 再将从index开始之后的所有成员后移一个位置；
* 将element插入index位置；最后size加1。
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
// Increments modCount!!
ensureCapacityInternal(size + 1);
//arraycopy()这个实现数组之间复制的方法一定要看一下，
//下面就用到了arraycopy()方法实现数组自己复制自己
System.arraycopy(elementData, index, elementData,
index + 1,size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
```
#### 2.1.2 删除元素
需要调用 `System.arraycopy()` 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看出 ArrayList 删除元素的代价是非常高的。
```java
/**
* 从列表中删除指定元素的第一个出现（如果存在）。
* 如果列表不包含该元素，则它不会更改。
* 返回true，如果此列表包含指定的元素
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData,
index+1, elementData, index,numMoved);
elementData[--size] = null; // clear to let GC do its work
}
```
#### 2.1.3 Fail-fast
`modCount` 用来记录 ArrayList 结构**发生变化的次数**。结构发生变化是指**添加**或者**删除**至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。
在进行**序列化**或者**迭代**等操作时，需要**比较操作前后 modCount**（在AbstractList中定义）**是否改变**，如果改变了需要抛出 ConcurrentModificationException。
#### 2.1.4 序列化
ArrayList 基于数组实现，并且具有**动态扩容**特性，因此保存元素的数组不一定都会被使用，那么就**没必要全部**进行**序列化**。
保存元素的数组 `elementData` 使用 `transient` 修饰，该关键字声明数组默认不会被序列化。ArrayList 实现了 `writeObject()` 和 `readObject()` 来控制只序列化数组中**有元素填充那部分**内容。
#### 2.1.5 System.arraycopy() & Arrays.copyOf()
```java
public static native void
arraycopy(Object src,int srcPos,Object dest,int destPos,int length);
```
`src`：the source array.**源数组**；
`srcPos`：starting position in the source array.**源数组**要复制的*起始位置*
`est`：the destination array.**目标数组**（将原数组复制到目标数组）
`destPos` ：starting position in the destination data.**目标数组***起始位置*（从目标数组的哪个下标开始复制操作）
`length`：the number of array elements to be copied.复制源数组的**长度**（从srcPos开始复制几个）
Arrays.copyOf() 内部实际调用了 System.arraycopy()方法，它的返回值时一个新的数组
#### 2.1.6 ArrayList继承AbstractList为什么还要实现List
如果不实现List，使用Class.getInterfaces时无法获取到对应的接口，可能在实现代理时出现问题。
#### 2.1.7 快速失败(fail-fast) 和安全失败(fail-safe)
**一：快速失败（fail—fast）**
在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增
加、删除、修改），则会抛出 Concurrent Modification Exception。
**原理：**迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCo
unt 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。每当迭代器使
用 hashNext()/next()遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmod
Count 值，是的话就返回遍历；否则抛出异常，终止遍历。
**注意：**这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如
果集合发生变化时修改 modCount 值刚好又设置为了 expectedmodCount 值，则异常不会
抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检
测并发修改的 bug。
**场景：**java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过
程中被修改）。
**二：安全失败（fail—safe）**
采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原
有集合内容，在拷贝的集合上进行遍历。
**原理：**由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改
并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。
**缺点：**基于拷贝内容的优点是避免了 Concurrent Modification Exception，但同样地，
迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，
在遍历期间原集合发生的修改迭代器是不知道的。
**场景：**java.util.concurrent 包下的容器都是安全失败，可以在多线程下并发使用，并
发修改。
快速失败和安全失败是对迭代器而言的。 快速失败：当在迭代一个集合的时候，如果有另
外一个线程在修改这个集合，就会抛出 ConcurrentModification 异常，java.util 下都是快速
失败。 安全失败：在迭代时候会在集合二层做一个拷贝，所以在修改集合上层元素不会影
响下层。在 java.util.concurrent 下都是安全失败
### 2.2 Vector
>1. `ArrayList` 是 `List` 的主要实现类，底层使用 `Object[ ]`存储，适用于频繁的查找工作，线程不安全 ；
>2. `Vector` 是 `List` 的古老实现类，底层使用 `Object[ ]`存储，线程安全的。
它的实现与 ArrayList 类似，但是使用了 `synchronized` 进行同步。
* `Vector` 是**同步**的，因此**开销**就比 ArrayList 要**大**，访问速度更慢。最好使用 ArrayList 而不是 Vector，因为同步操作完全可以由程序员自己来控制；
* `Vector` 每次**扩容**请求其大小的 **2 倍**（也可以通过构造函数设置增长的容量），而 `ArrayList` 是 **1.5 倍**
**ArrayList线程安全的方案：**
可以使用 Collections.synchronizedList()得到一个线程安全的 ArrayList。
```java
List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);
```
也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。
```java
List<String> list = new CopyOnWriteArrayList<>();
```
### 2.3 LinkedList
基于双向链表实现，使用 Node 存储链表节点信息。
```java
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
```
每个链表存储了 first 和 last 指针:
```java
transient Node<E> first;
transient Node<E> last;
```
LinkedList是通过双向链表的，如何实现get(index)方法？它就是通过一个**计数索引值**来实现的。例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。
### 2.4 Arraylist 与 LinkedList 区别?
* **1.是否保证线程安全**：ArrayList 和 LinkedList 都是不同步的，也就是*不保证线程安全*；
* **2. 底层数据结构**：Arraylist底层使用的是*Object 数组*；LinkedList底层使用的是 *双向链表*（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
* **3. 插入和删除是否受元素位置的影响**：
* ① `ArrayList`采用*数组*存储，所以*插入*和*删除*元素的时间复杂度*受元素位置的影响*。比如：执行add(E e) 方法的时候， ArrayList会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
* ② `LinkedList` 采用*链表*存储，所以*插入，删除*元素时间复杂度*不受元素位置的影响*，都是近似 O（1）而数组为近似 O（n）。
* **4. 是否支持快速随机访问**：`LinkedList`*不支持*高效的随机元素访问，而`ArrayList`*支持*。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index) 方法)。
* **5. 内存空间占用：** `ArrayList`的空 间浪费主要体现在在*list列表的结尾*会预留一定的容量空间，而`LinkedList`的空间花费则体现在它的*每一个元素*都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。
### 2.5 HashTable
#### 2.5.1 参数
（1）table 是一个 Entry[]数组类型，而 Entry 实际上就是一个单向链表。哈希表的"key-value 键值对"都是存储在 Entry 数组中的。
（2）count 是 Hashtable 的大小，它是 Hashtable 保存的键值对的数量。
（3）threshold 是 Hashtable 的阈值，用于判断是否需要调整 Hashtable 的容量。threshold 的值="容量*加载因子"。
（4）loadFactor 就是加载因子。
（5）modCount 是用来实现 fail-fast 机制的
#### 2.5.2 put
从下面的代码中我们可以看出，Hashtable 中的 key 和 value 是不允许为空的，当我们想要想 Hashtable 中添加元素的时候，首先计算 key 的 hash 值，然后通过 hash 值确定在 table 数组中的索引位置，最后将 value 值替换或者插入新的元素，如果容器的数量达到阈值，就会进行扩充。
#### 2.5.3 get
#### 2.5.4 Remove
在下面代码中，如果 prev 为 null 了，那么说明第一个元素就是要删除的元素，那么就直接指向第一个元素的下一个即可。
#### 2.5.5 扩容
- 默认初始容量为 11线程安全，但是速度慢，不允许 key/value 为 null
- 加载因子为 0.75：即当 元素个数 超过 容量长度的 0.75 倍 时，进行扩容
- 扩容增量：2*原数组长度+1
如 HashTable 的容量为 11，一次扩容后是容量为 23
### 2.6 HashMap
>HashMap *允许 null* 键和 null 值，在计算哈键的哈希值时，null 键哈希值为 0。HashMap 并*不保证键值对的顺序*(LinkedHashMap解决这个问题)，这意味着在进行某些操作后，键值对的顺序可能会发生变化。另外，需要注意的是，HashMap 是*非线程安全*类，在多线程环境下可能会存在问题。
#### 2.6.1 JDK1.7版本
内部包含了一个 Entry 类型的数组 table。初始化容量为16，负载因子为0.75
```java
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
```
大方向上， HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。上图中，每个绿色的实体是嵌套类 Entry 的实例， Entry 包含四个属性： key, value, hash 值和用于单向链表的 next。
1. capacity：当前数组容量，始终保持 2^n，扩容后数组大小为当前的 2 倍。
2. oadFactor：负载因子，默认为 0.75。
3. threshold：扩容的阈值，等于 capacity * loadFactor
Java8 对 HashMap 进行了一些修改， 最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话， 需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中， 当链表中的元素超过了 8 个以后，
会将链表转换为红黑树，在这些位置查找的时候可以降低时间复杂度为O(logN)。
#### 2.6.2 存储
Entry 存储着键值对。它包含了四个字段，从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当成一个桶，一个桶存放一个链表。HashMap 使用**拉链法**来解决冲突，同一个链表中存放哈希值和散列桶取模运算结果相同的 Entry。
应该注意到链表的插入是以**头插法**方式进行的，哈希冲突时插入在链表头部。
为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。可能会想到采用%取余的操作来实现。`hash%table.length`
但是，重点来了：**“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。”** 并且 **采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方** 此外，使`lenght-1`的全部位为1，能使计算出来的下标分布更均匀，减少哈希碰撞。*在扩容相关的transfer方法中，也有调用indexFor重新计算下标。容量设计成2的n次幂能使扩容时重新计算的下标相对稳定，减少移动元素
#### 2.6.3 查找 get
查找需要分成两步进行：
* 计算键值对所在的桶；
* 在链表上顺序查找，时间复杂度显然和链表的长度成正比。
#### 2.6.4 插入 put
HashMap **允许插入**键为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法，也就无法确定该键值对的桶下标，只能通过*强制指定一个桶下标来存*放。HashMap 使用*第 0 个*桶存放键为 null 的键值对。*因此 HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null。*
*这里 HashMap 里面用到链式数据结构的一个概念。上面我们提到过 Entry 类里面有一个 next 属性，作用是指向下一个 Entry。打个比方， 第一个键值对 A 进来，通过计算其 key 的 hash 得到的 index=0，记做:Entry[0] = A。一会后又进来一个键值对 B，通过计算其 index 也等于 0，现在怎么办？HashMap 会这样做:B.next = A,Entry[0] = B,如果又进来 C,index 也等于 0,那么 C.next = B,Entry[0] = C；这样我们发现 index=0 的地方其实存取了 A,B,C 三个键值对,他们通过 next 这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，HashMap 的大致实现。*
#### 2.6.5 扩容
设 HashMap 的 table 长度为 M，需要存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此平均查找次数的复杂度为 $O(N/M)$。为了让查找的成本降低，应该尽可能使得 N/M 尽可能小，因此需要保证 M 尽可能大，也就是说 table 要尽可能大。
- `capacity`：当前数组容量，始终保持2^n，默认为16。扩容是扩充为当前的2倍
- `size`：当前键值对的数量
- `threshold`：size的临界值，大于等于threshold就需要扩容。**threshold = (int)(Capacity * loadFactor)**
- `load_factor`：负载因子，默认值为*0.75*
HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。
#### 2.6.6 与 HashTable 的比较
* HashTable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。
* HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。
* HashMap 的迭代器是 fail-fast 迭代器。
* HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。
* HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
* 哈希值的使用不同，HashTable直接使用对象的hashCode，代码是这样的：
```java
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
```
而HashMap重新计算hash值，而且用与代替求模：
```java
int hash = hash(k);
int i = indexFor(hash, table.length);
static int hash(Object x) {
int h = x.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
static int indexFor(int h, int length) {
return h & (length-1);
}
```
#### 2.6.7 多线程死循环
是多线程**同时put**时，如果同时触发了**rehash操作**，会导致HashMap中的链表中出现**循环节点**，进而使得后面get的时候，会死循环。因为会将同一链表的值翻转，当一个线程完成翻转后，第二个线程再次翻转就会出现死循环问题。（transfor方法，第二个线程的第三次循环会出问题）
要想实现线程安全，那么需要调用 collections 类的静态方法
synchronizeMap（）实现
#### 2.6.8 JDK1.8版本
当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
扩容时需要把键值对重新放到对应的桶上，采用一个特殊机制，降低重新计算桶下标的操作。只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”
其中n为table的长度。
>参考：
>【HashMap 源码浅析 1.8】https://blog.51cto.com/14220760/2363572
>【Java 8系列之重新认识HashMap】https://zhuanlan.zhihu.com/p/21673805
#### 2.6.9 哈希冲突详解
一般来说哈希冲突有两大类**解决方式**
1. Separate chaining
2. Open addressing
Java 中采用的是第一种 Separate chaining，即在发生碰撞的那个桶后面再加一条“链”来存储，那么这个“链”使用的具体是什么数据结构，不同的版本稍有不同：
在 JDK1.6 和 1.7 中，是用**链表**存储的，这样如果碰撞很多的话，就变成了在链表上的查找，worst case 就是 O(n)；
在 JDK 1.8 进行了优化，当链表长度较大时（超过 8），会采用**红黑树**来存储，这样大大提高了查找效率。
第二种方法 open addressing 也是非常重要的思想，因为在真实的分布式系统里，有很多地方会用到 hash 的思想但又不适合用 seprate chaining。
这种方法是顺序查找，如果这个桶里已经被占了，那就按照“**某种方式**”继续找下一个没有被占的桶，直到找到第一个空的。
<img src="https://i.loli.net/2020/12/23/BK8qx7cADzkIOnt.png" alt="image-20201223161944059" style="zoom: 50%;" />
如图所示，John Smith 和 Sandra Dee 发生了哈希冲突，都被计算到 152 号桶，于是 Sandra 就去了下一个空位 - 153 号桶，当然也会对之后的 key 发生影响：Ted Baker 计算结果本应是放在 153 号的，但鉴于已经被 Sandra 占了，就只能再去下一个空位了，所以到了 154 号。
这种方式叫做 Linear probing 线性探查，就像上图所示，一个个的顺着找下一个空位。当然还有其他的方式，比如去找平方数，或者 Double hashing.
### 2.7 ConcurrentHashMap
一个 ConcurrentHashMap 维护一个 Segment 数组，一个 Segment 维护一
个 HashEntry 数组。
**Segment 段**
ConcurrentHashMap 和 HashMap 思路是差不多的，但是因为它支持并发操作，所以要复杂一些。整个 ConcurrentHashMap 由一个个 Segment 组成， Segment 代表”部分“或”一段“的意思，所以很多地方都会将其描述为分段锁。注意，行文中，我很多地方用了“槽”来代表一个segment。
**线程安全（Segment 继承 ReentrantLock 加锁）**
简单理解就是， ConcurrentHashMap 是一个 Segment 数组， Segment 通过继承ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全
#### 2.7.1 JDK1.7 ConCurrentHashMap 原理
其中 Segment 继承于 ReentrantLock
<img src="https://i.loli.net/2020/12/23/sYorGxkKfiHgZty.png" alt="image-20201223162327891" style="zoom:50%;" />
**并行度（默认 16）**
concurrencyLevel：并行级别、并发数、 Segment 数，怎么翻译不重要，理解它。默认是 16，也就是说 ConcurrentHashMap 有 16 个 Segments，所以理论上， 这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。再具体到每个 Segment 内部，其实每个 Segment 很像之前介绍的 HashMap，不过它要保证线程安全，所以处理起来要麻烦些.
Segment 继承了 ReentrantLock，表明每个 segment 都可以当做一个锁。这样对每个 segment 中的数据需要同步操作的话都是使用每个 segment 容器对象自身的锁来实现。只有对全局需要改变时锁定的是所有的 segment。
#### 2.7.2 JDK1.7 Get
**CurrentHashMap 是否使用了锁？？？**
它也没有使用锁来同步，只是判断获取的 entry 的 value 是否为 null，为null 时才使用加锁的方式再次去获取。 这里可以看出并没有使用锁，但是value 的值为 null 时候才是使用了加锁！！！
**Get 原理：**
第一步，先判断一下 count != 0；count 变量表示 segment 中存在 entry的个数。如果为 0 就不用找了。假设这个时候恰好另一个线程 put 或者 remove了这个 segment 中的一个 entry，会不会导致两个线程看到的 count 值不一致呢？看一下 count 变量的定义： transient volatile int count;它使用了 volatile 来修改。我们前文说过，Java5 之后，JMM 实现了对 volatile的保证：对 volatile 域的写入操作 happens-before 于每一个后续对同一个域
的读写操作。所以，每次判断 count 变量的时候，即使恰好其他线程改变了
segment 也会体现出来
- **1) 在 get 代码的①和②之间，另一个线程新增了一个 entry**
如果另一个线程新增的这个 entry 又恰好是我们要 get 的，这事儿就比较微妙了。下图大致描述了 put 一个新的 entry 的过程。
<img src="https://i.loli.net/2020/12/24/wCiepaL7SAHEG2y.png" alt="image-20201224093427997" style="zoom:67%;" />
因为每个 HashEntry 中的 next 也是 final 的，没法对链表最后一个元素增加一个后续 entry 所以新增一个 entry 的实现方式只能通过头结点来插入了。newEntry 对象是通过 new HashEntry(K k , V v, HashEntry next) 来创建的。如果另一个线程刚好 new 这个对象时，当前线程来 get 它。因为没有同步，就可能会出现当前线程得到的newEntry 对象是一个没有完全构造好的对象引用。 如果在这个 new 的对象的后面，则完全不影响，如果刚好是这个 new的对象，那么当刚好这个对象没有完全构造好，也就是说这个对象的 value 值为 null,就出现了如下所示的代码，需要重新加锁再次读取这个值！
- **2) 在 get 代码的①和②之间，另一个线程修改了一个 entry 的 value**
value 是用 volitale 修饰的，可以保证读取时获取到的是修改后的值。
- **3) 在 get 代码的①之后，另一个线程删除了一个 entry**
假设我们的链表元素是：e1-> e2 -> e3 -> e4 我们要删除 e3 这个 entry，因为 HashEntry 中 next 的不可变，所以我们无法直接把 e2 的 next 指向 e4，而是将要删除的节点之前的节点复制一份，形成新的链表。它的实现大致如下图所示：
<img src="https://i.loli.net/2020/12/24/2zBZMuOjDNY7edX.png" alt="image-20201224093637324" style="zoom:67%;" />
如果我们 get 的也恰巧是 e3，可能我们顺着链表刚找到 e1，这时另一个线程就执行了删除 e3 的操作，而我们线程还会继续沿着旧的链表找到 e3 返回。这里没有办法实时保证了，也就是说没办法看到最新的。
我们第①处就判断了 count 变量，它保障了在 ①处能看到其他线程修改后的。①之后到②之间，如果再次发生了其他线程再删除了 entry 节点，就没法保证看到最新的了，这时候的 get 的实际上是未更新过的！！！。
不过这也没什么关系，即使我们返回 e3 的时候，它被其他线程删除了，暴漏出去的 e3 也不会对我们新的链表造成影响。
#### 2.7.3 JDK1.7 Put
1. 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
2. 遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
3. 不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
4. 最后会解除在 1 中所获取当前 Segment 的锁。
可以说是首先找到segment，确定是哪一个segment,然后在这个 segment中遍历查找 key值是要查找的key值得entry,如果找到，那么就修改该key,如果没找到，那么就在头部新加一个 entry.
#### 2.7.4 JDK1.7 Remove
<img src="https://i.loli.net/2020/12/24/DtOobZRdF9qPAvU.png" alt="image-20201224094626707" style="zoom:67%;" />
#### 2.7.5 JDK1.8 ConCurrentHashMap原理
1. 其中抛弃了原有的 其中抛弃了原有的 Segment 分段锁，而采用了 分段锁，而采用了CAS + synchronized 来保证并发安全性。
2. 大于 大于 8 的时候才去红黑树 的时候才去红黑树链表转红黑树的阀值，当 链表转红黑树的阀值，当 table[i]下面的链表长度 下面的链表长度大于 大于 8时就转化为红黑树结构。
**Java8 实现 （引入了红黑树）**
<img src="https://i.loli.net/2020/12/23/gRh41vz6en2aAfE.png" alt="image-20201223162435125" style="zoom: 50%;" />
#### 2.7.6 JDK1.8 get
- 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
- 如果是红黑树那就按照树的方式获取值。
- 就不满足那就按照链表的方式遍历获取值
#### 2.7.7 JDK1.8 Put
- 根据 key 计算出 hashcode 。
- 判断是否需要进行初始化
- f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS
尝试写入，失败则自旋保证成功。
- 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
- 如果都不满足，则利用 synchronized 锁写入数据(分为链表写入和红黑树写入）。
- 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
#### 2.7.8 HashTable HashMap ConCurrentHashMap区别
**hashtable 和hashmap 区别**
- Hashtable的方法是同步的， HashMap未经同步，所以在多线程场合要手动同步。
- Hashtable不允许null值(key和vlue都不可以）， HashMap允许h值（key和value都可以）
- 两者的遍历方式大同小异， Hashtable仅仅比 HashMap多一个 elements方法。
- Hashtable和 HashMap都能通过 values()方法返回一个 Collection，然后进行遍历处理。
- 两者也都可以通过 entry Set()方法返回一个set，然后进行遍历处理
- HashTable使用 Enumeration， HashMap使用 Iterator
- 哈希值使用不同， Hashtable直接使用对象的 hashCode。而 HashMap重新计箅hash，而且用于代替求模。
- H-ashtable中hash数组默认大小是11，增加的方式是od*2+1. HashMap中hash数组的默认大小是16，而且一定是2的指数
- HashTable基于 Dictionary类，而 HashMap基于 AbstractMap类
**HashMap 和 和 ConCurrentHashMap 区别**
- HashMap是非线程安全的， ConCurrentHashMap是线程安全的
- ConCurrentHashMap将整个Hash桶进行了分段 segment，也就是将这个大的数组分成了几个小的片段 segment，而且毎个小的片段 segment上面有锁存在，那么在插入元素的时候就需要先找到应该插入到哪一个片段 segment，然后再在这个片段上面进行插入，而且这里还斋要获取 segment锁
- ConcurmentHashMap让锁的拉度更精细些，并发性能更好。
**ConcurrentHashMap 和 HashTable 区别**
<img src="https://i.loli.net/2020/12/24/C6Ua3xOc7VGPNdL.png" alt="image-20201224102022411" style="zoom: 50%;" />
### 2.8 LinkedHashMap
>LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条**双向链表**，解决了 HashMap 不能随时保持**遍历顺序**和**插入顺序**一致的问题。除此之外，LinkedHashMap 对**访问顺序**(LRU)也提供了相关支持。在一些场景下，该特性很有用，比如缓存。
<img src="https://i.loli.net/2020/02/01/UK5B6SGw94MlgI3.jpg" alt="-w500" style="zoom:50%;" />
* 继承自 HashMap，因此具有和 HashMap 一样的快速查找特性。
```java
public class LinkedHashMap<K,V>
extends HashMap<K,V> implements Map<K,V>
```
内部维护了一个`双向链表`，用来维护**插入顺序**或者 **LRU 顺序**。
*accessOrder 决定了顺序，默认为 false，此时维护的是插入顺序。初始化为true则为访问顺序*
```java
final boolean accessOrder;
```
LinkedHashMap 最重要的是以下用于维护顺序的函数，它们会在 put、get 等方法中调用。
```java
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
```
#### 2.7.1 afterNodeAccess()访问后的处理
当一个节点被访问时，如果 **accessOrder 为 true**（*即它按访问顺序维护链表）*，则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后，在每次访问一个节点时，会将这个节点移到链表尾部，保证链表尾部是最近访问的节点，那么链表首部就是最近最久未使用的节点。
```java
// 如果 accessOrder 为 true，
//则调用 afterNodeAccess 将被访问节点移动到链表最后
if (accessOrder)
afterNodeAccess(e);
```
假设我们访问下图键值为3的节点，访问前结构为：
<img src="https://i.loli.net/2020/02/01/uOJ6Y4znKy1TCx8.jpg" alt="-w500" style="zoom: 50%;" />
访问后，键值为3的节点将会被移动到双向链表的最后位置，其前驱和后继也会跟着更新。访问后的结构如下
<img src="https://i.loli.net/2020/02/01/yhxHFNZKTnVJB6W.jpg" alt="-w500" style="zoom:50%;" />
#### 2.7.2 afterNodeRemoval()删除后的处理
删除的过程并不复杂，上面这么多代码其实就做了三件事：
- 根据 hash 定位到桶位置
- 遍历链表或调用红黑树相关的删除方法
- 从 LinkedHashMap 维护的双链表中移除要删除的节点
<img src="https://i.loli.net/2020/02/01/q4xYiMfKhXP2HyI.jpg" alt="-w500" style="zoom:50%;" />
根据 hash 定位到该节点属于3号桶，然后在对3号桶保存的单链表进行遍历。找到要删除的节点后，先从单链表中移除该节点。如下：
然后再双向链表中移除该节点：
<img src="https://i.loli.net/2020/02/01/UvEDkdCButhQwgF.jpg" alt="-w500" style="zoom:50%;" />
#### 2.7.3 afterNodeInsertion()
在 put 等操作之后执行，当 `removeEldestEntry()` 方法返回 true 时会移除最晚的节点，也就是链表首部节点 first。
`removeEldestEntry()`（可以用来判断节点是否超限） 默认为 false，如果需要让它为 true，需要继承 `LinkedHashMap` 并且覆盖这个方法的实现，这在实现 LRU 的缓存中特别有用，通过移除最近最久未使用的节点，从而保证缓存空间足够，并且缓存的数据都是热点数据。
```java
void afterNodeInsertion(boolean evict){
LinkedHashMap.Entry<K,V> first;
// 根据条件判断是否移除最近最少被访问的节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
```
>参考：
>【LinkedHashMap 源码详细分析（JDK1.8）】https://www.imooc.com/article/22931
#### 2.7.4 LRU 缓存
以下是使用 LinkedHashMap 实现的一个 LRU 缓存：
* 设定最大缓存空间 MAX_ENTRIES 为 3；
* 使用 LinkedHashMap 的构造函数将 accessOrder 设置为 true，开启 LRU 顺序；
* 覆盖 removeEldestEntry() 方法实现，在节点多于 MAX_ENTRIES 就会将最近最久未使用的数据移除
```java
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_ENTRIES = 3;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
LRUCache() {
super(MAX_ENTRIES, 0.75f, true);
}
}
public static void main(String[] args) {
LRUCache<Integer, String> cache = new LRUCache<>();
cache.put(1, "a");
cache.put(2, "b");//本例中最早且非最近使用
cache.put(3, "c");
cache.get(1);//最近使用
cache.put(4, "d");
System.out.println(cache.keySet());//[3, 1, 4]
}
```
### 2.9 WeakHashMap
#### 2.9.1 存储结构
`WeakHashMap `的 **Entry** 继承自 WeakReference，被 WeakReference 关联的对象在**下一次垃圾回收**时会被回收。
WeakHashMap 主要用来*实现缓存*，通过使用 WeakHashMap 来引用缓存对象，由 JVM 对这部分缓存进行回收。
```java
private static class Entry<K,V>
extends WeakReference<Object> implements Map.Entry<K,V>
```
这个“弱键”的原理呢？大致上就是，通过**WeakReference**和**ReferenceQueue**实现的。 `WeakHashMap`的*key*是“弱键”，即是WeakReference类型的；**ReferenceQueue**是一个队列，它会保存被GC回收的“弱键”。
实现步骤是：
- (01) 新建WeakHashMap，将“**键值对**”添加到WeakHashMap中。实际上，WeakHashMap是通过数组table保存Entry(键值对)；每一个Entry实际上是一个单向链表，即Entry是键值对链表。
- (02) 当**某“弱键”不再被其它对象引用**，并**被GC回收**时。在GC回收该“弱键”时，**这个“弱键”也同时会被添加到ReferenceQueue(queue)队列**中。
- (03) 当下一次我们需要操作WeakHashMap时，会先同步table和queue。table中保存了全部的键值对，而queue中保存被GC回收的键值对；同步它们，就是**删除table中被GC回收的键值对**。
#### 2.9.2 ConcurrentCache
Tomcat 中的 **ConcurrentCache** 使用了 *WeakHashMap* 来实现缓存功能。
ConcurrentCache 采取的是分代缓存：
* **经常使用**的对象放入 eden 中，**eden** 使用 *ConcurrentHashMap* 实现，不用担心会被回收（伊甸园）；
* **不常用的**对象放入 **longterm**，longterm 使用 *WeakHashMap* 实现，这些老对象会被垃圾收集器回收。
* 当调用 `get()` 方法时，会先从 eden 区获取，如果没有找到的话再到 longterm 获取，当从 longterm 获取到就把对象放入 eden 中，从而保证经常被访问的节点不容易被回收。
* 当调用 `put()` 方法时，如果 eden 的大小超过了 size，那么就将 eden 中的所有对象都放入 longterm 中，利用虚拟机回收掉一部分不经常使用的对象。
### 2.10 PriorityQueue
>PriorityQueue 是一个基于优先级堆的无界队列，它的元素都以他们的自然顺序有序排列。Java中的PriorityQueue采用的是堆这种数据结构来实现的,而存储堆采用的则是数组。
**满二叉树**
二叉树当中，叶子节点全部在最底层除了叶子节点外,每个节点都有左右两个子节点
<img src="https://i.loli.net/2020/02/02/PzhCfFqpEkiNKRu.jpg" alt="-w200" style="zoom:50%;" />
**完全二叉树**
如果叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树就叫作完全二叉树
<img src="https://i.loli.net/2020/02/02/8MJjqGkHblZQzcR.jpg" alt="-w400" style="zoom:50%;" />
`堆`是一个**完全二叉树**,堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
- 对于每个节点的值**都大于等于**子树中每个节点值的堆，我们叫做`大顶堆`。
- 对于每个节点的值**都小于等于**子树中每个节点值的堆，我们叫做`小顶堆`。
**PriorityQueue的特点：**
>- 1. PriorityQueue 是基于*堆*的，堆是一个特殊的*完全二叉树*，它的每一个节点的值都必须小于等于（或大于等于）其子树中每个节点的值
- 2. PriorityQueue 的**出队**和**入队**操作时间复杂度都是 *O(log(n))*，仅与堆的高度有关
- 3. PriorityQueue 初始容量为 11，支持**动态扩容**。容量小于 64 时，扩容一倍。大于 64 时，扩容 0.5 倍
- 4. PriorityQueue **不允许 null** 元素，*不允许不可比较的元素*
- 5. PriorityQueue **不是线程安全**的，PriorityBlockingQueue **是线程安全的**
#### 2.10.1 如何实现一个堆
<img src="https://i.loli.net/2020/02/02/YzVTlqLPtIgfWiy.jpg" alt="-w400" style="zoom:50%;" />
可以看出来，数组中下标为i的节点，其左子节点就是下标为 i*2+1 的节点,右子节点则是下标为 i*2+2 的节点。
PriorityQueue数据结构如下:
```java
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 数组
transient Object[] queue;
// 数组中元素个数
private int size = 0;
}
```
#### 2.10.2 新增
新增的时候，我们将插入的数据暂时放置到数组中的**最后一个位置**，运气好的话,它就刚好满足堆特性，也不需要移动元素了。不好的话就需要移动元素位置了。
移动过程如下：**新插入**的节点与*父节点*比较大小，如果不满足子节点大于等于父节点的大小关系(小顶堆)，则*互换*两个节点，一直*重复*这个过程，直到父子节点满足刚才说的那种关系
```java
/*
1.判断插入元素是否为空，为空则抛出NPE异常
2.在判断数组是否需要扩容,如果是则进行扩容
3.如果是第一次插入元素，则放入数组的第一个位置
4.如果不是则进行堆化过程
4.1 找到父节点位置 : (k-1) >>> 1
4.2 判断插入元素的值是否大于父节点(小顶堆)，如果是则结束堆化过程
4.3 如果不是则交换元素位置
4.4 持续上面的1,2,3步骤，直到插入的节点已经是堆顶结点(k==0)
*/
public boolean offer(E e) {
if (e == null) throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length) grow(i + 1);
size = i + 1;
// 第一次插入放入数组的第一个位置(下标从0开始)
if (i == 0) queue[0] = e;
else siftUp(i, e);
return true;
}
// 堆化过程
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
// 1. 父节点位置 (k-1)/2,这里采用无符号右移(值为整数)
int parent = (k - 1) >>> 1;
Object e = queue[parent];
// 2. 如果要插入的元素大于父节点元素的值，则结束堆化过程
if (key.compareTo((E) e) >= 0)
break;
// 3. 交换元素位置
queue[k] = e;
k = parent;
}
queue[k] = key;
}
```
#### 2.10.3 删除
对于小顶堆而言,当删除堆顶元素之后，就需要把第二小的元素放到堆顶,那么第二小的元素就会出现在左右子节点中。
当删除后，如果我们还是迭代的从左右子节点中选择最小元素放入堆顶，就会造成数组空洞，我用下面的图来演示这个问题。
由于删除了一个元素,所以在移动的过程中会导致空洞，所以要找一个元素把这个洞填起来呢？我们可以在删除堆顶元素的时候，将最后一个元素拿来补位。由于在堆化的过程中，都是交换操作，就不会出现数组空洞了。
```java
// k=0, x=queue[size-1]
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
// 找到左右子节点中小的那个节点
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
// 如果比小的那个节点值还要小,则循环结束
if (key.compareTo((E) c) <= 0)
break;
// 移动数据
queue[k] = c;
k = child;
}
queue[k] = key;
}
```
需要注意的是这里的结束条件是k < half,为什么呢？因为我们的堆化是从上到下，只会找一边(要么是左子树，要么是右子树)。
>参考
>https://mp.weixin.qq.com/s/mJbzq1kMs8SpW7baCHUqRA
>https://mp.weixin.qq.com/s/JosUVtCnxs49DWIOD0056g
### 2.11 AVL(平衡二叉搜索树)
#### 2.11.1 二叉搜索树复杂度分析
二叉搜索树退化成链表
- 当n比较大时，两者的性能差异比较大
- 比如当n=1000000时，二叉搜素树的最低高度是20
除了添加会退化成链表以为，多次删除操作也会使其退化
平衡二叉搜索树的出现就是为了防止二叉搜索树退化成链表，使其的操作复杂度维持在$O(log_2N)$
**平衡的概念**
当节点数量固定时，左右子树的高度越接近，这颗二叉树就越平衡（树的高度越低）
如下：同样节点的二叉树，从左到右的平衡性越来越好
最理想的平衡，就是像完全二叉树、满二叉树那些，高度最小
#### 2.11.2 平衡二叉搜索树（Balanced Binary search Tree ）
也称自平衡二叉搜索树，英文简称BBST，经典常见的平衡二叉搜索树有
- AVL树 ：windows NT内核中广泛使用
- 红黑树：
- C++ STL（比如map，set）
- JAVA的TreeMap，TreeSet，HashMap，HashSet
- Linux进程调度
- Nigx的timer管理
#### 2.11.3 AVL树
- 平衡因子（Balance Factor）：某节点左右子树的高度差
- AVL树的特点
- 每个节点的平衡因子只可能是1、0、-1（绝对值小于1，如果超过1，称之为“失衡”）
- 每个节点的左右子树高度差不超过1
- 搜索、添加、删除的时间复杂度是$O(log_2N)$
**添加导致的失衡**
**LL-右旋转（单旋）**
旋转之后仍然是一个二叉搜索树：T0 < n < T1 < p < T2 < g < T3，整棵树再次平衡（仔细观察，旋转之后，高度又回到红线上面，说明子部分的树高度没有变化，原来全树整体再次平衡）选择后续工作：更新g，p高度，更新T2，p，g的parent指向。
**RR-左旋转（单旋）**
**LR-RR左旋转，LL右旋转（双旋转)**
**RL-LL右旋转，RR左旋转**
》https://www.bilibili.com/video/av77758248?p=51
### 2.12 2-3树
2-3树和红黑树有一定的联系，对于理解红黑树会有很大的帮助，所以我们先来看一下2-3树相关的一些性质。首先，2-3树满足二分搜索树的性质。不同的是在2-3树中，存在两种节点。一种是有两个叶子节点的，我们称作“2节点”；另一种是有三个叶子节点的，我们称作“3节点”。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/2-3树节点概览.png" alt="img" style="zoom:33%;" />
如下是一整颗2-3树的示例。需要强调的是2-3树是完全平衡的树，即从根节点到任意一个叶子节点的高度都是相同的。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/2-3树整体示例.png" alt="img" style="zoom:33%;" />
**2-3树怎样保持完全平衡性**
向2-3树中添加一个节点，遵循向二分搜索树中添加节点的基本思路，插入节点比当前节点小，则向当前节点的左子树添加，否则向右子树添加。不过由于2-3树特殊的性质，当要向“2节点”添加节点时，将待插入的节点与该“2节点”进行融合，组成一个新的“3节点”，如下图所示。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/2-3树插入2节点.png" alt="img" style="zoom:33%;" />
如果要向“3节点”添加节点，同向“2节点”添加节点一样，先组成一个临时的4节点，之后再拆分成3个“2节点”，如图所示。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/2-3树插入3节点.png" alt="img" style="zoom:33%;" />
如果要插入的“3节点”的父节点是一个“2节点”，通过上述步骤得到的拆分过成为父节点的“2节点”，需要向原“3节点”的父节点进行融合，组成新的“3节点”。过程如下图所示。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/2-3树插入3节点-父节点.png" alt="img" style="zoom:33%;" />
如果要插入的“3节点”的父节点是一个“3节点”，大体思路相同，向父节点进行融合，只不过此时融合后成为一个临时的“4节点”，之后要再次进行拆分。过程如图所示。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/2-3树插入3节点-父节点3.png" alt="img" style="zoom: 33%;" />
如上所述，2-3树保持了完全的平衡性。说了这么长时间的2-3树，那么2-3树和红黑树之间到底有怎样的关系，下面我们具体来看一下。
#### 2-3树与红黑树
对于2-3树中的“2节点”，对应于红黑树中的“黑节点”，即相当于普通二分搜索树中的一个节点。
对于2-3树中的“3节点”，相当于普通二分搜索树中的两个节点融合在一起，我们如何来描述这种融合在一起的两个节点之间的关系呢？其实很简单，如果我们将连接这两个节点的边涂成红色，就可以表示这两个节点是融合的关系，即2-3树中的一个“3节点”。那么问题又来了，对于树这种数据结构，我们在定义的时候通常都是针对节点进行定义，并没有对节点之间的边进行定义，我们如何来表示这条被涂成红色的边呢？大家都知道，对于树中的任意一个节点，都是只有一个父亲节点，所以与其父节点相连接的边可以用该节点进行表示。那么我们就可以将这两个节点中较小的节点（作为左子树的节点）涂成红色，就可以很好地表示这两个节点融合的关系了。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/2-3树与红黑树-3节点对应.png" alt="img" style="zoom:33%;" />
综合以上描述，2-3树与红黑树之间的关系，我们可以用下图很好地进行表示。我们这里说的红色节点都是向左倾斜的。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/2-3树与红黑树-节点综合.png" alt="img" style="zoom:33%;" />
看过2-3树中的两种节点和红黑树中节点的对应关系后，我们就来看一下一棵2-3树与红黑树之间的对比，如图所示。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/2-3树与红黑树-整体对比.png" alt="img" style="zoom:33%;" />
### 2.14 红黑树
#### 2.14.1 红黑树的性质
1. 每个节点或者是红色，或者是黑色
2. 根节点是黑色
3. 每一个叶子节点(最后的空节点)是黑色的
4. 如果一个节点是红色的，那么它的孩子节点都是黑色的
5. 从任意一个节点到叶子节点，经过的黑色节点是一样的
>1. 每个节点或者是红色，或者是黑色
> 这条定义很好理解，在此不做解释。
>2. 根节点是黑色
> 根据之前说过的，红色的节点对应于2-3树中“3节点”中较小的那个节点，拆成两个“2节点”的话则是一个左子树的节点，即红色的节点总是可以和其父节点进行融合，所以红色节点一定有父节点，显然根节点不能是红色，所以根节点是黑色。
>3. 每一个叶子节点(最后的空节点)是黑色的
> 这条性质和第2条是对应的。对于叶子节点（最后的空节点），一颗空树的根节点也为黑色，所以与其说第三条是一条性质，不如说也是一个定义。
>4. 如果一个节点是红色的，那么它的孩子节点都是黑色的
> 根据上面2-3树与红黑树两种节点的对比图，我们很容易看到，红色节点的两个子树，对应2-3树中的话，要么是一个“2节点”，要么是一个“3节点”，而不管是“2节点”还是“3节点”，相连的第一个节点都是黑色的，所以说红色节点的孩子节点都是黑色的。
>5. 从任意一个节点到叶子节点，经过的黑色节点是一样的
> 根据2-3树与红黑树的关系对比图，可以发现，红黑树中一个黑色节点对应2-3树中一整个节点（“2节点”或“3节点”），而2-3树是完全平衡的树，从根节点到任意路径的叶子节点，经过的节点个数都是相同的，对应红黑树中，即从任意节点到叶子节点，经过的黑色节点是一样的。
#### 2.14.2 红黑树添加元素
回忆刚刚提到的向2-3树中添加元素的过程，或者添加进一个“2节点”，形成一个“3节点”，或者添加进一个“3节点”，形成一个临时的“4节点”。理解了2-3树如何添加节点，对应红黑树就很好理解了。很容易知道，我们总是会将待插入的节点向父节点进行融合，所以我们将待插入的节点看成红色,即永远添加红色节点。
向一棵空树添加节点42。插入后，该节点是根节点，根据红黑树的性质，根节点必须是黑色，所以讲该节点染成黑色。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树添加-根节点.png" alt="img" style="zoom:33%;" />
若向如图的红黑树中添加节点37。因为37比42小，所以添加在42的左子树，对应2-3树中，形成一个“3节点”
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树添加-左子树.png" alt="img" style="zoom:33%;" />
若向如图的红黑树中添加节点42。因为42比37大，所以添加在37的右子树。这样的话红色节点就出现在了一个节点的右子树中，所以此时需要进行左旋转，让树满足红黑树的性质。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树添加-左旋转.png" alt="img" style="zoom:33%;" />
##### 2.14.2.1 左旋转
对于一般的情况，如何进行左旋转呢？我们要对下图的红黑树进行左旋转。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/左旋转-初始.png" alt="img" style="zoom:33%;" />
首先将node节点与x节点断开，其次将x的左子树作为node的右子树。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/左旋转-过程1.png" alt="img" style="zoom:33%;" />
然后再将node作为x新的左子树，之后要把x的颜色染成node的颜色，最后将node的颜色变为红色，这样就完成了左旋转的操作。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/左旋转-过程2.png" alt="img" style="zoom:33%;" />
##### 2.14.2.2 颜色翻转（flipColors）
向红黑树中插入节点66，很容易知道插入到42右子树的位置，对应于2-3树的插入如图所示。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/颜色翻转-1.png" alt="img" style="zoom:33%;" />
然而上面我们说到，我们总是要将新拆分出来的树的父亲节点向上进行融合，即这个父亲节点在红黑树中总是红色的，根据红黑树的性质，该父亲节点的两个孩子节点一定是黑色的。这样就需要将上一步形成的树进行颜色的翻转，变成如下图的形态。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/颜色翻转-2.png" alt="img" style="zoom:33%;" />
##### 2.14.2.3 右旋转
向如图的红黑树中插入节点12，根据二分搜索树插入的操作，此时会形成一条链状的结构，对于2-3树中则是变形成为图中的样子，才能保证平衡性。所以在红黑树中，也要通过变形，变成与2-3树对应的形态。这种情况的变形操作，称为“右旋转”。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/右旋转-1.png" alt="img" style="zoom:33%;" />
一般的情况，右旋转操作同上面的左旋转操作很类似，下面我们一起来看一下过程。我们要对下图的红黑树进行右旋转的操作。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/右旋转一般-初始.png" alt="img" style="zoom:33%;" />
首先将node和x节点断开，将x的右子树T1作为node的左子树。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/右旋转一般-过程1.png" alt="img" style="zoom:33%;" />
其次将node作为x的右子树。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/右旋转一般-过程2.png" alt="img" style="zoom:33%;" />
接着要把x的颜色染成原来node的颜色，把node染成红色。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/右旋转一般-过程3.png" alt="img" style="zoom:33%;" />
然后很显然，需要再进行一次颜色翻转操作，才能满足红黑树的性质。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/右旋转后颜色翻转.png" alt="img" style="zoom:33%;" />
有一种比较复杂的情况，向下图的红黑树中插入节点40,要满足的红黑树的性质我们需要怎么操作呢？
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树插入复杂-1.png" alt="img" style="zoom:33%;" />
对应2-3树中最终的形态，第一步我们可以通过一次左旋转，变成下图的样子。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树插入复杂左旋转.png" alt="img" style="zoom:33%;" />
会发现，这样就变成了上面说到的需要右旋转的形态，所以再进行一次右旋转和颜色翻转，就可以满足红黑树的性质了。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树插入复杂右旋转颜色翻转.png" alt="img" style="zoom:33%;" />
##### 2.14.2.4 红黑树插入总结
上面分情况讨论了向红黑树中添加节点的各种情况，这里总结一下。其实根据上面的讨论，我们可以发现，最后一种复杂的情况可以涵盖其余简单的情况，复杂的操作包含了左旋转、右旋转、颜色翻转，这三种操作，完全可以保持红黑树的性质。下面的一张图，很好的总结了向红黑树中添加节点不同情况下的过程。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树插入总结.png" alt="img" style="zoom:33%;" />
#### 2.14.3 红黑树删除元素
关于红黑树的删除操作，比插入操作要复杂一些，需要分情况进行讨论。下面我们具体来看一下。
红黑树的删除操作大体分为2步：
1. 二分搜索树删除节点
2. 删除修复操作
红黑树的删除首先满足二分搜索树的删除，然后对删除节点后的树进行修复操作，让其重新满足红黑树的5条性质。
对于二分搜索树的删除，这里就不再赘述，我们主要讨论红黑树的删除修复操作。以下所说的当前节点意思是通过二分搜索树的方式删除要删除的节点后，代替原来节点的节点。
当删除节点是红色节点时,那么原来红黑树的性质依旧保持，此时不用做修复操作。
当删除节点是黑色节点时,情况很多，我们分情况讨论。
##### 2.14.3.1 简单情况
1. 当前节点是红色节点
直接把当前节点染成黑色,结束，红黑树的性质全部恢复。
2. 当前节点是黑色节点，并且是根节点
什么都不做，直接结束。
##### 2.14.3.2 复杂情况
###### 1.N、S、SL、SR、P都为黑色
其中N是上述的当前节点，S是N的兄弟节点，P是N的父节点，SL和SR是N兄弟节点的左右孩子节点。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况1-1.png" alt="img" style="zoom:33%;" />
此时将S染成红色，这样经过N路径的黑色节点就和N的兄弟子树中的黑色节点相同了，但是经过P节点的黑色节点少了一个，此时需要将P当做新的N再进行操作，具体怎么操作可以见以下一些情况。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况1-2.png" alt="img" style="zoom:33%;" />
###### 2.N、S、SL、SR为黑，P为红
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况2-1.png" alt="img" style="zoom:33%;" />
此时将P和S的颜色进行交换,P成为了黑色,它为经过节点N的路径添加了一个黑色节点，从而补偿了被删除的黑色节点。S的颜色只是上移到父节点P上,因而经过S节点路径的黑色节点的数目也没有发生改变。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况2-2.png" alt="img" style="zoom:33%;" />
###### 3.N、S为黑色，SR为红色
图中蓝色节点表示该节点可以为黑色也可以为红色，即对该节点的颜色没有要求。
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况3-1.png" alt="img" style="zoom:33%;" />
此时将以P为根的子树进行左旋转
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况3-2.png" alt="img" style="zoom:33%;" />
然后交换P和S的颜色
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况3-3.png" alt="img" style="zoom:33%;" />
将SR染成黑色
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况3-4.png" alt="img" style="zoom:33%;" />
调整后经由N的路径的黑色节点数比调整前增加了一个，恰好补偿了被删除的黑色节点。对于不经过N但经过其他节点的任意一个路径来说，它们贡献的黑色节点数目不变。
###### 4.N、S为黑，SL为红，SR为黑
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况4-1.png" alt="img" style="zoom:33%;" />
此时，将以S为根的子树进行右旋转
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况4-2.png" alt="img" style="zoom:33%;" />
接着交换S和SL的颜色
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况4-3.png" alt="img" style="zoom:33%;" />
节点SL的左孩子在旋转前后不变，而SL原来为红色，所以SL的左孩子必定为黑色。所以旋转后对于N节点来说，相当于情况3。之后再通过情况3中的描述进行操作。整体上情况4需要进行一次右旋转和一次左旋转。
###### 5.N为黑色，S为红色
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况5-1.png" alt="img" style="zoom:33%;" />
此时，将以P为根的子树进行左旋转
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况5-2.png" alt="img" style="zoom:33%;" />
将P和S颜色交换
<img src="https://hexo-rxy.oss-cn-beijing.aliyuncs.com/data_structure/RBTree/红黑树删除情况5-3.png" alt="img" style="zoom:33%;" />
经过这样的变换后，把该情形转化成了N为黑色，其兄弟为黑色的情形，再通过以上描述的几种情况进行变换，最终保持红黑树的性质。
#### 2.14.4 红黑树的性能
红黑树的增删改查的复杂度显然是O(logn)级别的，通常说红黑树是统计性能更优的树结构。
为什么说统计性能更优呢？因为若是单纯的读操作，AVL树的性能比红黑树强一些，红黑树不是严格的平衡树，它是保持“黑平衡”的树。对于红黑树，最坏的情况，是树中最左侧的节点的左子树都是红色的节点，即对应2-3树中的“3节点”，所以这时红黑树的高度就是2logn（除了logn个黑色节点外，还有logn个红色节点），红黑树要比AVL树要高一些。所以从单纯的查询性能来说，红黑树的性能并没有AVL树强。
对于插入删除操作来说，红黑树相比于AVL树减少了左旋转或右旋转的次数，所以红黑树的插入删除的性能比AVL树强一些。
综合增删改查各方面的性能，红黑树的综合性能比较高。
#### 2.14.5 红黑树的应用
1. Java中的TreeMap，Java8中HashMap的TreeNode节点采用了红黑树实现
2. C++中，STL的map和set也应用了红黑树
3. Linux中完全公平调度算法CFS(Completely Fair Schedule)
4. 用红黑树管理进程控制块epoll在内核中的实现，用红黑树管理事件块
5. Nginx中，用红黑树管理timer等