[数据结构与算法] HashMap源码解读

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> HashMap源码解读 -> 正文阅读

[数据结构与算法]HashMap源码解读

本文主要是对JDK1.8的HashMap的主要方法实现做了分析，对于一些基础的知识，认为大家在看这篇文章之前是都懂得的，比如哈希表的原理、红黑树的原理！

如果大家有不了解这些原理的一定要去看看相关文章，否则如果直接看下面的源码的分析肯定有你看不懂的！

数据结构—红黑树(RedBlackTree)的实现原理以及Java代码的完全实现，这是看懂HashMap底层红黑树源码必备的基础知识！

数据结构—散列表(哈希表)的原理以及Java代码的实现，HashMap就是一张散列表，这是关于散列表的介绍！

文章目录
1 HashMap的概述
2 主要类属性
3 主要内部类
3.1 Node
3.2 TreeNode
4 构造器
4.1 HashMap()
4.2 HashMap(initialCapacity)
4.3 HashMap(initialCapacity, loadFactor)
4.4 HashMap(m)
5 put方法
5.1 顶层put方法
5.1.1 hash(key)计算hash值
5.2 putVal插入键值对
5.2.1 计算节点存储位置的哈希算法
5.2.1.1 为什么不直接使用hashCode返回值最终存储位置？
5.2.1.2 为什么hash值的计算需要采用扰动算法，而不是直接用hashcode参与计算？
5.2.1.3. 为什么采用(n-1) & hash计算数组下标？为什么数组容量为2的幂次方？
5.2.2 resize()数组的初始化or扩容
5.2.2.1 数据转移的规律
5.2.2.1.1 特性1
5.2.2.1.2 特性2
5.2.2.1.3 数据转移的规律
5.2.2.1.4 e.hash & oldCap判断高位
5.2.2.2 链表数据转移
5.2.2.3.1 案例详解
5.2.2.3 split()红黑树数据转移
5.2.2.3.1 untreeify树还原
5.2.3 尾插法与并发扩容安全问题
5.2.3.1 尾插法和头插法
5.2.3.2. 并发扩容导致循环链表原理
5.2.3.3 并发扩容导致节点丢失原理
5.2.4 treeifyBin树形化
5.2.4.1 treeify构建红黑树
5.2.4.1.1 比较节点大小
5.2.4.1.1.1 comparableClassFor方法
5.2.4.1.1.2 compareComparables方法
5.2.4.1.1.3 tieBreakOrder方法
5.2.4.1.2 balanceInsertion插入后调整平衡
5.2.4.1.2.1 rotateLeft左旋和rotateRight右旋
5.2.4.1.3 moveRootToFront调整root位置
5.2.4.2 树形化的总结
5.2.5 putTreeVal插入红黑树节点
5.2.5.1 find查找相同节点
5.3. put方法流程图总结
5.3.1 put方法的关键流程图
5.3.2 resize方法关键流程图
6 remove方法
6.1 removeNode移除节点的总方法
6.1.1 removeTreeNode移除红黑树节点的方法
6.1.1.1 balanceDeletion移除后调整平衡
7 其他方法
7.1 get方法
7.2 containsKey方法
7.3 containsValue方法
7.4 putAll方法
7.5 clear方法
7.6 遍历的方法
8 Hashmap 在JDK1.7和1.8的某些区别
8.1 数据结构
8.2 链表插入数据方式
8.3 扩容机制
8.4 扰动算法
9 总结
1 HashMap的概述
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

HashMap，来自于JDK1.2的哈希表的实现，JDK1.8底层是使用数组+链表+红黑树来实现的（JDK1.7是使用数组+链表实现的），使用“链地址法”解决哈希冲突。

实现了Map接口，存放的自然是key-value形式的数据，拥有Map接口的通用操作。允许null键和null值，元素无序。

实现了Cloneable、Serializable标志性接口，支持克隆、序列化操作。

此实现不是同步的，可以使用Collections.synchronizedMap()方法获得一个同步的Map。

默认容量为16，第一次存放元素时初始化；默认加载因子为0.75；扩容增量为增加原容量的1倍，即变成原容量的两倍。

2 主要类属性
主要类属性包括一些默认值常量属性，还有一些关键属性。

从这些属性可知，默认初始容量16，最大容量2^30，加载因子0.75。

链表树形化阈值8（大于），哈希表树形化阈值64（大于等于），resize时树还原阈值6（小于等于）。

/**

默认初始容量为16，所有的容量不许时2的幂次方，这在哈希算法中会使用到。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**

最大容量为1 << 30，即2^30次方。
我们知道int类型的范围是[-2^31 ~ 2^{31-1]，因此这里的2}30实际上就是int范围类的最大的2的幂次方值。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**

默认加载因子为0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**

链表树形化阈值,即链表转成红黑树的阈值，在存储数据时，当链表长度大于8 时，则将链表转换成红黑树。
*/
static final int TREEIFY_THRESHOLD = 8;

/**

红黑树还原为链表的阈值，当在扩容时，resize()方法的split()方法中使用到该字段
在重新计算红黑树的节点存储位置后，当拆分成的红黑树链表内节点数量小于等于6 时，则将红黑树节点链表转换成普通节点链表。
该字段仅仅在split()方法中使用到，在真正的remove删除节点的方法中时没有用到的，实际上在remove方法中，
判断是否需要还原为普通链表的个数不是固定为6的，即有可能即使节点数量小于6个，也不会转换为链表，因此不能使用该变量！
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**

哈希表树形化的最小容量阈值，即当哈希表中的容量大于等于64 时，才允许树形化链表，否则不进行树形化，而是扩容。
*/
static final int MIN_TREEIFY_CAPACITY = 64;

/**

底层存储key-value数据的数组，长度必须是2的幂次方。由于HashMap使用"链地址法"解决哈希冲突，table中的一个节点是链表头节点或者红黑树的根节点。节点类型为Node类型，后面我们会分析到，Node的实际类型可能表示链表节点，也可能是红黑树节点。
*/
transient Node<K, V>[] table;

/**

集合中键值对的数量，可通过size()方法获取。
*/
transient int size;

/**

扩容阈值(容量 x 加载因子)，当哈希表的大小大于等于扩容阈值时，哈希表就会扩容。
*/
int threshold;

/**

哈希表实际的加载因子。
*/
final float loadFactor;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
3 主要内部类
HashMap的内部类比较多，这里讲解主要的内部节点类，一个是Node节点，即普通链表节点；另一个是TreeNode节点类，即红黑树节点。

实际上Node节点直接实现了Map.Entry（Map体系中的集合的内部节点实现类的超级接口），实现了Map.Entry接口的全部方法。而TreeNode直接继承了LinkedHashMap.Entry节点类，而LinkedHashMap类中的节点类Entry则是继承了Node节点类。

虽然它们的关系有点绕，但是TreeNode和Node仍然属于Map.Entry节点体系，并且TreeNode节点类通过LinkedHashMap.Entry间接继承了Node节点类（爷孙关系）。因此底层数组table中的Node的实际类型可能就是链表节点Node，也可能是红黑树节点TreeNode。

3.1 Node
/**

JDK1.8的HashMap的链表节点实现类（JDK 1.7 使用Entry类，只是名字不一样）。
具有hash属性，用于存放key的hashCode方法的返回值，避免重复计算。
具有key、value属性用于存放键值对。
具有next属性，由于HashMap使用"链地址法"解决哈希冲突，因此使用next指向后来加入的存放在同一个桶位置（即哈希冲突）的节点。
实现了Map.Entry（Map体系中的集合的内部节点实现类的超级接口）。
实现了Map.Entry接口的全部方法，比如getKey、getValue、setValue，总之：比较简单。
*/
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;

Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() {
return key;
}

public final V getValue() {
return value;
}

public final String toString() {
return key + “=” + value;
}

public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
3.2 TreeNode
/**
JDK1.8的HashMap的红黑树节点实现类，直接实现了LinkedHashMap.Entry节点类。
具有传统红黑树节点该有的属性，比如两个字节点、父节点、节点颜色等。
具有链表树化的方法和树还原链表的方法，具有查找、存放、移除树节点的方法，具有调整平衡、左旋、右旋的方法，总之：比较复杂。
后面会具体分析它的源码！
*/
static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
//父节点索引
TreeNode<K, V> parent; // red-black tree links
//左子节点索引
TreeNode<K, V> left;
//右子节点索引
TreeNode<K, V> right;
//删除节点是使用到的辅助节点，指向原链表的前一个节点
TreeNode<K, V> prev;
//节点的颜色，默认是红色
boolean red;

/**
- 构造方法，实际上只是调用了父类LinkedHashMap.Entry的构造方法，
- 而在LinkedHashMap.Entry的对应构造方法中，又调用父类Node的构造方法
- @param hash key的hashCode返回值
- @param key k
- @param val v
- @param next 链表的下一个节点引用
  */
  TreeNode(int hash, K key, V val, Node<K, V> next) {
  super(hash, key, val, next);
  }
/**
- 返回包含此节点的树的根节点
  */
  final TreeNode<K, V> root() {
  //……
  }
/**
- 把给定的节点是指为桶的第一个节点，即数组的节点
  */
  static <K, V> void moveRootToFront(Node<K, V>[] tab, TreeNode<K, V> root) {
  //……
  }
/**
- 从当前节点开始通过给定的hash和key查找节点
  */
  final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
  //……
  }
/**
- 从根节点开始通过给定的hash和key查找节点
  */
  final TreeNode<K, V> getTreeNode(int h, Object k) {
  //……
  }
/**
- 比较节点大小，用来排序
  */
  static int tieBreakOrder(Object a, Object b) {
  //……
  }
/**
- 链表树化
  */
  final void treeify(Node<K, V>[] tab) {
  //……
  }
/**
- 红黑树还原为链表，removeTreeNode、split方法中会调用到
  */
  final Node<K, V> untreeify(HashMap<K, V> map) {
  //……
  }
/**
- 存放树节点
  */
  final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab,
  int h, K k, V v) {
  //……
  }
/**
- 删除树节点
  */
  final void removeTreeNode(HashMap<K, V> map, Node<K, V>[] tab,
  boolean movable) {
  //……
  }
/**
- resize时，对红黑树节点的调用方法，包含了untreeify的逻辑
  */
  final void split(HashMap<K, V> map, Node<K, V>[] tab, int index, int bit) {
  //……
  }
/**
- 左旋
  */
  static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root,
  TreeNode<K, V> p) {
  //……
  }
/**
- 右旋
  */
  static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root,
  TreeNode<K, V> p) {
  //……
  }
/**
- 插入后调整平衡
  */
  static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root,
  TreeNode<K, V> x) {
  //……
  }
/**
- 删除后调整平衡
  */
  static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root,
  TreeNode<K, V> x) {
  //……
  }
/**
- 递归不变性检查
  */
  static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
  //……
  }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  4 构造器
  4.1 HashMap()
  public HashMap()

构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。

/**

默认构造函数，可以看到并没有进行底层数组初始化，只是设置了加载因子为默认加载因子，即0.75
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
1
2
3
4
5
6
4.2 HashMap(initialCapacity)
public HashMap(int initialCapacity)

构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。如果初始容量为负，则抛出IllegalArgumentException异常。

public HashMap(int initialCapacity) {
//内部调用指定容量大小和默认加载因子0.75的构造函数
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
1
2
3
4
4.3 HashMap(initialCapacity, loadFactor)
public HashMap(int initialCapacity,float loadFactor)

构造一个带指定初始容量和加载因子的空 HashMap。如果初始容量为负或者加载因子为非正，则抛出IllegalArgumentException异常。

注意，加载因子可以大于1。

/**

构造一个带指定初始容量和加载因子的空 HashMap。
如果初始容量为负或者加载因子为非正，则抛出IllegalArgumentException异常。
*/
public HashMap(int initialCapacity, float loadFactor) {
/1 参数检测/
// 如果指定的初始容量小于0,那么抛出IllegalArgumentException异常
// 指定初始容量必须非负数，否则报错
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);

// 如果指定的初始容量如果大于最大容量，那么初始容量等于最大容量
// 即HashMap的最大容量只能是MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;

// 如果加载因子小于等于0或者不是一个数值类型，那么抛出IllegalArgumentException异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);

/2 初始化参数/
/到这一步，说明上面的检测全部通过/
// 设置实际加载因子
this.loadFactor = loadFactor;

// 设置“扩容阈值”。注意这里设置的值并不是真正的阈值，因为我们说过容量只能是2的幂次方，因此需要先确保容量是2的幂次方才行
// 这里的tableSizeFor方法仅仅只是将传入的容量转化为大于等于该容量的最小2的幂次方，然后赋值给threshold这个变量临时存储真正的初始容量，而真正的阈值在后面还会重新计算
/2.1 设置真正的初始容量/
this.threshold = tableSizeFor(initialCapacity);
}

/**

2.1 tableSizeFor(initialCapacity)，类似于JDK 1.7 中 inflateTable()里的 roundUpToPowerOf2(toSize)，或者类似于JDK1.8 ArrayDeque中的allocateElements(numElements)方法
该方法用于将传入的容量转化为大于等于该容量的最小2的幂次方值,即用于计算真正的初始化容量
该算法首先让指定容量cap的二进制的最高位后面的数全部变成了1，
*/
static final int tableSizeFor(int cap) {
// 使用cap-1来计算，是因为下面的5行算法是尝试查找大于数n的最小2的幂次方-1，因此要想查找大于等于cap的最小2的幂次方，只能使用cap-1来进行运算
int n = cap - 1;
//使用无符号右移和位或操作，尝试将n的最高位1的所有低位全部都变成1，即变成了一个奇数。
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//上面的算法看起来很完美,但是实际上还是有两个局限性的：
//1 如果cap=0，那么经过上面的算法计算出来的n为-1，小于了0
//2 如果cap> (1<<30) ，那么经过上面的算法计算出来的n为2147483647，即int最大值，大于了最大容量
//因此还需要下面的3个判断：
//1如果n小于0，即如果cap传入0，那么n=0-1=-1，那么返回初始容量1
//2否则，如果n大于等于最大容量,那么就返回最大容量；
//3否则，由于此时n为(大于原n的最小2的幂次方-1)，n+1之后正好是大于等于cap的最小2的幂次方，返回n+1。
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
关于上面tableSizeFor的算法更详细解释，我在这篇文章的“ArrayDeque(int numElements)”部份有解释：Java集合—ArrayDeque的源码深度解析以及应用介绍。另外在JDK1.8的Integer类中的highestOneBit方法也使用了类似的算法，不过它是尝试返回小于等于参数的2的幂次方！

4.4 HashMap(m)
public HashMap(Map<? extends K,? extends V> m)

构造包含指定Map的新HashMap。所创建的HashMap具有默认加载因子(0.75)和足以容纳指定 Map 中键值对的初始容量。如果指定的映射为 null，则抛出NullPointerException异常。

/**

构造包含指定Map的新HashMap。
所创建的HashMap具有默认加载因子(0.75)和足以容纳指定 Map 中键值对的初始容量。
*/
public HashMap(Map<? extends K, ? extends V> m) {
//设置加载因子为默认值0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
//1 将传入的子Map中的全部元素逐个添加到HashMap中
putMapEntries(m, false);
}

/**

1 将传入的子Map中的全部元素逐个添加到HashMap中
@param m 被加入的集合
@param evict 在构造器中调用该方法时传入false，其他方法中(比如put、putAll)调用该方法时传入true。实际上在HashMap中没啥用，是留给其子类linkedHashMap用于实现LRU缓存的！
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//s为m的实际元素个数
int s = m.size();
if (s > 0) {
// 判断table是否已经初始化
if (table == null) { // pre-size
// 未初始化，计算初始容量
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 计算得到的t大于阈值，则初始化阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
// 已初始化，并且m元素个数大于阈值，进行扩容处理
else if (s > threshold)
resize();
// 然后,将m中的所有元素循环添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//该方法也是put方法内部调用的方法
putVal(hash(key), key, value, false, evict);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
5 put方法
public V put(K key,V value)

将指定的键值对存入，此集合中。如果该集合以前包含了一个该键的映射关系，则旧值被替换。返回与 key 关联的旧值；如果 key 没有任何映射关系，则返回 null。（返回 null 还可能表示该映射之前将 null 与 key 关联。）

put方法是HashMap的核心方法之一，源码较多，但是如果理解了put方法那么其他方法也就比较简单了！

最顶层的put方法可以分为两步：

hash(key)方法计算key的hash值；
putVal方法存放k-v。
5.1 顶层put方法
/**

put方法开放给外部调用的API
@param key k
@param value v
@return 返回与key关联的旧值；如果key没有任何映射关系，则返回null。（返回 null 还可能表示该映射之前将 null 与 key 关联。）
*/
public V put(K key, V value) {
//内部调用putVal方法，可以看到第一个参数是hash(key)方法的返回值，因此真正的第一步实际上是调用hash(key)方法
return putVal(hash(key), key, value, false, true);
}
1
2
3
4
5
6
7
8
9
10
11
5.1.1 hash(key)计算hash值
hash(key)方法用于计算key的hash值！

/**

JDK1.8获取key的hash值：hashCode() + 1次位运算 + 1次异或运算（2次扰动）
后面（1次位运算 + 1次异或运算）被称作扰动算法，在原hashCode的值上进过了扰动算法，目的是用于降低哈希冲突概率
相比于JDK1.7，扰动算法的代码更简单，但是原理不变
@param key k
@return key的hash值
*/
static final int hash(Object key) {
int h;
//1次>>>运算 + 1次^运算（2次扰动）；如果key==null则直接返回0
//这里我们能够知道，对于key为null的元素hash始终返回0，后面还会知道实际上key为null的元素被始终固定存储到数组0索引的位置
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**

JDK 1.7.0_79获取key的hash值：hashCode() + 4次位运算 + 5次异或运算（9次扰动）
@param k k
@return key的hash值
*/
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
//4次位运算 + 5次异或运算（9次扰动）
h ^= k.hashCode();
//扰动算法
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
5.2 putVal插入键值对
putVal方法用于存放key-value，但实际上它的内部做了很多事，又可以分为几步：

判断如果table数组为null或者长度为0，则初始化数组；
计算新节点存放位置i（哈希算法），并且判断该位置是否发生哈希冲突；
如果没有哈希冲突，创建新普通节点存放在该索引位置处；
如果有哈希冲突，设置变量e默认为null，并进行下面的操作：
首先判断table[i]处的key是否与需插入的key相等，相等则e记录该节点；
否则，判断该位置的节点是否是红黑树节点类型，如果是那么调用putTreeVal进行红黑树节点的添加或者替换。返回需要被替换的节点或者null（表示已添加），使用变量e记录返回值；
否则，循环链表。查找是否有key与需插入的key相等，有则e记录该节点，结束循环；否则在链表尾部插入新节点（尾插法），然后判断链表长度是否大于8，如果是那么将该链表树形化，结束循环；
经过上面的三个判断之一之后，统一判断e是否不为null，如果是，说明需要进行节点value的替换，则对节点e的value进行替换，并且返回旧的value，putVal方法结束；
走到这一步，说明是新加了节点。那么判断如果**++size大于扩容阈值threshold则调用resize方法进行扩容，putVal方法结束；否则不需要扩容，putVal方法结束！
/

存放键值对的方法，HashMap的核心方法之一
@param hash key的hash值
@param key 需要插入的key
@param value 需要插入的值
@param onlyIfAbsent 如果为true，并且传入的key已经存在，并且旧的value不为null，那么不进行value替换，返回旧的value。如果不存在key，就添加key和value，返回null。在JDK1.8的新方法putIfAbsent、中,传入true；

                如果为false，并且传入的key已经存在，那么进行value替换，并返回旧的value。如果不存在key，就添加key和value，返回null；

@param evict 在构造器中调用该方法时传入false，其他方法中(比如put、putAll)调用该方法时传入true。

                实际上该参数在HashMap中没啥用，是留给其子类linkedHashMap用于实现LRU缓存的！

@return 旧值，如果没有则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
/1 首先判断如果table数组为null或者长度为0 则通过resize()初始化数组/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*2 计算新元素应该存放的位置通过(n - 1) & hash 计算得来，并且判断该位置是否为null，即判断是否发生哈希冲突。
- 2.1 如果为null说明没有哈希冲突，那么调用newNode方法创建普通节点，存放在该索引位置处
- */
  if ((p = tab[i = (n - 1) & hash]) == null)
  tab[i] = newNode(hash, key, value, null);
  else {
  /2.2 如果不为null，那么说明这里已经有元素了，发生了哈希冲突，开始解决冲突/
  Node<K, V> e;
  K k;
  /*判断 table[i]位置的元素的key是否与需插入的key相等
  - 通过（hashcode的返回值hash）&&（== || equals）来判断，这说明要求两个key的hashCode相等并且两个key==或者equals方法返回true 才能算是两个key相等
  - */
    /2.2.1 如果两个key相等，那么先用e展示保存p的引用，后续代码会直接替换value/
    if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;
    /2.2.2 如果两个key不相等，那么再判断该数组索引的元素是否是红黑树节点类型，若是，则直接在树中使用putTreeVal 插入 or 更新键值对/
    else if (p instanceof TreeNode)
    //若数组索引的元素是否是红黑树节点类型，则直接在树中使用putTreeVal 插入 or 更新键值对
    //如果是需要更新键值对,则返回需要更新的节点,如果是插入新节点,那么返回null,使用e保存返回值
    e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
    else {
    /*2.2.3 否则，两个key既不相等，也不是红黑树节点类型，那么只能是链表类型
    - 遍历table[i]处的链表，判断Key是否已存在，同样采用上面的方式判断
    - 如果已存在，则结束遍历，在后续代码中直接用新value 覆盖旧value
    - 如果遍历完毕后，发现不存在，则直接在链表尾部插入数据（尾插法）
    - 新增节点后，需判断链表长度是否>8，如果是，则把链表转换为红黑树
    - */
      /循环链表/
      for (int binCount = 0; ; ++binCount) {
      // 若e=p.next并且为null，表示已到链表尾部，此时还没有找到key值相同节点，则说明此联表并不存在相同的key的节点
      // JDK 1.7的HashMap以及JDK1.8的Hashtable是从链表头插入，即新节点永远都是添加到数组的位置，原来数组位置的节点成为新节点的next节点（头插法）
      if ((e = p.next) == null) {
      // 此时使用newNode新建链表节点，然后插入节点到链表尾部（尾插法）
      p.next = newNode(hash, key, value, null);
      //新增节点后，需判断链表长度是否大于等于(8-1)，如果是，则把链表转换为红黑树
      //因此实际上是插入节点后如果链表长度大于8，则转换为红黑树，等于8的时候是不会树化的！
      //那么有可能出现链表长度大于8但是还没有树形化的情况吗?
      //实际上是存在的，在remove某些节点之时，红黑树可能会转换为链表，此时节点数量可能会等于9，但此时属于普通链表.在后面的remove方法中会讲到!
      if (binCount >= TREEIFY_THRESHOLD - 1)
      //树形化的方法，在该方法里面还会判断，即当哈希表中的容量大于等于64 时，才允许树形化链表，否则不进行树形化，而是扩容。
      treeifyBin(tab, hash);
      //结束循环
      break;
      }
      //如果在链表中找到了key相同的节点，那么直接结束遍历，在后续代码中直接用新value 覆盖旧value
      if (e.hash == hash &&
      ((k = e.key) == key || (key != null && key.equals(k))))
      break;
      //p保存e的引用
      p = e;
      }
      }
      //如果e不为null，说明此时找到了key相同的节点,需要进行value的替换
      if (e != null) {
      V oldValue = e.value;
      //如果（onlyIfAbsent为true，并且传入的key已经存在，并且旧的value不为null），那么不进行替换，返回旧的value。
      if (!onlyIfAbsent || oldValue == null)
      //用新值替换旧值
      e.value = value;
      // 当一个节点被访问时，会调用该方法，因此算作会调用方法。
      // 这个方法在HashMap是空实现，实际上是留给其子类linkedHashMap用来实现LRU缓存的。
      afterNodeAccess(e);
      //返回旧值,到此替换value的情况结束,方法结束
      return oldValue;
      }
      }
      /走到这里,说明是新建的节点/
      // 此时结构改变次数自增1
      ++modCount;
      /如果添加节点后size+1大于扩容阈值，开始调用resize方法扩容/
      if (++size > threshold)
      resize();
      //插入元素之后会调用的回调方法
      //这个方法在HashMap同样是是空实现，实际上是留给其子类linkedHashMap用来实现LRU缓存的。
      //在构造器中evict会传递false，其他方法中会传递true
      afterNodeInsertion(evict);
      //返回null
      return null;
      }

/**

创建普通节点
*/
Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
return new Node<>(hash, key, value, next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
下面对以上步骤的重点内容进行说明！

5.2.1 计算节点存储位置的哈希算法
新节点的最终位置是通过：(n - 1) & hash 计算出来的，其中的n表示数组的容量，hash是最开始计算出来的key的hash值。

前面我们知道，对于key为null的元素hash始终返回0，那么实际上key为null的元素被固定存储到数组0索引的位置。因为(n-1)&hash同样始终返回0。

这里有几个问题：

5.2.1.1 为什么不直接使用hashCode返回值最终存储位置？
因为hashCode的大小是不固定的，容易超过数组索引的范围。因此HashMap使用 (n-1) & hash 来确保最终的位置是处于索引范围之内的。

为什么(n-1) & hash 能确保最终的位置是出于索引范围之内，可以看第三个问题！

5.2.1.2 为什么hash值的计算需要采用扰动算法，而不是直接用hashcode参与计算？
因为通常声明Map集合时不会指定大小，并且Map集合的容量并不会很大，而一个1000000000000000，的二进制数的大小为32768，实际上很少有这么大容量的Map。所以在容量比较小的时候，比如容量n为32，那么n-1的二进制就是0001 1111，从第六位开始它的高位实际上全是0，我们知道0&（1或0）的结果都是0，因此实际上只有hashcode的低位能够参与有效的&运算。

我们知道上面的扰动算法是hashcode ^ (hashcode>>>16)。这里的>>>是无符号右移运算符。我们将hashcode右移是16位，即将高16位移动到了低位16位,然后再与自身^运算。这样最终的结果的高16位不变，但是低16位是原来的高16位和低16位进行 ^ 运算之后得出来的值，这样实际上在最终计算存储位置时，该hashcode的高位也参与了每一次的运算过程。

因为有可能两个key的hashcode的低位是一样的，但是高位不一样，通过扰动算法之后，低位会变得不一样，这样计算出来的最终位置也是不一样的，减少了碰撞率。

5.2.1.3. 为什么采用(n-1) & hash计算数组下标？为什么数组容量为2的幂次方？
上面讲到，我们需要将最终计算出的下标固定在数组的索引范围之内，此时我们想到的肯定有取模（求余）算法，即hash % n，由小学数学可知：余数一定会比除数小。此时可保证最终结果固定在[-(n-1),n-1]的范围类，然后再取绝对值，由于计算量不大，这也是很常用的一种哈希算法。

而对于hash % n，就算n不是2的幂次方也能得出正确的范围，那么这里为什么需要n（数组容量）一定是2的幂次方呢？

实际上在hash % n的运算中，如果n为2的幂次方，hash为正数，那么hash % n等价于hash & (n-1)。而因为&属于位运算，位运算直接对内存数据进行操作，不需要像取模运算一样转成十进制，因此处理速度快，效率更高，当n是2的幂次方时，hash % n可以使用hash & (n-1)代替，并且&运算能够保证最终结果处于[0,n-1]之间，也不需要后续的处理，这样提高了哈希算法的效率！如果n不是2的幂次方，就不能转换为(n-1) & hash，虽然仍然能够得到正确的结果，但必须使用十进制%计算，然后再处理结果，效率却没有位运算的效率高！

另外，使用&能够保证得到的结果永远在[0,n-1]的范围之内，而是用%则不一定，使用%运算之后还需要取绝对值等处理，使用&就不需要了。

更深层次的原因，在hash % n的运算中，如果n为奇数，那么计算得到的余数结果将会分布的更加均匀（https://blog.csdn.net/lpf463061655/article/details/85130872）。

5.2.2 resize()数组的初始化or扩容
从源码中，我们知道数组（哈希表）的初始化和扩容使用的是同一个方法：resize()，这个方法既支持初始化还支持扩容！

resize方法同样很复杂，可以大概分为如下几步：

如果老容量大于0，即已经初始化了哈希表，那么可能需要扩容：
如果老容量oldCap大于等于最大容量，则不再扩容，直接返回旧数组，resize方法结束。
如果老容量小于最大容量，则需要扩容，计算扩容新容量newCap和新阈值newThr；
如果老容量等于0，即没有初始化哈希表，计算初始化新容量newCap和新阈值newThr；
建立新数组newTab，容量为新容量newCap，将table引用指向新数组。这个newCap可能是初始化容量也可能是扩容新容量；
如果旧数组oldTab有数据，那么转移旧数组的数据到新数组newTab；
返回新数组，resize方法结束。
/**

resize方法可用于：
1 初始化哈希表;
2 扩容;
*/
final Node<K, V>[] resize() {
// 获取旧数组
Node<K, V>[] oldTab = table;
//获取数组的容量（长度），如果老的数组为空，老的数组容量设为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取老的扩容阈值
int oldThr = threshold;
int newCap, newThr = 0;

/1 如果老容量大于0，即已经初始化了哈希表那么需要扩容/
if (oldCap > 0) {
/1.1 如果老容量大于等于最大容量，则不再扩容/
if (oldCap >= MAXIMUM_CAPACITY) {
// 设置容量阈值为int类型最大值，
threshold = Integer.MAX_VALUE;
//直接返回旧的数组,即不进行扩容。
return oldTab;
}
/1.2 如果老容量小于最大容量，则需要扩容/
// 首先计算新容量、新阈值
// 新容量尝试扩容为老容量的2倍： newCap = oldCap << 1
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {
// 如果新容量小于最大容量，并且老容量大于等于默认容量，那么新阈值也尝试直接扩容为旧阈值的2倍：newThr = oldThr << 1
newThr = oldThr << 1;
}
}
/2 否则，如果旧阈值大于0，即没有初始化哈希表那么需要初始化/
/*这是采用HashMap(int initialCapacity)、HashMap( initialCapacity, loadFactor)这两个构造器创建Map对象，但是还没有添加数据时，出现的情况。
- 在那些构造器中，有这样的设置threshold = tableSizeFor(initialCapacity); 即将实际初始容量值赋给了扩容阈值，因此数组一定为null，扩容阈值一定大于0。
- /
  else if (oldThr > 0) {
  // 第一次初始化哈希表，新容量newCap就设置为老的阈值
  // 新阈值newThr还是0，这里没计算，在后面会计算
  newCap = oldThr;
  }
  /
- 3 否则，那就是oldThr等于0，oldCap等于0。实际上就是采用无参构造器 HashMap() 创建Map对象，但是还没有添加数据时，出现的情况。
- 在无参构造器中，仅仅设置默认加载因子，oldThr还是为0，oldTab还是为null。
- 此时还是属于没有初始化哈希表的情况那么需要初始化
- */
  else {
  //容量和阈值都直接初始化为默认值
  newCap = DEFAULT_INITIAL_CAPACITY;
  newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  /*4 在上面的三种情况中走完之后，如果新阈值newThr还是等于0，那说明有情况2和还有情况1的newCap >=MAXIMUM_CAPACITY 或者 oldCap < DEFAULT_INITIAL_CAPACITY 的时候都会走到这一步
- 现在计算新的阈值newThr
- /
  if (newThr == 0) {
  //计算出新容量加载因子的值ft，注意在构造器源码中我们知道加载因子loadFactor可以大于1，因此ft明显可能大于MAXIMUM_CAPACITY
  float ft = (float) newCap * loadFactor;
  //1 如果新容量小于MAXIMUM_CAPACITY并且新阈值小于MAXIMUM_CAPACITY，那么新阈值newThr就等于计算出的ft值
  //2 否则，此时有可能是1 新容量等于最大容量，2 新阈值大于等于最大容量，这两种情况,数组都不能再扩容了。
  // 此时直接设置newThr为Integer.MAX_VALUE，即变成1.1的情况。
  // 比如使用构造器HashMap( 1, Integer.MAX_VALUE)，就会出现这种情况，这种情况可能会造成大量的哈希冲突，
  // 上面的构造器的构造的Map底层数组容量一直是1，后续的数据将一直挂在table[0]的位置处，即一直冲突。
  newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
  (int) ft : Integer.MAX_VALUE);
  }
  // 将阈值设置为新阈值
  threshold = newThr;
  /*5 建立新数组
- 到这里才算真正开始初始化 or 扩容，前面的都是辅助计算*/
  /新建一个Node数组newTab，容量为前面计算出的newCap，这个newCap可能是初始化容量也可能是扩容新容量/
  Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
  //newTab赋值给table,这样底层table数组变成了新数组,然后还需要数据的转移
  table = newTab;
  /*6 转移旧数组的数据
- 如果原来的table不等于null，尝试将老table的数据转移到新的table中，即扩容后转移数据
- */
  if (oldTab != null) {
  //从0索引开始，循环整个数组，把每个bucket的元素都移动到新的buckets中；将非空元素进行复制；
  for (int j = 0; j < oldCap; ++j) {
  Node<K, V> e;
  /获取数组的第j个元素，使用变量e来保存/
  /如果e不为null,说明这个桶位存在至少一个元素,然后开始处理/
  if ((e = oldTab[j]) != null) {
  //将旧数组该位置置空
  oldTab[j] = null;
  /6.1 如果e.next为null,说明e是这个桶位的唯一一个元素,即该位置没有哈希冲突，转移这一个元素/
  if (e.next == null) {
  //此时直接再次使用哈希算法计算出该元素在新数组的桶位，然后插入即可
  newTab[e.hash & (newCap - 1)] = e;
  }
  /6.2 否则，如果e属于TreeNode，即红黑树节点类型，那么说明该处桶位是一颗红黑树，并且有较严重的哈希冲突，开始进行红黑树节点的转移/
  else if (e instanceof TreeNode) {
  //调用split方法，将红黑树节点也转移到新数组中，split方法中具有将红黑树还原为链表的方法
  ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
  }
  /6.3 否则，那么此处桶位肯定存在一张链表，并且有哈希冲突。且具有2-8个元素，开始进行链表节点的转移/
  else {
  /*6.3.1 通过规律找出链表中需要移动索引和不需要移动索引的元素 */
  //存放不需要移动索引位置的链表的头、尾节点
  Node<K, V> loHead = null, loTail = null;
  //存放需要移动索引位置的链表的头、尾节点
  Node<K, V> hiHead = null, hiTail = null;
  Node<K, V> next;
  /do while循环旧链表/
  do {
  //获取下一个节点
  next = e.next;
  /e.hash & oldCap用于比较元素是否需要移动,即比较高一位是否是1还是0,1就需要移动,0则不需要这是一个规律,具体怎么得到的,后面的说明中详细讲解/
  /e.hash & oldCap 的结果如果等于0，说明下面是对不需要移动索引位置元素的处理/
  if ((e.hash & oldCap) == 0) {
  if (loTail == null)
  //第一次进入外层if时，loTail == null为true，因此loHead = e
  loHead = e;
  else
  //后续进入外层if时，loTail == null为false，因此loTail.next=e，相当于记录一个链表
  loTail.next = e;
  //每次进入外层if时，将loTail指向e，这样除了第一次之外，其他时候进入时loTail都不为null。
  loTail = e;
  }
  /e.hash & oldCap 的结果如果不等于0，说明下面是对需要移动索引位置元素的处理/
  else {
  //第一次进入外层else时，hiTail == null为true，因此hiHead = e
  if (hiTail == null)
  hiHead = e;
  else
  //后续进入外层else时，hiTail == null为false，因此hiTail.next=e，相当于记录一个链表
  hiTail.next = e;
  //每次进入外层else时，将hiTail指向e，这样除了第一次之外，其他时候进入时hiTail都不为null。
  hiTail = e;
  }
  //如果e的next不为null,说明链表还没遍历到尾部，继续循环遍历
  } while ((e = next) != null);
  /*6.3.2 将上面找到的两张旧链表迁移到新数组的对应索引位置中 */
  /如果loTail不为null，说明if代码块至少进入了一次，或者说明不需要移动索引位置的链表有数据/
  if (loTail != null) {
  //到这里loTail.next实际上可能还会指向其他元素,因此将loTail.next 置为 null
  loTail.next = null;
  //直接将不需要移动索引位置的节点放到新数组的原索引位置处
  newTab[j] = loHead;
  }
  /如果hiTail不为null，说明else代码块至少进入了一次，或者说明需要移动索引位置的链表有数据/
  if (hiTail != null) {
  //到这里hiTail.next实际上可能还会指向其他元素,因此将hiTail.next 置为 null
  hiTail.next = null;
  //直接将需要移动索引位置的节点放到新数组的(原索引+oldCap)索引位置处
  newTab[j + oldCap] = hiHead;
  }
  }
  }
  }
  }
  /7 返回新数组/
  return newTab;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  5.2.2.1 数据转移的规律
  5.2.2.1.1 特性1
  如果oldCap为2的幂次方，设e.hash & (oldCap-1) 哈希算法得到的值转换为二进制补码为a，oldCap直接转换为二进制补码为b，那么有这样的特性：
  b的最高位1及其上面的位数在a中对应的位数全部是0。

案例：

设e.hash的二进制补码为：0110 0001 0100 0100 0111 0101 1100 1010。设oldCap为16，那么oldCap二进制补码为：0000 0000 0000 0000 0000 0000 0001 0000。oldCap-1的二进制补码为：0000 0000 0000 0000 0000 0000 0000 1111。（实际上2n的正整数转换为二进制补码后，补码从右向左的第n+1位为1，其他位数全是0。2n-1转换为二进制补码后，补码从右向左的第1到第n位全为1，其他位数全是0。）

那么e.hash & (oldCap-1)得到的二进制补码为:

0110 0001 0100 0100 0111 0101 1100 1010
0000 0000 0000 0000 0000 0000 0000 1111
——————————————————————
0000 0000 0000 0000 0000 0000 0000 1010
1
2
3
4
计算后的结果a=0000 0000 0000 0000 0000 0000 0000 1010，相比与oldCap直接转换成的二进制补码b=0000 0000 0000 0000 0000 0000 0001 0000，b的最高位1及其上面的位数在a中对应的位数全部是0。

5.2.2.1.2 特性2
如果oldCap为2的幂次方，当容量扩容为两倍之后，newCap的二进制补码相对于oldCap的二进制补码来说，最高位的1左移了一位。

案例：

newCap=32时，它的二进制补码为：0000 0000 0000 0000 0000 0000 0010 0000，相比16的二进制补码，最高位的1确实左移了一位。

5.2.2.1.3 数据转移的规律
有了上面的两个特性，我们可以说，老节点在新数组中的位置计算和在旧数组的位置计算，在二进制下的差别就在于新数组的位置计算中新增了一个的高位参与计算。所以老节点在新数组中的位置和原位置的区别实际上就取决于这个高位的运算结果。

最终的规律是：

如果老节点的hash的对应新增高位是1，那么&之后的高位结果还是1，那么老节点在新数组的位置实际上就是（原索引+oldCap），即原索引加上旧数组容量。
如果老节点的hash的对应新增高位是0，那么&之后的高位结果变成0，那么老节点在新数组的位置实际上还是原索引位置，即没改变。
总结：旧数组的索引k的节点，在新数组中的位置只能是索引k或者k+oldCap两者中的一个！
案例：

有两个key，k1.hash=0110 0001 0100 0100 0111 0101 1100 1010，k2.hash=0110 0001 0100 0100 0111 0101 1101 1010。oldCap=16，此时计算出来的位置如下：

k1.hash 0110 0001 0100 0100 0111 0101 1100 1010
oldCap-1 0000 0000 0000 0000 0000 0000 0000 1111
——————————————————————————
index1 0000 0000 0000 0000 0000 0000 0000 1010
1
2
3
4
k2

k2.hash 0110 0001 0100 0100 0111 0101 1101 1010
oldCap-1 0000 0000 0000 0000 0000 0000 0000 1111
——————————————————————————
index2 0000 0000 0000 0000 0000 0000 0000 1010
1
2
3
4
从结果可以看出来，不同的hash计算出来的结果是一样的，即都位于10的位置。假设key不相等，那么这个位置就存放了这两个元素节点。

在扩容之后，newCap=32。此时采用传统方法重新计算位置。计算出来的位置如下：

k1.hash 0110 0001 0100 0100 0111 0101 1100 1010
newCap-1 0000 0000 0000 0000 0000 0000 0001 1111
——————————————————————————
index3 0000 0000 0000 0000 0000 0000 0000 1010
1
2
3
4
k2

k2.hash 0110 0001 0100 0100 0111 0101 1101 1010
newCap-1 0000 0000 0000 0000 0000 0000 0001 1111
——————————————————————————
index4 0000 0000 0000 0000 0000 0000 0001 1010
1
2
3
4
上面的案例也能看出来，我们所说的新增参与计算的一个高位是怎么回事儿了。并且index3=index1，而index4= index2+16。因此我们可以有这样的规律！

5.2.2.1.4 e.hash & oldCap判断高位
有了上面的规律。我们直接判断节点的hash的对应高位是否为0或者1，就能知道这个节点在新数组中的位置，使用这个规律，相比于每次都重新进行哈希算法的计算，提升了效率！

那么，怎么来判断e.hash的新增高位是否是0还是1呢？我们还发现，实际oldCap直接转换为二进制补码之后，它的唯一的那个1正好对应着e.hash新增的高位，并且其他位数全是0。

那么，我们可以直接使用e.hash & oldCap的方式判断高位（注意区别存放数据时计算数组下标的e.hash&(cap-1)），由于oldCap除了高位1之外，其他位全是0，那么最终的值就取决于e.hash的对应新增高位的值了：

如果最终值等于0，那么说明e.hash的对应新增高位为0，该数据就存储在新数组的原索引处；
否则说明e.hash的对应高位为1，该数据就存储在新数组的原索引+oldCap的索引位置处；
案例，oldCap为16：
k1

k1.hash 0110 0001 0100 0100 0111 0101 1100 1010
oldCap 0000 0000 0000 0000 0000 0000 0001 0000
——————————————————————
result1 0000 0000 0000 0000 0000 0000 0000 0000
1
2
3
4
k2

k2.hash 0110 0001 0100 0100 0111 0101 1101 1010
oldCap 0000 0000 0000 0000 0000 0000 0001 0000
——————————————————————
result2 0000 0000 0000 0000 0000 0000 0001 0000
1
2
3
4
我们看到，k1、k2和oldCap进行&运算之后的result1等于0，而result2不等于0，因此k1被存放到新数组的原索引位置，k2被存放到新数组的原索引+oldCap位置。

总结接下，首先判断节点的e.hash & oldCap的值是否等于0，来判断新增参与计算的高位是0还是1，进而直接判断该节点在新数组的索引位置是原索引+oldCap还是原索引。

即，判断

JDK1.8使用上面的规律来计算同一个桶位置的节点新位置的方法，相对于JDK1.7的对每个元素重新使用哈希算法【hashCode()–> 扰动处理 -->hash & (length-1)】来获取新位置的方法，代码简单了不少，同时提升了效率。

并且JDK1.8中旧链表节点迁移到新数组之后，在原同一张链表中的元素相对位置无变化；在JDK在1.7中，旧链表节点迁移到新数组之后，在原同一张链表中的元素相对位置变成了倒置；

5.2.2.2 链表数据转移
上面讲了数据转移的规律，现在来看看JDK1.8的HashMap是如何利用这个规律来快速转移链表数据的，转移链表数据大概分为两步：

将老索引位置k的全部节点，拆分成不需要移动索引位置和需要移动索引位置的两条链表；
将这两条链表头节点分别赋值给新数组的k和k+oldCap索引位置处，转移结束！
两张链表的构建在源码中是这么写：

//存放不需要移动索引位置的节点
Node<K, V> loHead = null, loTail = null;
//存放需要移动索引位置的节点
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
/do while循环旧链表/
do {
//获取下一个节点
next = e.next;
/e.hash & oldCap用于比较元素是否需要移动,即比较高一位是否是1还是0,1就需要移动,0则不需要这是一个规律,具体怎么得到的,后面的说明中详细讲解/
/e.hash & oldCap 的结果如果等于0，说明下面是对不需要移动索引位置元素的处理/
if ((e.hash & oldCap) == 0) {
if (loTail == null)
//第一次进入外层if时，loTail == null为true，因此loHead = e
loHead = e;
else
//后续进入外层if时，loTail == null为false，因此loTail.next=e，相当于记录一个链表
loTail.next = e;
//每次进入外层if时，将loTail指向e，这样除了第一次之外，其他时候进入时loTail都不为null。
loTail = e;
}
/e.hash & oldCap 的结果如果不等于0，说明下面是对需要移动索引位置元素的处理/
else {
//第一次进入外层else时，hiTail == null为true，因此hiHead = e
if (hiTail == null)
hiHead = e;
else
//后续进入外层else时，hiTail == null为false，因此hiTail.next=e，相当于记录一个链表
hiTail.next = e;
//每次进入外层else时，将hiTail指向e，这样除了第一次之外，其他时候进入时hiTail都不为null。
hiTail = e;
}
//如果e的next不为null,说明链表还没遍历到尾部，继续循环遍历
} while ((e = next) != null);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
5.2.2.3.1 案例详解
上面的代码光说文字肯定有点绕，但是画张图一下就明白了，这两张链表的构建原理是一样的。首先是一张旧的哈希表：

我们以第一个桶位置的链表为案例来讲解！

最开始，e=e1，loHead、loTail、hiHead、hiTail、next都为null。

第1次执行do代码块，e=e1，next= e .next=e2，假设e.hash & oldCap等于0，那么第1次进入第一个if块，由于loTail为null，因此loHead=e，loTail=e，代码结束，此时变量的引用关系为：

执行while条件，e = next为e2，判断e2不为null，那么开始第2次执行do代码块，e=e2，next= e .next=e3，假设e.hash & oldCap不等于0，那么第1次进入第二个if块，由于hiTail为null，因此hiHead=e，hiTail=e，代码结束，此时变量的引用关系为：

执行while条件，e = next为e3，判断e3不为null，那么开始第3次执行do代码块，e=e3，next= e .next=e4，假设e.hash & oldCap不等于0，那么第2次进入第二个if块，由于hiTail不为null，因此hiTail.next = e，hiTail=e，代码结束，此时变量的引用关系为：

执行while条件，e = next为e4，判断e4不为null，那么开始第4次执行do代码块，e=e4，next= e .next=e5，假设e.hash & oldCap等于0，那么第2次进入第一个if块，由于loTail不为null，因此loTail.next = e，loTail=e，代码结束，此时变量的引用关系为：

执行while条件，e = next为e5，判断e5不为null，那么开始第5次执行do代码块，e=e5，next= e .next=e6，假设e.hash & oldCap不等于0，那么第3次进入第二个if块，由于hiTail不为null，因此hiTail.next = e，hiTail=e，代码结束，此时变量的引用关系为：

执行while条件，e = next为e6，判断e6不为null，那么开始第6次执行do代码块，e=e6，next= e .next=null，假设e.hash & oldCap等于0，那么第3次进入第一个if块，由于loTail不为null，因此loTail.next = e，loTail=e，代码结束，此时变量的引用关系为：

执行while条件，e = next为null，那么do while循环结束，最终的引用指向结果为：

最终我们可以看到， loHead指向了不需要移动索引位置的链表节点头部，loTail指向不需要移动索引位置的链表节点尾部；hiHead指向了需要移动索引位置的链表节点头部，hiTail指向需要移动索引位置的链表节点尾部。

但是我们还发现，可能会出现某一张链表的尾节点的next节点不为null，因此还需要进一步处理，对于这个情况的处理，是在第二步插入到新数组时完成的！

插入链表到新数组的源码如下：

/如果loTail不为null，说明if代码块至少进入了一次，或者说明不需要移动索引位置的链表有
数据/
if (loTail != null) {
//到这里loTail.next实际上可能还会指向其他元素,因此将loTail.next 置为 null
loTail.next = null;
//直接将不需要移动索引位置的节点放到新数组的原索引位置处
newTab[j] = loHead;
}
/如果hiTail不为null，说明else代码块至少进入了一次，或者说明需要移动索引位置的链表有数据/
if (hiTail != null) {
//到这里hiTail.next实际上可能还会指向其他元素,因此将hiTail.next 置为 null
hiTail.next = null;
//直接将需要移动索引位置的节点放到新数组的(原索引+oldCap)索引位置处
newTab[j + oldCap] = hiHead;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
JDK1.8中旧链表迁移到新数组，在原同一张链表中的元素相对位置没有变化；在JDK在1.7中，旧链表迁移到新数组，在原同一张链表中的元素相对位置变成了倒置（头插法），下面会详细讲解。

通过数据转移的规律和上面两个步骤，我们在向新数组转移原数组某个桶位置的节点时，直接将这计算出来的链表插入通过规律计算出的新数组对应索引处，方便快捷！

5.2.2.3 split()红黑树数据转移
红黑树的数据节点转移是一个单独的方法：split。它的内部源码起始也比较复杂，但是仍然可以分为两步：

将老索引位置k的全部节点，拆分成不需要移动索引位置和需要移动索引位置的两条链表，并记录两条链表的长度；
将这两条链表分别转移到新数组的k和k+oldCap索引位置处，在这个过程中需要判断两条链表的长度小于等于6就调用“树还原为普通链表”的方法untreeify存储到新位置，否则选择“树形化”的方法treeify形成新的红黑树存储到新位置。
/**

红黑树节点类型的数据转移
@param map 当前hashMap对象
@param tab 新数组
@param index 需要转移的红黑树的位置，旧数组索引
@param bit 旧数组容量
*/
final void split(HashMap<K, V> map, Node<K, V>[] tab, int index, int bit) {
TreeNode<K, V> b = this;
/*1 类似于链表的转移的第一步，将老索引位置的全部节点，拆分成不需要移动索引位置和需要移动索引位置的两条链表；
- 为什么红黑树也能采用这种方法？因为TreeNode间接的继承了Node，自然具有Node的所有属性和方法
- 并且在转换为红黑树或者插入红黑树节点时，实际上TreeNode之间还维护了插入的先后关系的next字段
- */
  //存放不需要移动索引位置的链表的头、尾节点
  TreeNode<K, V> loHead = null, loTail = null;
  //存放需要移动索引位置的链表的头、尾节点
  TreeNode<K, V> hiHead = null, hiTail = null;
  //存放不需要\需要移动索引位置的链表的长度
  int lc = 0, hc = 0;
  //由于TreeNode之间通过next维护了先后顺序,因此同样循环遍历就可以了
  for (TreeNode<K, V> e = b, next; e != null; e = next) {
  next = (TreeNode<K, V>) e.next;
  e.next = null;
  if ((e.hash & bit) == 0) {
  if ((e.prev = loTail) == null)
  loHead = e;
  else
  loTail.next = e;
  loTail = e;
  ++lc;
  } else {
  if ((e.prev = hiTail) == null)
  hiHead = e;
  else
  hiTail.next = e;
  hiTail = e;
  ++hc;
  }
  }
  /2 将上面找到的两张旧链表迁移到新数组的对应索引位置中，相比于链表的迁移更加复杂/
  //判断不需要移动索引位置的链表有数据
  if (loHead != null) {
  //如果不需要移动索引位置的链表长度小于等于UNTREEIFY_THRESHOLD，即小于等于6
  if (lc <= UNTREEIFY_THRESHOLD)
  //那么将loHead链表的红黑树节点转换为链表节点存储
  //树还原为链表，untreeify将返回普通链表头节点
  tab[index] = loHead.untreeify(map);
  else {
  //否则，那么将loHead链表转换为红黑树存储
  tab[index] = loHead;
  if (hiHead != null) // (else is already treeified)
  //树形化。该方法在“树形化treeifyBin方法”部分有源码讲解。
  loHead.treeify(tab);
  }
  }
  //判断需要移动索引位置的链表有数据
  if (hiHead != null) {
  //如果需要移动索引位置的链表长度小于等于UNTREEIFY_THRESHOLD，即小于等于6
  //那么将loHead链表的红黑树节点转换为链表节点存储
  if (hc <= UNTREEIFY_THRESHOLD)
  //树还原为链表，untreeify将返回普通链表头节点
  tab[index + bit] = hiHead.untreeify(map);
  else {
  //否则，那么将loHead链表转换为红黑树存储
  tab[index + bit] = hiHead;
  if (loHead != null)
  //树形化。该方法在“树形化treeifyBin方法”部分有源码讲解。
  hiHead.treeify(tab);
  }
  }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
树形化方法treeify在“treeifyBin树形化”部分有讲解；树还原的方法untreeify下面讲解！

5.2.2.3.1 untreeify树还原
树还原方法untreeify用于将红黑树链表转换为普通节点链表，在删除节点以及树节点转移过程中都可能会调用到。

原理很简单：遍历红黑树节点链表，将每个红黑树节点转换为普通节点，然后保存他们的next引用关系即可。

/**

树还原为普通链表的方法，由红黑树链表头节点调用
@param map 当前Map集合
@return 普通节点链表头节点
*/
final Node<K, V> untreeify(HashMap<K, V> map) {

Node<K, V> hd = null, tl = null;
//循环该红黑树链表，转换为普通节点链表，节点顺序还是原来的顺序
for (Node<K, V> q = this; q != null; q = q.next) {
//将每一个树节点转换为普通节点，主次此事next关系没有记录，在下面会记录
Node<K, V> p = map.replacementNode(q, null);
/类似于转移节点时的链表构造原理/
//首次for循环时，tl为null,将会进入该代码块
if (tl == null)
//红黑树链表头节点作为普通链表头节点
hd = p;
//后续循环时，tl不为null,将会进入该代码块
else
//这里重新关联next关系
tl.next = p;
//tl指向该新节点
tl = p;
}
//普通节点链表头节点
return hd;
}

/**

用于从树节点转换为普通节点
@param p 树节点
@param next next引用
@return 普通节点
*/
Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
//返回新建的普通节点，存入树节点的内容
return new Node<>(p.hash, p.key, p.value, next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
5.2.3 尾插法与并发扩容安全问题
5.2.3.1 尾插法和头插法
JDK1.8的HashMap在插入节点时，采用的“尾插法”，尾插法很好理解，实际上就是将新的节点链接到原链表的尾部，使之成为新的尾节点。而JDK1.8之前的HashMap或者全部版本的Hashtable则是采用的“头插法”，顾名思义，头插法就是将新节点链接到链表头部，使之成为新的头节点。

在扩容转移元素时，JDK1.7的HashMap也是采用的头插法，这样造成了元素的相对位置变成了倒置；而JDK1.8由于采用了计算规律，并且获得的两个链表的元素相对顺序并没有变，也相当于“尾插法”的结果。

采用头插法的思想很简单，那就是后来插入的元素可能会被更大概率的访问到，那么插入的链表头部相比于插入链表尾部，能够节省更多的遍历时间，提升效率。但是后来人们发现，对于HashMap这种非线程安全的集合，在多线程下在扩容时采用头插法可能会构造一个循环链表，在遍历时造成死循环，因此JDK1.8的HashMap改为“尾插法”！

5.2.3.2. 并发扩容导致循环链表原理
在JDK1.7中，由于扩容时使用头插法，在并发时可能会形成循环列表，导致死循环，在JDK1.8中改为尾插法，可以避免这种问题，但是依然避免不了节点丢失等各种安全问题。

先来看看JDK1.7转移数据的源码，大概就是：循环遍历旧数组，然后循环遍历每一个链表，将每个链表节点通过头插法插入到新数组。

下面的源码中有两个关键位置：“关键位置1”和“关键位置2”，后续会用到！

void transfer(Entry[] newTable, boolean rehash) {
//新数组容量
int newCapacity = newTable.length;
//旧数组，将桶为的每一个链表转移到新数组中，注意这里是从链表的头部开始遍历的
for (Entry<K,V> e : table) {
while(null != e) {
//关键位置1
Entry<K,V> next = e.next;
//关键位置2
/hashCode–>扰动算法–>h & (length-1) 计算在新数组中的位置/
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
/这三步，就是头插法的运用,后续的节点将会插入到新数组链表头部/
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
设采用HashMap(2,1)的方式创建了哈希表，并且加入了两个元素e1，e2并且发生了冲突，此时该哈希表的结构如下。注意JDK1.7的HashMap是先通过(size >= threshold) && (null != table[bucketIndex])判断是否需要扩容并且在扩容之后，再添加元素的。

当添加第三个元素e3时，明显size=2等于threshold=2，假设第三个元素同样计算的位置和另两个元素位于同一个桶内，那么需要扩容！

如果此时有两个线程A、B调用put方法，那么它们检测到的结果是都需要扩容，假设他们都执行到了transfer方法。线程A运行到关键位置2时，此时线程A中e=e1，next=e2，然后切换到了线程B，并且将transfer方法执行完毕，假设e1和e2计算出来的在新数组中的位置一样，那么此时的新table数组可能是：

然后又切换到了线程A，注意在transfer方法之前，两个线程自个建立了属于自己线程的新数组，但是内部元素却是两个线程共享的。

此时线程A中e=e1，next=e2。线程A继续执行，e.next=newTable[i]，即e.next=null，然后将newTable[i] = e，即将e1头插法迁移到自己的新数组中，然后e=next，即将e2赋值给e，此时A线程中新数组状态为：

第二次执行while，此时e=e2，由于线程B改变了e1和e2的引用关系，导致next=e。next=e1。同头插法插入e2之后，e=next=e1，此时A线程中新数组状态为：

第三次执行while，此时e=e1，因此还需要循环。此时next=e.next=null。e.next=newTable[i]，即e.next=e2，然后newTable[i] = e，即将e1头插法迁移到自己的新数组中，然后e=next=null，此时A线程中新数组状态为：

第四次，然后e =null，while循环结束，这样形成了循环链表，我们知道在查找元素的时候，需要遍历整个链表，那么如果是循环链表，就没有了尾节点，遍历永远不会结束，造成死循环！

5.2.3.3 并发扩容导致节点丢失原理
同样，由于两个线程都具有自己的新数组，那么在给共享变量table赋值时，会造成两个数组的相互覆盖，这样也能造成数据节点的丢失。在JDK1.8中改为尾插法，可以避免死循环的问题，但是依然避免不了节点丢失的问题。

我们假设e1和e2在新数组的位置不一样，如果线程A执行到关键位置1，就切换到了线程B，此时线程A中e=e1。

线程B将transfer方法执行完毕。然后切换到A线程，继续执行，next = e.next，由于e1和e2的引用关系已被线程B去除了，此时next = e1.next=null，因此transfer方法执行完毕之后，线程B、A中的新数组结果如下：

transfer方法执行完毕之后，紧跟着就是将新数组赋值给共享变量table，如果B先复制，A后赋值，那么A的数组将覆盖B的数组，此时将造成数据节点的丢失！

数据节点丢失的情况，无论是JDK1.7还是JDK1.8的HashMap都不能避免，因此有并发的场景，推荐使用ConcurrentHashMap。

5.2.4 treeifyBin树形化
当添加新节点之后的链表长度大于8，那么将该链表转换为红黑树，使用的就是treeifyBin方法。JDK1.8的HashMap的红黑树最初的由来就是通过该方法构造的！

注意：在该方法里面还会判断当哈希表中的容量大于等于MIN_TREEIFY_CAPACITY，即64 时，才允许树形化链表，否则不进行树形化，而是扩容。

treeifyBin方法可以分为以下几步：

如果旧数组为空，或者容量小于MIN_TREEIFY_CAPACITY，即小于64，那么只是进行数组扩容，方法结束。
否则，可以开始树形化：
循环普通链表，将普通节点链表，转换为红黑树节点链表，顺序还是原来的顺序；
红黑树链表头节点调用treeify方法，由红黑树节点链表构建成为红黑树，方法结束。
/**

当添加新节点之后的链表长度大于8，那么将该链表转换为红黑树，使用的就是treeifyBin方法。
JDK1.8的HashMap的红黑树最初的由来就是通过该方法构造的！
@param tab 旧数组
@param hash key的hash值
*/
final void treeifyBin(Node<K, V>[] tab, int hash) {
int n, index;
Node<K, V> e;
/1 如果旧数组为空,或者容量小于MIN_TREEIFY_CAPACITY,即小于64，那么进行数组扩容/
//从这里可以看出来,想要进行树形化，那么需要某个桶位的链表长度大于8，同时需要数组容量大于等于64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
//扩容一次，方法返回
resize();
}
/2 否则,可以开始树形化/
//计算链表索引位置
else if ((e = tab[index = (n - 1) & hash]) != null) {
//hd保存红黑树链表的头部，tl保存红黑树链表的尾部
TreeNode<K, V> hd = null, tl = null;
/2.1 循环普通链表，将普通节点链表，转换为红黑树节点链表，顺序还是原来的顺序/
do {
//新建红黑树节点，注意这里没有保存了节点之间的next的关系
TreeNode<K, V> p = replacementTreeNode(e, null);
//第一次进入do代码块时，tl为null
if (tl == null)
//hd赋值为p
hd = p;
//后续进入do代码块时，tl不为null
else {
//p的前驱设置为tl，这里保存了节点之间的前驱关系
p.prev = tl;
//tl的后继设置为p，这里保存了节点之间的后继关系
tl.next = p;
}
//每次，tl赋值为p
tl = p;
} while ((e = e.next) != null);
//数组的槽位暂时存入红黑树链表的头节点，后面还会调整为红黑树的根节点（moveRootToFront方法中）
if ((tab[index] = hd) != null)
/2.2 红黑树链表头节点调用treeify方法，由红黑树节点链表构建成为红黑树/
hd.treeify(tab);
}
}

/**

新建红黑树节点，注意这里没有保存了节点之间的next的关系
@param p 链表节点,从头节点开始
@param next 下一个节点引用，为null
@return 红黑树节点，颜色属性red默认是false，即黑色。
*/
TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
下面详细讲解，如何通过红黑树链表构建红黑树的！

5.2.4.1 treeify构建红黑树
这个treeify方法用于将红黑树链表构建成为红黑树，在新增节点树形化以及树节点转移过程中都可能会调用到。大概步骤有如下几步：

遍历红黑树链表，获取每一个红黑树节点：
第一次直接将第一个节点当成红黑树的根节点，后续对每个节点采用排序二叉树的方法，在经过一系列比较大小的方法之后插入到红黑树中；
每次插入完成之后对红黑树调用balanceInsertion方法进行重平衡操作，并获取新的根节点。
遍历链表结束之后（也标志着红黑树转换完毕），调用moveRootToFront方法调整根节点的next和prev引用并设置为对应数组索引位置的节点，即tab[i]=root。
/**

由红黑树节点链表构建成为红黑树
@param tab 旧数组
*/
final void treeify(Node<K, V>[] tab) {
//树根节点
TreeNode<K, V> root = null;
/遍历链表，x指向当前调用节点/
for (TreeNode<K, V> x = this, next; x != null; x = next) {
//next指向下一个节点，一次循环之后x指向next
next = (TreeNode<K, V>) x.next;
//设置当前节点的左右节点为空，在扩容方法那里调用该方法时会用到，
//因为扩容时原红黑树链表节点保存了以前的旧的关系，现在需要重新确定关系，因此先清空旧的关系
x.left = x.right = null;
/1 如果没有根节，那么x成为根节点，在treeifyBin方法中，是由红黑树链表的头节点hd调用的该方法/
if (root == null) {
//根节点的父节点指向null
x.parent = null;
//颜色设置为false，即黑色
x.red = false;
//root指向根节点
root = x;
}
/2 如果有根节点/
else {
K k = x.key;
int h = x.hash;
//key所属类型
Class<?> kc = null;
/从根节点开始遍历红黑树/
for (TreeNode<K, V> p = root; ; ) {
//dir 标识左右，-1表示左侧，1表示右侧
//ph保存当前树节点的hash值
int dir, ph;
//当前树节点key
K pk = p.key;
//如果当前树节点p的hash值大于x节点的hash值
if ((ph = p.hash) > h)
//-1表示x节点会放到当前树节点的左侧
dir = -1;
//否则，如果当前树节点p的hash值小于x节点的hash值
else if (ph < h)
//1表示x节点会放到当前树节点的右侧
dir = 1;
//否则，如果当前树节点p的hash值等于x节点的hash值，那么比较k和pk的大小
//如果x的key的类型kc等于null，那么kc等于comparableClassFor(k)，如果k的类型属于Comparable类型，那么kc不为null，否则kc=null
//由于||运算是短路法运算，因此如果kcnull为真，并且kc = comparableClassFor(k)) == null 也为真，那么||后面的表达式将不会执行，
//此时表示k不属于Comparable类型，然后使用tieBreakOrder比较得出最终结果。
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
//如果kcnull为true，并且kc = comparableClassFor(k)) == null 为false，或者kc==null为false，那么表示k属于Comparable类型，此时前面的表达式为false，
// 那么||后面的表达式将会执行，即使用compareComparables方法比较，compareComparables实际上就是将两个k使用compareTo方法比较
// 如果得到的结果为0，那么表示相等，后面的表达式返回true，此时再通过tieBreakOrder比较一次计算出最终结果
(dir = compareComparables(kc, k, pk)) == 0)
//如果k的类型不是Comparable类型，或者k和pk使用compareComparables比较返回结果为0，那么最终调用tieBreakOrder方法进行比较
//最终比较k和kp大小的方法,实际上是比较k和pk的类名字符串或者比较k和pk的identityHashCode的大小,最后只会返回-1或者1
dir = tieBreakOrder(k, pk);
//使用xp保存当前树节点p
TreeNode<K, V> xp = p;
//如果dir小于等于0，那么x节点一定在当前树节点p的左侧；否则,如果dir 大于0，那么x节点一定在当前树节点p的右侧
//由于仅仅知道x是在p的左侧或者右侧，不知道p是否有左、右子树，如果已经存在了左右子树，那么还需要递归子树，直到查找到对应位置为null，因此还需要判断：
//如果x是在p的左侧，并且当p的左子树为null时，直接使x成为xp的左子节点，x.parent指向xp，然后xp.left指向x
//如果x是在p的右侧，并且当p的右子树为null时，直接使x成为xp的右子节点，x.parent指向xp，然后xp.right指向x
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//上面的插入实际上就是排序二叉树的插入方式,对与红黑树来说，在调用二叉排序树的插入方式成功插入节点之后，可能会破坏红黑树的平衡，因此还需要重平衡操作，
//因此在最后调用balanceInsertion(root, x)方法对红黑树进行重平衡,然后返回平衡之后的新的根节点
root = balanceInsertion(root, x);
//导致成功的插入了红黑树节点，并且调整了平衡，结束该次红黑树的遍历，继续下一个链表节点的插入
break;
}
}
}
}
//将链表完全转换为红黑树之后，红黑树可能经历了多次再平衡，需要将最后的root节点，设置为数组节点，即tab[i]=root
//同时需要调整root放入next和prev的引用指向，将root节点作为链表的头节点
moveRootToFront(tab, root);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
下面针对重要方法进行讲解！

5.2.4.1.1 比较节点大小
由于红黑树属于二叉排序树的一种，因此红黑树的节点之间必须具有大小关系，这样才能构建红黑树。即使HashMap的元素是无序的，即使元素没有实现Comparable接口，在HashMap内部的红黑树中也会采用自己的方法对节点进行比较排序！

5.2.4.1.1.1 comparableClassFor方法
对象x的类型为c，如果对象x实现了Comparable< c >接口，那么返回对象x的类型c，否则返回null。

/**

对象x的类型为c，如果对象x实现了Comparable< c >接口，那么返回对象x的类型c，否则返回null
*/
static Class<?> comparableClassFor(Object x) {
/x是否属于Comparable类型/
if (x instanceof Comparable) {
//如果x属于Comparable类型，还需要进一步判断Comparable接口的泛型类型！
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
//如果x的类型c是String类型，即key为String类型，那么直接返回c。
//因为String类型实现了Comparable接口
if ((c = x.getClass()) == String.class) // bypass checks
return c;
//否则，获取c直接实现的接口类型数组，如果是泛型接口（参数化类型）还会返回泛型的信息，简单的说具有<>符号的接口是参数化类型
if ((ts = c.getGenericInterfaces()) != null) {
//遍历该数组
for (int i = 0; i < ts.length; ++i) {
//(t = ts[i]) instanceof ParameterizedType -->如果t是个泛型接口（参数化类型），
//(p = (ParameterizedType)t).getRawType() == Comparable.class -->如果该接口的类型是Comparable类型
//as = p.getActualTypeArguments()) != null -->如果该接口具有泛型参数
//as.length == 1 -->如果该接口的泛型参数个数为1个
//as[0] == c -->如果该接口的泛型参数类型为c
//如果以上条件全部满足，说明x实现了Comparable接口，并且Comparable接口的泛型参数类型就是x的类型c，那么同样直接返回c
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
//如果x不属于Comparable类型，或者实现Comparable接口的泛型类型不是x的所属类型，那么最终返回null
return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
5.2.4.1.1.2 compareComparables方法
如果kc == null为true，并且kc = comparableClassFor(k)) == null 为false，或者kc==null为false，那么表示kc一定是属于Comparable类型。

此时前面的表达式为false，那么||后面的表达式将会执行，即使用compareComparables方法进一步比较，compareComparables实际上就是将两个k使用compareTo方法比较。

如果x（pk）为null，或者x（pk）的类型不是kc，则返回0；否则返回k.compareTo(x)的比较结果。

/**

如果x为null，或者x的类型不是kc，则返回0；否则返回k.compareTo(x)的比较结果
@param kc x.key的类型，执行到这个方法，kc一定是Comparable类型
@param k x.key
@param x 当前树节点p的key，pk
@return 如果x为空，或者x的类型不是kc，则返回0；否则返回k.compareTo(x)的比较结果
*/
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable) k).compareTo(x));
}
1
2
3
4
5
6
7
8
9
10
11
12
5.2.4.1.1.3 tieBreakOrder方法
如果k的类型不是Comparable类型，或者k和pk使用compareComparables比较返回结果为0，即不具备compareTo比较资格或者compareTo比较之后仍然没有分出大小，那么最终调用tieBreakOrder方法进行比较。

实际上tieBreakOrder方法是比较k和pk的类名字符串或者比较k和pk的identityHashCode的大小,最后只会返回-1或者1。

/**

如果k的类型不是Comparable类型，或者k和pk使用compareComparables比较返回结果为0。
即不具备compareTo比较资格或者compareTo比较之后仍然没有分出大小，那么最终调用tieBreakOrder方法进行比较。
@param a x节点的key，k
@param b 当前树节点的key，pk
@return 只会返回 1 或者 -1
*/
static int tieBreakOrder(Object a, Object b) {
int d;
//a == null --> 如果a等于null
//b == null --> 如果a不等于null，b等于null
//(d = a.getClass().getName().compareTo(b.getClass().getName())) == 0
// -->如果a不等于null，b不等于null,那么比较两个对象的类名字符串，按照字符串的比较方法返回结果d
//如果a不等于null，b不等于null
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
//如果a不等于null，b不等于null，并且a、b类名字符串的比较结果还是返回0
//那么调用identityHashCode方法获取a、b的本地哈希码进行比较，如果a小于等于b则返回-1，否则返回1
//identityHashCode()：即无论对象有没有重写hashcode()方法，都调用Object类的原始hashCode()方法。
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
5.2.4.1.2 balanceInsertion插入后调整平衡
该方法在红黑树节点成功插入之后调用，重新平衡红黑树，用于维持红黑树的性质！

关于插入之后的平衡，有很多种情况，我们只需要根据情况按部就班的采用对应的方法就行了，在红黑树的原理和实现部分已经有了插入平衡的详细讲解，这里不再多说：数据结构—红黑树(RedBlackTree)的实现原理以及Java代码的完全实现。

/**

该方法在红黑树节点成功插入之后调用，重新平衡红黑树，用于维持红黑树的性质！
关于插入之后的平衡，有很多种情况，我们只需要根据情况按部就班的采用对应的方法就行了，
在红黑树的原理和实现部分已经有了插入平衡的详细讲解，实际上不是很复杂的，
这里不再多说，只是将每种情况和红黑树原理那儿的每种情况的简称对应上来，这样就很容易理解了！
同样假设，null节点为黑色节点
@param root 平衡之前的根节点
@param x 新插入的节点
@return 平衡之后的根节点
/
static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x) {
//新插入节点设置为红色
x.red = true;
//xp表示x节点的父节点，xpp表示x节点的祖父节点，xppl表示左叔节点，xppr表示右叔节点
for (TreeNode<K, V> xp, xpp, xppl, xppr; ; ) {
/1 如果新节点的父节点为null，即作为根节点，对应——“新根”的情况/
if ((xp = x.parent) == null) {
//改变颜色即可
x.red = false;
return x;
}
/2 如果父节点为黑色，此时是天然平衡的不需要调整，||后面的操作仅仅是为了给祖父节点赋值，对应——“父黑”的情况！/
else if (!xp.red || (xpp = xp.parent) == null)
return root;
/3 剩下的就是父节点是红色的情况，此时祖父节点肯定存在并且是黑色!这是插入之后最复杂的情况了，需要更加细致的分类讨论/
/ 如果父节点是作为祖父节点的左子节点，即L，那么叔节点肯定是右子节点*/
if (xp == (xppl = xpp.left)) {
/3.1 如果叔节点为红色，很明显，对应——“父红叔红”的情况/
/此时可以将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，
直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。（摘自红黑树实现原理）/
if ((xppr = xpp.right) != null && xppr.red) {
//叔节点涂黑
xppr.red = false;
//父节点涂黑
xp.red = false;
//祖父节点涂红
xpp.red = true;
//祖父节点作为新插入节点，递归操作直到平衡，这里使用的for循环处理，思想很优秀！
x = xpp;
}
/*3.2 如果叔节点为黑色（或者不存在），很明显，对应——“父红叔黑”的情况，在原理部分我们讨论过，需要分四种情况，但是由于父节点在前面确认属于左边，即L，因此有两种情况：
* 1) 在祖父节点G的左孩子节点P的左子树中插入节点N，简称“LL”；
* 2) 在祖父节点G的左孩子节点P的右子树中插入节点N，简称“LR”；
* */
else {
/*3.2.1 如果新插入节点，属于父节点的右子节点，即对应——
* 2) 在祖父节点G的左孩子节点P的右子树中插入节点N，简称“LR”；的情况
* 此时的处理方式是：先将P左旋，实际上是转换为LL的情况，然后将G右旋；然后N涂黑，G涂红。HashMap的处理方法差不多，只是顺序有变。
* */
/首先将LR转换为LL的情况。/
if (x == xp.right) {
//重新为x赋值为xp，这里将P左旋，然后原xp节点成为了原x节点的左子节点，实际上是转换成了LL的情况
root = rotateLeft(root, x = xp);
//重新为xp、xpp赋值
xpp = (xp = x.parent) == null ? null : xp.parent;
}
/3.2.2 这里实际上是处理LL的情况，有可能本来就是LL的情况，也有可能是LR转换为LL的情况，即
* 1) 在祖父节点G的左孩子节点P的左子树中插入节点N，简称“LL”；
* 此时的处理方式是：将G右旋，然后P涂黑，G涂红；
* /
if (xp != null) {
//LL的父节点P涂黑，也对应着LR的N涂黑。
xp.red = false;
//如果祖父节点不为null
if (xpp != null) {
//LL的祖父节点G涂红，实际上对应着LR的G涂红
xpp.red = true;
//最后将G右旋，到此实际上平衡完毕了，但是HashMap没有主动结束，而是继续循环，下一次循环时，将会变成“父黑”的情况，直接结束！
root = rotateRight(root, xpp);
}
}
}
}
/ 如果父节点是作为祖父节点的右子节点，即R，那么叔节点肯定是右子节点/
else {
/3.1 如果叔节点为红色，很明显，对应——“父红叔红”的情况/
/此时可以将父/叔 (P/U) 节点涂黑，祖父节点(G)涂红；而后以祖父节点(G)作为新的平衡节点N，向上递归的执行平衡操作，
直到不再发生两个相连的红色节点或者达到根（它将被重新涂成黑色）为止。（摘自红黑树实现原理）/
if (xppl != null && xppl.red) {
//叔节点涂黑
xppl.red = false;
//父节点涂黑
xp.red = false;
//祖父节点涂红
xpp.red = true;
//祖父节点作为新插入节点，递归操作直到平衡，这里使用的for循环处理，思想很优秀！
x = xpp;
}
/*3.2 如果叔节点为黑色（或者不存在），很明显，对应——“父红叔黑”的情况，在原理部分我们讨论过，需要分四种情况，但是由于父节点在前面确认属于右边，即R，因此有两种情况：
* 3) 在祖父节点G的右孩子节点P的左子树中插入节点N，简称“RL”；
* 4) 在祖父节点G的右孩子节点P的右子树中插入节点N，简称“RR”。
* */
else {
/*3.2.3 如果新插入节点，属于父节点的左子节点，即对应——
* 3) 在祖父节点G的右孩子节点P的左子树中插入节点N，简称“RL”；的情况
* 此时的处理方式是：先将P右旋，实际上是转换为RR的情况，然后将G左旋；然后N涂黑，G涂红。HashMap的处理方法差不多，只是顺序有变。
* */
/首先将RL转换为RR的情况。/
if (x == xp.left) {
//重新为x赋值为xp，这里将P右旋，然后原xp节点成为了原x节点的右子节点，实际上是转换成了RR的情况
root = rotateRight(root, x = xp);
//重新为xp、xpp赋值
xpp = (xp = x.parent) == null ? null : xp.parent;
}
/*3.2.4 这里实际上是处理RR的情况，有可能本来就是RR的情况，也有可能是RL转换为RR的情况，即
* 4) 在祖父节点G的右孩子节点P的右子树中插入节点N，简称“RR”。
* 此时的处理方式是：将G左旋，然后P涂黑，G涂红；
* */
if (xp != null) {
//RR的父节点P涂黑，也对应着RL的N涂黑。
xp.red = false;
//如果祖父节点不为null
if (xpp != null) {
//RR的祖父节点G涂红，实际上对应着RL的G涂红
xpp.red = true;
//最后将G左旋，到此实际上平衡完毕了，但是HashMap没有主动结束，而是继续循环，下一次循环时，将会变成“父黑”的情况，直接结束！
root = rotateLeft(root, xpp);
}
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
5.2.4.1.2.1 rotateLeft左旋和rotateRight右旋
rotateLeft是红黑树左旋的通用方法，用于调整右树失衡的情况；rotateRight是红黑树右旋的通用方法，用于调整左树失衡的情况。

不同红黑树的实现虽然代码可能不一样，但是旋转的原理的都是一样的，红黑树和AVL树的单纯的旋转原理又是一样的，在AVL树原理部分已经有了详细讲解，在此不再赘述：数据结构—平衡二叉树(AVL树)的原理以及Java代码的完全实现。

/**

左旋的方法，和右旋是镜像的，根据红黑树原理，左旋的通解是:
设k1为需要旋转的节点，k2为k1的右子节点，左旋之后，k2成为根节点，k1成为k2的左子节点，k2的左子树2成为k1的右子树
@param root 当前根节点
@param p 需要左旋的节点
@return 新的根节点
*/
static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root, TreeNode<K, V> p) {
TreeNode<K, V> r, pp, rl;
//如果p(k1)以及p的右子节点r(k2)不为null
if (p != null && (r = p.right) != null) {
//如果r(k2)的左子树rl不为null
//同时p(k1)的右子节点设置为r(k2)的左子节点
if ((rl = p.right = r.left) != null)
//那么rl的父节点变成成为p(k1)
rl.parent = p;
//如果pp即p的父节点为null,说明此时p(k1)是根节点,那么旋转之后r(k2)成为根节点
//同时r(k2)的父节点设置为p(k1)的父节点
if ((pp = r.parent = p.parent) == null)
//r赋值给root,并且涂黑
(root = r).red = false;
//否则，如果p(k1)是pp的左子节点
else if (pp.left == p)
//那么r(k2)成为pp的左子节点，即代替了p的位置
pp.left = r;
//否则，r(k2)成为pp的右子节点，即代替了p的位置
else
pp.right = r;
//r(k2)的左子节点变成p(k1)
r.left = p;
//p(k1)的父节点变成r(k2)
p.parent = r;
}
//返回新根节点
return root;
}

/**

右旋的方法，和左旋是镜像的，根据红黑树原理，右旋的通解是:
设k1为需要旋转的节点，k2为k1的左子节点，右旋之后，k2成为根节点，k1成为k2的右子节点，k2的右子树2成为k1的左子树
@param root 当前根节点
@param p 需要右旋的节点
@return 新的根节点
*/
static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root, TreeNode<K, V> p) {
TreeNode<K, V> l, pp, lr;
//如果p(k1)以及p的左子节点l(k2)不为null
if (p != null && (l = p.left) != null) {
//如果l(k2)的右子树lr不为null
//同时p(k1)的左子节点设置为l(k2)的右子节点
if ((lr = p.left = l.right) != null)
//那么lr的父节点变成成为p(k1)
lr.parent = p;
//如果pp即p的父节点为null,说明此时p(k1)是根节点,那么旋转之后l(k2)成为根节点
//同时l(k2)的父节点设置为p(k1)的父节点
if ((pp = l.parent = p.parent) == null)
//l赋值给root,并且涂黑
(root = l).red = false;
//否则，如果p(k1)是pp的右子节点
else if (pp.right == p)
//那么l(k2)成为pp的左子节点，即代替了p的位置
pp.right = l;
//否则，l(k2)成为pp的左子节点，即代替了p的位置
else
pp.left = l;
//l(k2)的左子节点变成p(k1)
l.right = p;
//p(k1)的父节点变成l(k2)
p.parent = l;
}
return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
5.2.4.1.3 moveRootToFront调整root位置
moveRootToFront方法，被用在红黑树完全构建成功之后。

将链表完全转换为红黑树之后，红黑树可能经历了多次再平衡，需要将最后的root节点，设置为数组节点，即tab[i]=root。

另外，我们从treeifyBin方法的源码中能看出来，实际上红黑树是通过红黑树链表构建而来的，而在构建红黑树时，链表节点之间的prev和next关系是没有清除的，因此红黑树的节点之间还保持着链表的next关系。因此还需要调整root的next和prev的引用指向，将root节点作为链表的头节点。

/**

moveRootToFront方法，被用在红黑树完全构建成功之后。
将root节点作为数组桶位节点以及链表头节点
*/
static <K, V> void moveRootToFront(Node<K, V>[] tab, TreeNode<K, V> root) {
int n;
//非空判断
if (root != null && tab != null && (n = tab.length) > 0) {
//计算root节点的槽位，这个槽位就是原红黑树链表的槽位
int index = (n - 1) & root.hash;
//获取该位置的节点，这个节点实际上就是在treeifyBin方法中在调用treeify方法前设置的红黑树链表头节点
TreeNode<K, V> first = (TreeNode<K, V>) tab[index];
/*判断链表头节点是否还作为红黑树的根节点
* 如果root和first不相等，那么需要调整引用关系
* 简单来说就是将，红黑树根节点调整为原链表的头节点，并设置为数组桶位置的节点，大概有三步：
* 1 数组桶位的节点设置为红黑树根节点root
* 2 解除root节点和原红黑树链表节点之间的next和prev关系，root的前驱和后继直接关联
* 3 重新关联root节点和原红黑树链表的关系，将root设置为链表头节点
*
* */
if (root != first) {
Node<K, V> rn;
/1 数组桶位的节点设置为红黑树根节点root/
tab[index] = root;
```
     /*2 解除root节点和原红黑树链表节点之间的next和prev关系，root的前驱和后继直接关联*/
     //获取root的前驱节点rp
     TreeNode<K, V> rp = root.prev;
     //获取root的后继rn并判断是否不为null，不为null就说明root节点不是原链表追后一个节点
     if ((rn = root.next) != null)
         //后继节点rn的前驱节点设置为rp
         ((TreeNode<K, V>) rn).prev = rp;
     //如果rp不为null,那么说明root不是原链表头节点
     if (rp != null)
         //那么前驱节点的后继节点设置为root的后继节点rn
         rp.next = rn;
     //如果first不为null
     if (first != null)
         //那么原链表头节点的前驱设置为红黑树根节点root
         first.prev = root;

     /*3 重新关联root节点和原红黑树链表节点的关系，将root设置为链表头节点*/
     //红黑树根节点root的后继节点设置为原链表头节点first
     root.next = first;
     //红黑树根节点root的前驱设置为null
     root.prev = null;
 }
 // 校验该红黑树结构是否正确
 assert checkInvariants(root);
```
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
5.2.4.2 树形化的总结
通过查看JDK1.8HashMap树形化方法treeifyBin的源码，我们能够发现一些不为人知的细节：

树形化的要求：在外面的方法判断插入节点之后链表长度大于8并调用该方法时，在该方法里面还会判断当前哈希表中的容量大于等于MIN_TREEIFY_CAPACITY（即64）时，才允许树形化链表，否则不进行树形化，而是扩容一次。
树形化过程：普通节点类型链表(节点具有next关系) --> 红黑树节点类型链表(节点具有prev和next关系) --> 红黑树(保留了节点的prev和next关系)
红黑树的根节点最终会作为数组桶位的直达节点，并调整为红黑树链表的头节点。
由此，我们能够画出HashMap树形化的转换流程图：

首先是，链表长度大于8，同时数组容量大于等于64的情况，此时可以转换为红黑树：

然后是，转换为红黑树节点链表，此时全部是默认黑色节点：

然后是，红黑树链表转换为红黑树之后，调整root位置/引用之前的结构，此时数组桶位节点还是原链表头节点：

最后是，调整root位置/引用之后的结构，root变成了链表头节点，以及数组桶位节点。树形化彻底完成：

5.2.5 putTreeVal插入红黑树节点
putTreeVal方法主要有两个作用：

一个是先查找是否具有相同的key的节点，找打就返回该节点，表明需要替换value；
没找到那就是插入新节点了，然后返回null，表示插入了节点。
key相同的的要求是：两个key的hash相同，并且两个key的equals或者==比较返回true。

putTreeVal插入的逻辑和treeify由红黑树链表构建红黑树的方法有些相似，都有寻找位置-插入节点-调整平衡-调整root引用关系的步骤，理解了一个方法另一个方法也就不难理解了。

/**

插入红黑树节点的方法，该方法有一部分和treeify树形化方法相似
该方法由红黑树节点调用
@param map 当前map集合
@param tab 当前集合的table数组
@param h key的hash
@param k key
@param v value

@return 返回需要替换value的树节点，或者在新添加树节点之后返回null
*/
final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab, int h, K k, V v) {
//存储k的class对象
Class<?> kc = null;
// 标识是否已经遍历过一次当前节点。 false表示没有，true 表示已经遍历过
boolean searched = false;
//判断该方法调用节点的父节点是否为null，来获取根节点
TreeNode<K, V> root = (parent != null) ? root() : this;
//从根节点开始遍历红黑树链表，寻找相等的节点
for (TreeNode<K, V> p = root; ; ) {
//dir表示寻找的方向 -1表示左边 1表示右边
//ph用来存储当前节点的hash
int dir, ph;
//用来存储当前节点的key
K pk;
/先比较两个key的hash/
//如果当前节点hash值ph 大于指定key的hash值h
if ((ph = p.hash) > h)
//那么dir=-1 表示新节点应该放在左侧
dir = -1;
//否则，如果当前节点hash值ph 小于指定key的hash值h
else if (ph < h)
//那么dir=1 表示新节点应该放在右侧
dir = 1;
/如果hash相等，然后使用key的equals方法比较/
//否则，如果两个key使用==比较或者使用equals比较返回true，那说明存在相同的key，此时应该进行value的替换
//返回当前节点p，该节点就是需要替换value的节点，这里不进行替换，在putVal方法中进行统一替换
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
/如果equals方法比较返回false，然后尝试将两个key转换为Comparable进行比较/
//否则，通过上面的方法不能分出大小，即key的hash值相等，但是key不相等，那么和treeify树形化方法的比较操作相似
//使用comparableClassFor和compareComparables方法进行比较，实际上是想将两个key转换为Comparable进行比较
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
/如果上面的比较完毕还是到了这一步，说明两个key无法比较（无法转换为Comparable），或者Comparable比较返回0/
/判断searched并尝试搜索该节点的左子树/
//标识是否已经遍历过一次当前节点，如果为true表示遍历过，那么它的子树也肯定遍历过
//如果为false，那么它的子树也肯定没有遍历过，因为是节点的遍历是从上向下遍历的
//那么此时!searched就为true，开始遍历左右子树
if (!searched) {
TreeNode<K, V> q, ch;
//searched设置为true
searched = true;
/可以看到两个表达式中间使用||连接，那么是短路法运算。先是从左子树中尝试查找相等key的节点，如果找到了那么就不找右子树了
如果没找到，那么第一个表达式返回false，那么继续查找右子树，如果在其中一方找到了相同的key，那么返回对应的节点q，
该节点q就是需要替换value的节点，这里不进行替换，在putVal方法中进行统一替换/
if (((ch = p.left) != null &&
//查询左子树
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
//查询右子树
(q = ch.find(h, k, kc)) != null)) {

             return q;
         }
     }
     /*如果上面的遍历了所有子节点也没有找到和当前键equals相等的节点，那么使用tieBreakOrder方法进行最终的比较，
      * 但是这个方法只会返回1或者-1，实际上这已经是在为插入新节点做准备了
      * */
     dir = tieBreakOrder(k, pk);
 }
 /*到这一步，表示该节点以及它的所有子节点都没找到相同的key，那么需要插入新节点*/
 // xp保存当前节点
 TreeNode<K, V> xp = p;
 /*这里就和treeify树形化方法相似了，都是插入节点，这里摘取treeify部分的描述*/
 //如果dir小于等于0，那么x节点一定在当前树节点p的左侧；否则,如果dir 大于0，那么x节点一定在当前树节点p的右侧
 //由于仅仅知道x是在p的左侧或者右侧，不知道p是否有左、右子树，如果已经存在了左右子树，那么还需要递归子树，直到查找到对应位置为null，因此还需要判断：
 //如果x是在p的左侧，并且当p的左子树为null时，直接使x成为xp的左子节点，x.parent指向xp，然后xp.left指向x
 //如果x是在p的右侧，并且当p的右子树为null时，直接使x成为xp的右子节点，x.parent指向xp，然后xp.right指向x
 if ((p = (dir <= 0) ? p.left : p.right) == null) {
     /*如果某个子节点为null，那么在该位置插入新节点作为xp的子节点*/
     //获取xp的的next节点xpn
     Node<K, V> xpn = xp.next;
     //新建红黑树节点x，该节点的next指向xpn
     TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
     //成为xp的左子节点
     if (dir <= 0)
         xp.left = x;
         //成为xp的右子节点
     else
         xp.right = x;
     /*这里是相比于treeify方法多出的部分，由于treeify方法本身就是操作的红黑树链表，他们的节点天然具有next和prev关系
      * 这里插入新的节点和目前的红黑树节点不具有next和prev关系，因此需要维持关系
      * 这里关系的维持方式是：x的父节点xp作为前驱prev，x作为父节点xp的后继next
      * 上面新建节点时则维护了父节点xp的next节点xpn作为新节点x的后继next，这里继续判断如果xpn != null，新节点x作为父节点xp的next节点xpn的前驱prev
      * 总结来说：新插入节点 在红黑树连变化中的位置，是插入到它的父节点和父节点的next节点之间！
      * */
     //xp的next指向新插入的节点x
     xp.next = x;
     //新插入节点x的父节点和前驱节点都指向xp
     x.parent = x.prev = xp;
     //如果xpn不为null
     if (xpn != null)
         //那么xpn的前驱指向新节点x
         ((TreeNode<K, V>) xpn).prev = x;
     //同样插入节点之后需要balanceInsertion调整平衡,以及moveRootToFront重设root的引用关系
     //这两个方法在"构建红黑树treeify方法"部分已经详细讲解了，在此不作赘述
     moveRootToFront(tab, balanceInsertion(root, x));
     //返回null，表示新插入了节点
     return null;
 }

}
}

/**

获取根节点的方法root()
*/
final TreeNode<K, V> root() {
//从当前节点向上寻找，直到某个节点的parent为null，那么该节点就是根节点
for (TreeNode<K, V> r = this, p; ; ) {
if ((p = r.parent) == null)
return r;
r = p;
}
}

/**

新建红黑树节点
@param hash k的hash
@param key k
@param value v
@param next next
@return 红黑树节点
*/
TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next) {
return new TreeNode<>(hash, key, value, next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
5.2.5.1 find查找相同节点
find方法用于根据指定key查找key相同的节点。查找成功就返回找到的节点，查找失败就返回null。这个查找实际上就是二叉排序树的查找递归查找。在插入获取和删除时都需要调用find方法。

key相同的的要求是：两个key的hash相同，并且两个key的equals或者==比较返回true。

/**

以调用该方法的该节点作为根节点，查找其所有子孙节点，尝试匹配给定的h或者k或者kc
就是二叉排序树的查找方式，递归查找
@param h k的hash
@param k key
@param kc k的类型
@return 没找到就返回null, 找到匹配的就返回该节点
*/
final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
//获取调用节点
TreeNode<K, V> p = this;
/循环该节点的子树查找相等的key/
do {
//dir表示寻找的方向 -1表示左边 1表示右边
//ph用来存储当前节点的hash
int ph, dir;
//用来存储当前节点的key
K pk;
//获取p的左子结点pl和右子节点pr
TreeNode<K, V> pl = p.left, pr = p.right, q;
/首先比较hash值/
//如果当前节点的hash值大于k的hash值h，那么应该查找左子树
if ((ph = p.hash) > h)
p = pl;
//如果当前节点的hash值小于k的hash值h，那么应该查找右子树
else if (ph < h)
p = pr;
/到这里,说明hash值相等,那么比较equals或者==/
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
//到这里还是相等，那么就算找到了相等的key的节点，返回p
return p;
/到这里,说明hash相等但是比较equals或者==都返回false，那么尝试超找左/右子节点,前提是必须有一个子节点为null/
//如果左子节点为null，那么查找右子节点
else if (pl == null)
p = pr;
//如果右子节点为null，那么查找左子节点
else if (pr == null)
p = pl;
/如果左右孩子都不为空，尝试将两个key转换为Comparable进行比较，来确定到底该往哪个方向去对比/
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
/到这一步，说明两个key可以比较（可以转换为Comparable），或者Comparable比较不返回0/
//dir小于0，就查找左子树，否则查找右子树。
p = (dir < 0) ? pl : pr;
/*到这一步，说明两个key无法比较（不可以转换为Comparable），或者Comparable比较返回0
* 那么指定从右子树递归查找
* */
else if ((q = pr.find(h, k, kc)) != null)
//如果返回q不为null，说明找到了，那么返回q
return q;
/如果从右子树递归查找后仍未找到，那么从左子树开始循环查找/
else
p = pl;
/如果p为null，表示查找到了叶子节点，那么循环结束/
} while (p != null);
/循环结束还是没找到，返回null/
return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
5.3. put方法流程图总结
5.3.1 put方法的关键流程图
根据上面的规律，我们可以总结出JDK1.8的HashMap的put方法的关键流程图：

5.3.2 resize方法关键流程图
JDK1.8HashMap的resize方法(用于初始化和扩容)的关键流程图：

6 remove方法
public V remove(Object key)

从此map中移除指定键的键值对（如果存在）。返回与 key 关联的value；如果没有指定key，则返回 null。（返回 null 还可能表示该映射之前将 null 与 key 关联。）

remove方法是HashMap的核心方法之一，源码较多，主要难点在于移除红黑树节点之后的平衡方法，不过这些都是有章可循的！

remove方法可以分为两步：

寻找与给定key相同的节点。
找到了就移除该节点，返回该节点的value；没找到就返回null。
/**

移除节点开放给外部调用的方法，根据指定key移除找到的节点
1. 寻找与给定key相同的节点；
1. 找到了就移除该节点，返回该节点的value；没找到就返回null
@param key k
@return 返回与 key 关联的value；如果没有指定key，则返回 null。（返回 null 还可能表示该映射之前将 null 与 key 关联。）
*/
public V remove(Object key) {
Node<K, V> e;
//主要是调用removeNode方法，hash(key)方法在最前面添加节点时就已经分析了
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
6.1 removeNode移除节点的总方法
removeNode是移除节点的总方法，即很多开放给外部调用的API中，内部就是调用的该方法。可以是根据key移除节点，也可以是根据key和value移除节点。

大概可以分为如下几步：

在哈希表中尝试查找与key相同的节点；
如果找到了节点，那么判断是否符合指定的模式：是根据key移除还是根据key和value移除，如果符合，那么尝试移除节点，并返回被移除的节点，否则返回null。
/**

移除节点的总方法，可以是根据key移除，也可以是根据key和value移除
@param hash key的hash
@param key 要匹配的key
@param value 要匹配的value
@param matchValue 如果为 true，则需要在键和值都比较并相等时才删除；否则只比较key
@param movable 如果为 false，则在删除时不移动其他节点，用在红黑树中
@return 返回被删除的节点，没有删除则返回null
/
final Node<K, V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K, V>[] tab;
Node<K, V> p;
int n, index;
/判断哈希表是否非空(不为null且有节点)，以及key通过哈希算法计算出来的桶为是否具有节点/
//如果table非空，key对应桶位节点p不为null，那么才进一步处理，否则直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//node保存要返回的节点
Node<K, V> node = null, e;
K k;
V v;
/1 在哈希表中查找与key相同的节点/
//如果key和数组桶为的第一个节点就像等了,那么node赋值为p
//相等的条件是：两个key的hash相同，并且两个key的equals或者比较返回true。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
/否则，查找该位置的链表或者红黑树/
else if ((e = p.next) != null) {
/*如果p是红黑树节点类型，那么p调用getTreeNode方法查找，
* 相等的条件是：两个key的hash相同，并且两个key的equals或者比较返回true。/
if (p instanceof TreeNode)
//getTreeNode方法下面有详解
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
/否则，就是普通节点类型，那么遍历链表查找/
else {
/do while循环链表/
do {
//相等的条件是：两个key的hash相同，并且两个key的equals或者比较返回true。
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
//如果key相等，那么node赋值为e，结束循环
node = e;
//这里break之后，下面的p = e;将不会执行，那么e就是p的next节点，即node是p的next节点
break;
}
//p=e
p = e;
//e=e.next
} while ((e = e.next) != null);
}
}
/*2 尝试移除节点
* &&左边的表达式一判断bode是否不为null，不为null就表示找到了key相等的节点
* &&右边的表达式二然后根据matchValue的值继续判断,如果matchValue为false,那么由于短路法后面的表达式为true
* 如果matchValue为true，那么比较value是否相等，相等的条件是：两个value的equals或者比较返回true。
* &&两边的表达式都为true时，进入if方法体，否则返回null
* */
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
/2.1 如果找到的节点node属于红黑树节点，那么node节点调用removeTreeNode方法移除节点/
if (node instanceof TreeNode)
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
/2.2 否则，如果找到的节点node等于p，即是数组节点，那么直接将数组桶位指向该节点的next节点即可/
else if (node == p)
tab[index] = node.next;
/*2.3 否则，由于在上面链表中查找的时候，最终node是p的next节点
* 那么p.next指向node.next，即将node去除
* */
else
p.next = node.next;
//数据结构改变次数自增1
++modCount;
//节点数量自减1
–size;
//元素被删除之后的回调方法，该方法在HashMap中的实现为空
//是留给子类LinkedHashMap实现的，用于删除LinkedHashMap中维护的双链表
afterNodeRemoval(node);
//返回node
return node;
}
}
//返回null
return null;
}

/**

红黑树节点内部的方法，由红黑树节点调用，用于获取和指定key相等的节点
@param h k的hash
@param k k
@return 查找到的节点，没找到就返回null
*/
final TreeNode<K, V> getTreeNode(int h, Object k) {
//首先是判断当前节点是否根节点，即父节点是否为null，如果不是那么root()方法获取根节点，root方法在“插入红黑树节点putTreeVal方法”有详解
//然后根节点用调用find方法超找指定key的键值对，就是二叉排序树的查找方法，find方法在“find查找相同节点的方法”部分有详解
return ((parent != null) ? root() : this).find(h, k, null);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
下面对重要方法单独讲解！

6.1.1 removeTreeNode移除红黑树节点的方法
该方法仅仅被用在删除节点的removeNode方法中，用于移除红黑树的某个节点。

如果我们对红黑树有所了解，那么我们会知道，红黑树最复杂的地方就是删除节点的方法了，因为有很多种情况需要考虑到，需要对移除节点的红黑树进行再平衡操作。不同的代码虽然实现不同，但是原理基本上一致，如果懂得了原理，那么看代码就很简单了：数据结构—红黑树(RedBlackTree)的实现原理以及Java代码的完全实现！

大概分为如下几步：

将节点与红黑树链表的关系移除（next、prev关系）；
判断红黑树是否符合某些结构，如果符合那么将红黑树转换为链表，方法结束；
如果不符合，那么先通过二叉排序树的方式查找需要被真正移除的节点位置，找到之后如果不是原位置那么交换需要移除的节点和真正需要被移除的节点的数据（right、left、parent关系）；
如果需要移除的节点具有子节点（真正需要移除的位置的节点要么没有子节点要么只有一个子节点）。那么先使用二叉排序树的移除方法将需要移除的节点移除了（right、left、parent关系）；
调整平衡。这里的调整把需要移除的节点没有子节点的情况都考虑进去了，并返回调整平衡之后的root根节点；
在调整平衡之后，如果需要移除的节点没有子节点，那么将需要移除的节点移出了（right、left、parent关系）；
由于可能调整了树节点，导致产生新的root节点，因此调用moveRootToFront方法将root节点作为数组桶位节点以及链表头节点。
/**

该方法由红黑树节点对象调用
移除红黑树节点，在移除链表关系之后移除节点关系之前如果符合某些红黑树结构，红黑树将转换为链表。
@param map 当前map
@param tab 当前table数组
@param movable 如果为 false，则在删除时不移动其他节点
*/
final void removeTreeNode(HashMap<K, V> map, Node<K, V>[] tab, boolean movable) {
int n;
/如果table数组为null或者没有节点，那么直接返回/
if (tab == null || (n = tab.length) == 0)
return;
//获取当前调用节点所在的数组桶位
int index = (n - 1) & hash;
//获取数组节点作为链表头节点first，同时作为红黑树根节点root，rl作为根节点的左节点
TreeNode<K, V> first = (TreeNode<K, V>) tab[index], root = first, rl;
//succ作为当前调用节点的next节点，pred作为当前调用节点的prev节点
TreeNode<K, V> succ = (TreeNode<K, V>) next, pred = prev;

/*1
- 我们前面讲过，HashMap中的红黑树的节点还通过next和prev维持双向链表的特征
- 因此下面的代码是将当前this节点从红黑树链表(next和prev)中移除
- */
  /*1.1 如果前驱节点为null，那说明当前节点是根节点，并且是链表头节点
- 如果前驱节点不为null，那说明当前节点不是根节点，并且不是链表头节点
- */
  if (pred == null)
  //那么数组位置的节点使用当前调用节点的next节点来代替
  //并且first当前节点的next节点succ
  tab[index] = first = succ;
  else
  //那么前驱节点pred的next节点指向当前节点的next节点succ
  pred.next = succ;
  /1.2 如果当前调用节点的next节点succ不为null/
  if (succ != null)
  //那么succ的前驱节点设置为pred
  succ.prev = pred;
/如果first为null，即那么直接返回正常情况下应该不会发生/
if (first == null)
return;
/如果root的父节点不为null，那么获取真正的root节点并赋值给root，正常情况下应该不会发生/
if (root.parent != null)
root = root.root();
/* 2 在删除红黑树节点之前，判断红黑树的结构，如果符合以下结构，那么将红黑树转换为普通链表,然后方法结束
*
- 如果root为null，或者root的右子树为null，或者root的左子树rl为null，或者左子树rl的左子树为null
- 出现上述情况的一种，那么就表示红黑树节点太少了并且结构，将会使用untreeify方法将红黑树转换为链表
- 注意这里并不是判断数量小于等于UNTREEIFY_THRESHOLD（6），而是判断树结构，
- 从红黑树的结构，我们可以知道，最少节点为3个时将会从红黑树转换为链表，最多可以在还有10个节点时即可转换为普通链表
- */
  if (root == null || root.right == null ||
  (rl = root.left) == null || rl.left == null) {
  //untreeify方法将红黑树转换为链表，转换为链表时实际上是使用到了的next和prev引用
  //当前节点的next和prev引用在上面就已经和红黑树链表脱离了关系，因此转换为链表之后，该节点自动丢失，因此直接返回即可
  tab[index] = first.untreeify(map); // too small
  return;
  }
  /3 走到这里开始删除红黑树节点/
  //p为当前待删除节点 pl为左子节点 pr为右子节点,replacement用于记录后续填充被删除节点p的位置的节点
  TreeNode<K, V> p = this, pl = left, pr = right, replacement;
  /*3.1 如果左\右子节点都不为null，那么p不是叶子节点，这里需要查找真正应该被删除的节点
- HashMap的查找方式和二叉排序树的方式是一样的，并且是寻找右子树的最左（小）节点，替代目标节点，用来被删除
- 这里找到之后会进行节点的替换，注意这里的替换和某些红黑树的替换不一样，
- 这里的替换包括颜色的替换和相关引用的替换，即“真正”的将节点P替换到需要被删除的位置上，同时颜色还是保持了原来位置上的颜色
- */
  if (pl != null && pr != null) {
  //s作为真正需要被删除的节点，目前赋值为当前待删除节点的右子节点；sl作为s的左子节点
  TreeNode<K, V> s = pr, sl;
  /*寻找真正应该被删除的节点s，实际上是二叉排序树的删除逻辑，我们知道有两种查找方法：
  - 1 寻找右子树的最左（小）节点，替代目标节点，用来被删除
  - 2 寻找左子树的最右（大）节点，替代目标节点，用来被删除
  - 这里JDK1.8的HashMap采用的是第一种
  - */
    while ((sl = s.left) != null) // find successor
    //s赋值为sl
    s = sl;
    /首先交换s和p的颜色/
    boolean c = s.red;
    s.red = p.red;
    p.red = c; // swap colors
    /然后交换节点，所以说实际上是：最终节点换了位置，但是原位置上的节点颜色并没有换/
    //sr赋值为最左（小）节点s的右子节点
    TreeNode<K, V> sr = s.right;
    //pp赋值为待删除节点p的父节点
    TreeNode<K, V> pp = p.parent;
    /*如果右子树的最左（小）节点s等于待删除节点的右子节点pr
  - 那说明待删除节点p的右子节点pr没有左子节点，pr就是右子树的最左（小）节点s
  - 并且还说明说明p是s的直接父节点
  - */
    if (s == pr) { // p was s’s direct parent
    /交换它们的红黑树部分引用父子关系/
    p.parent = s;
    s.right = p;
    }
    /*否则，那说明待删除节点p的右子节点pr具有左子节点，pr不是右子树的最左（小）节点s
  - 并且还说明说明p不是s的直接父节点
  - */
    else {
    /交换它们的部分引用父子关系/
    //获取s的父节点sp
    TreeNode<K, V> sp = s.parent;
    //p的父节点指向sp并且不为null
    if ((p.parent = sp) != null) {
    //那么p为sp的某个子节点
    if (s == sp.left)
    sp.left = p;
    else
    sp.right = p;
    }
    //pr作为s的右子节点
    if ((s.right = pr) != null)
    pr.parent = s;
    }
    /为其他引用关系赋值/
    //p被交换到右子树的最左（小）节点上，那么p.left肯定置为null
    p.left = null;
    //p.right设置为sr
    if ((p.right = sr) != null)
    sr.parent = p;
    //s.left 设置为 pl
    if ((s.left = pl) != null)
    pl.parent = s;
    //如果父节点pp为null，那么s作为根节点
    if ((s.parent = pp) == null)
    root = s;
    //否则，建立它们的引用关系
    else if (p == pp.left)
    pp.left = s;
    else
    pp.right = s;
    /交换位置关系之后，s到了p的位置，p到了s的位置，即此时p作为真正需要被删除的节点/
    /寻找删除p之后替代p位置的节点/
    //交换关系之后，sr已被作为p的右子节点，sr如果不为null，那么sr将代替p删除后的位置
    if (sr != null)
    replacement = sr;
    //否则就是设置p本身代替p，实际上是此时的P没有了子节点。
    else
    replacement = p;
    }
    /3.2 如果左子树pl不为null，那么pl将代替p删除后的位置/
    else if (pl != null)
    replacement = pl;
    /3.3 如果右子树pr不为null，那么pr将代替p删除后的位置/
    else if (pr != null)
    replacement = pr;
    /3.4 否则，两个子节点都为null，那么就是设置p本身代替p/
    else
    replacement = p;
/*
- 4 如果replacement不等于p，那么表示将由节点replacement代替p的位置；
- 这里先把p进行删除，然后再进行平衡调整
- */
  if (replacement != p) {
  //replacement的父节点指向p的父节点
  TreeNode<K, V> pp = replacement.parent = p.parent;
  //父节点pp为null，表示p为根节点，删除p之后则replacement变成根节点
  if (pp == null)
  root = replacement;
  //设置与父节点的左右孩子关系
  else if (p == pp.left)
  pp.left = replacement;
  else
  pp.right = replacement;
  //p的关联引用置空
  p.left = p.right = p.parent = null;
  }
/*
- 5 判断被删除的p是否是红色节点，如果是红色，即属于“删红”的情况，那么不需要调整树结构，直接删除节点即可；
- 否则需要balanceDeletion方法分情况重新平衡红黑树，并返回平衡后旧的新root节点
- 这里平衡的时候把replacement == p的情况也进行平衡了，因为实际上这种情况可以看作“删黑子黑的情况”，这里把null节点看成黑色
- */
  TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);
/*6 如果replacement等于p，那么表示没有节点代替p的位置，有可能是sr为null或者被删除的节点P本来就没有左右子节点，实际上都是p作为叶子节点；
- 也把p进行删除，注意在此之前先进行了平衡调整，因此移除之后不必再进行平衡调整了。
- /
  if (replacement == p) { // detach
  /下面的代码将p的父节点pp和p的红黑树关系解除/
  TreeNode<K, V> pp = p.parent;
  p.parent = null;
  if (pp != null) {
  if (p == pp.left)
  pp.left = null;
  else if (p == pp.right)
  pp.right = null;
  }
  }
  /
- 7 moveRootToFront用于将最后的root节点，设置为数组节点，即tab[i]=root。
- 同时调整root的next和prev的引用指向，将root节点作为链表的头节点。该方法源码在添加元素时讲过了
- */
  if (movable)
  moveRootToFront(tab, r);
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159
  160
  161
  162
  163
  164
  165
  166
  167
  168
  169
  170
  171
  172
  173
  174
  175
  176
  177
  178
  179
  180
  181
  182
  183
  184
  185
  186
  187
  188
  189
  190
  191
  192
  193
  194
  195
  196
  197
  198
  199
  200
  其中某些方法比如moveRootToFront在前面添加元素时源码已经讲过，下面主要针对移除元素后调整平衡的方法进行讲解！

6.1.1.1 balanceDeletion移除后调整平衡
该方法比较复杂，因为红黑树最难的操作就是移除节点后的平衡，情况非常多，但是HashMap这里的实现代码还是比较少的，因此可能会有很多巧妙地思想难以理解！需要对红黑树的原理有深入掌握才能更方便理解！

具体的原理源码都在代码注释中了。

/**

删除节点时的平衡操作，进入该方法的情况是，被删除的节点必须是黑色。
该方法将一些复杂的情况最终转换为一些简单的情况统一返回，非常的巧妙
@param root 根节点
@param x 当前节点p或者替代p的replacement
@return 平衡止之后的根节点
*/
static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root,
TreeNode<K, V> x) {
for (TreeNode<K, V> xp, xpl, xpr; ; ) {
/1 如果x为空，或者x为根节点那么直接返回root。下面的复杂情况处理完毕在下次循环时会成为该情况/
if (x == null || x == root)
//返回根节点
return root;
/2 如果被删除节点x的父节点xp为null，那么x就是根节点，将x染黑即可，返回x。下面的复杂情况处理完毕在下次循环时会成为该情况。/
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
/3 否则，如果x为红色，那么属于“删黑子红”，此时x涂黑即可，返回root。下面的复杂情况处理完毕在下次循环时会成为该情况。/
else if (x.red) {
/x改为黑色，返回root/
x.red = false;
return root;
}
/*4 否则，属于“删子黑”，这并没有考虑被删除节点是红色还是黑色的情况，因为如果删除节点是红色，那么子节点肯定是黑色，删除红色节点是不需要调整的；
* 那么即使对它进行调整的运用，也一定完全兼容被删除节点是黑色的调整方式，思想很好！
* */
/获取获取x的左兄弟节点xpl，如果xpl等于x，那么说明x就是左子节点，兄弟节点就是右子节点/
else if ((xpl = xp.left) == x) {
/*4.1 获取右兄弟节点xpr，如果是红色，属于——“删兄红-右兄弟”
* 处理方法是：则以父节点P为基点左旋，然后B涂黑、P涂红，最后将BL看成新的兄弟节点newB，转换为“删兄黑”，然后统一处理。
* */
if ((xpr = xp.right) != null && xpr.red) {
//右兄弟xpr涂黑
xpr.red = false;
//父节点xp涂红
xp.red = true;
//父节点左旋
root = rotateLeft(root, xp);
//将BL看成新的兄弟节点newB
xpr = (xp = x.parent) == null ? null : xp.right;
}
/*4.2 下面的就是“删兄黑”的情，况如果xpr为null，null也看成黑色节点
* “删兄黑”的情况是最复杂的一种情况
* /
/4.2.1 如果xpr为null，即“删兄黑——兄子全黑”，null看成黑色/
if (xpr == null)
//父节点xp当作新的x节点，继续下一次循环，直到
x = xp;
else {
//sl作为右兄弟节点的左子节点，sr作为右兄弟节点的右子节点
TreeNode<K, V> sl = xpr.left, sr = xpr.right;
/如果（sr为null或者sr为黑色），并且（sl为null或者sl为黑色），即“删兄黑——兄子全黑”，null看成黑色/
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
//兄弟节点xpr涂红
xpr.red = true;
//父节点xp当作新的x节点
x = xp;
}
/ 上面的代码处理了“兄子全黑-父黑、父红“这两种两种情况，此时父节点xp作为x，可能为红或者黑。”
* 传统处理方法是：
* 对于兄子全黑-父黑：将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，回到删黑子黑的情况，即向上递归进行处理，直到C成为根节点或者达到平衡。
* 对于兄子全黑-父红：将兄弟节点B涂红，父节点P涂黑即可。此时原本删除黑色节点的路径补充了黑色节点，即可达到平衡。
*
* HashMap的处理方法是：兄弟节点B涂红，将父节点P设为新的C节点向上递归进行处理，直到C成为根节点或者达到平衡。
* HashMap没有特意区分这两种情况，而是统一循环处理了，减少了代码量：
* 如果父节点xp是红色，那么在下一次向上循环时，将在情况3的地方涂黑并返回
* 如果父节点xp是黑色，那么不断向上循环，直到C成为根节点或者达到平衡。
* */
/*4.2.2 否则，表示属于兄子非全黑的情况，需要进一步处理，此时可能是“兄右，右子黑或者兄右，右子红”的情况
*
* */
else {
/*如果右兄弟节点的右子节点为null或者为黑色，那么属于“兄右，右子黑”
* 处理方法是：以兄弟节点B为基点右旋，然后BL涂黑，B涂红，然后将BL当成新B，B当成新BR，这样就转换成了情况2-“兄右，右子红”。
* */
if (sr == null || !sr.red) {
//右兄弟节点的左子节点sl(BL)涂黑，
if (sl != null)
sl.red = false;
//兄弟节点xpr(B)涂红
xpr.red = true;
//以兄弟节点xpr(B)为基点右旋
root = rotateRight(root, xpr);
//然后将BL当成新B，B当成新BR，这样就转换成了情况2-“兄右，右子红”。
//实际上旋转之后BL成为了xp的right右子节点
xpr = (xp = x.parent) == null ?
null : xp.right;
}
/*下面就是“兄右，右子红”的情况
* 处理方法是：以父节点P为基点左旋，然后交换P和B的颜色（实际上就是兄弟节点的颜色设置为父节点的颜色，父节点涂黑，因为兄弟节点肯定是黑色的）
* ，然后BR涂黑，平衡完毕！
* */
if (xpr != null) {
//兄弟节点的颜色设置为父节点的颜色
xpr.red = (xp == null) ? false : xp.red;
//sr(BR)涂黑
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
//父节点涂黑
xp.red = false;
//以父节点xp§为基点左旋
root = rotateLeft(root, xp);
}
/设置x等于root，那么将在下一次循环时直接在情况1中退出/
x = root;
}
}
}
/否则，那么说明x就是右子节点，兄弟节点就是左子节点。它的处理方式和上面的if代码块中的方式是镜像的/
else { // symmetric
/*4.3 左兄弟xpl，如果是红色，属于——“删兄红-左兄弟”
* 处理方法是：则以父节点P为基点右旋，然后B涂黑、P涂红，最后将BR看成新的兄弟节点newB，转换为“删兄黑”，然后统一处理。
* */
if (xpl != null && xpl.red) {
//左兄弟xpl(B)涂黑
xpl.red = false;
//父节点xp§涂红
xp.red = true;
//以父节点xp§为基点右旋
root = rotateRight(root, xp);
//将BR看成新的兄弟节点newB
xpl = (xp = x.parent) == null ? null : xp.left;
}
/*4.4 下面的就是“删兄黑”的情况，如果xpl为null，null也看成黑色节点
* “删兄黑”的情况是最复杂的一种情况
* /
/4.4.1 如果xpl为null，即“删兄黑——兄子全黑”，null看成黑色/
if (xpl == null)
//父节点xp当作新的x节点
x = xp;
else {
//sl作为左兄弟节点的左子节点，sr作为左兄弟节点的右子节点
TreeNode<K, V> sl = xpl.left, sr = xpl.right;
/如果（sr为null或者sr为黑色），并且（sl为null或者sl为黑色），即“删兄黑——兄子全黑”，null看成黑色/
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
//兄弟节点xpr涂红
xpl.red = true;
//父节点xp当作新的x节点
x = xp;
}
/ 上面的代码处理了“兄子全黑-父黑、父红“这两种两种情况，此时父节点xp作为x，可能为红或者黑。”
* 传统处理方法是：
* 对于兄子全黑-父黑：将兄弟节点B涂红，将父节点P设为新的C节点，将U设为新B节点，将G设为新P节点，回到删黑子黑的情况，即向上递归进行处理，直到C成为根节点或者达到平衡。
* 对于兄子全黑-父红：将兄弟节点B涂红，父节点P涂黑即可。此时原本删除黑色节点的路径补充了黑色节点，即可达到平衡。
*
* HashMap的处理方法是：兄弟节点B涂红，将父节点P设为新的C节点向上递归进行处理，直到C成为根节点或者达到平衡。
* HashMap没有特意区分这两种情况，而是统一循环处理了，减少了代码量：
* 如果父节点xp是红色，那么在下一次向上循环时，将在情况3的地方涂黑并返回
* 如果父节点xp是黑色，那么不断向上循环，直到C成为根节点或者达到平衡。
* */
/*4.4.2 否则，表示属于兄子非全黑的情况，需要进一步处理，此时可能是“兄左，左子黑或者兄左，左子红”的情况
*
* */
else {
/*如果左兄弟节点的左子节点为null或者为黑色，那么属于“兄左，左子黑”
* 处理方法是：以兄弟节点B为基点左旋，然后BR涂黑，B涂红，然后将BR当成新B，B当成新BL，这样就转换成了情况4-“兄左，左子红”。
* */
if (sl == null || !sl.red) {
//左兄弟节点的右子节点sr(BR)涂黑，
if (sr != null)
sr.red = false;
//xpl(B)涂红
xpl.red = true;
//以兄弟节点xpl(B)为基点左旋
root = rotateLeft(root, xpl);
//然后将BR当成新xpl(B)，B当成新BL，这样就转换成了情况4-“兄左，左子红”。
//实际上旋转之后BR成为了xp的left左子节点
xpl = (xp = x.parent) == null ?
null : xp.left;
}
/*下面就是“兄左，左子红”的情况
* 处理方法是：以父节点P为基点右旋，然后交换P和B的颜色（实际上就是兄弟节点的颜色设置为父节点的颜色，父节点涂黑，因为兄弟节点肯定是黑色的）
* ，BL涂黑，平衡完毕！
* */
if (xpl != null) {
//兄弟节点的颜色设置为父节点的颜色
xpl.red = (xp == null) ? false : xp.red;
//sl(BL)涂黑
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
//父节点涂黑
xp.red = false;
//以父节点xp§为基点右旋
root = rotateRight(root, xp);
}
/设置x等于root，那么将在下一次循环时直接在情况1中退出/
x = root;
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
7 其他方法
如果我们把put和remove方法的源码看的差不多了，那么下面的一些其他方法对于我们来说就是小菜一碟！

7.1 get方法
public V get(Object key)

返回指定键所对应的值；如果找不到这个键，则返回 null。返回 null 值并不一定表明该映射不包含该键的映射关系；也可能该映射将该键显示地映射为 null。可使用 containsKey 操作来区分这两种情况。

/**

返回指定键所对应的值；如果找不到这个键，则返回 null。
返回 null 值并不一定表明该映射不包含该键的映射关系；也可能该映射将该键显示地映射为 null。
可使用 containsKey 操作来区分这两种情况。
@param key 查找的key
@return 返回指定键所对应的值；如果找不到这个键，则返回 null。
返回 null 值并不一定表明该映射不包含该键的映射关系；也可能该映射将该键显示地映射为 null。
*/
public V get(Object key) {
Node<K, V> e;
//内部调用getNode方法
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**

根据key获取具有相同key的Node节点
@param hash key的hash
@param key key
@return 相同key的Node节点或者null
*/
final Node<K, V> getNode(int hash, Object key) {
Node<K, V>[] tab;
Node<K, V> first, e;
int n;
K k;
/循环遍历数组/
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
/判断key相等的条件是：两个key的hash相同，并且两个key的equals或者==比较返回true。/
/1 如果数组桶位的节点的key是相同的，那么返回该节点，够则需要查询链表或者红黑树/
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
/2 查询链表或者红黑树/
if ((e = first.next) != null) {
/*如果属于红黑树节点类型，那么通过getTreeNode获取与指定key相同的节点
* getTreeNode方法在“removeNode移除节点的总方法”部分已经将过了
* */
if (first instanceof TreeNode)
return ((TreeNode<K, V>) first).getTreeNode(hash, key);
/否则，遍历普通链表获取与指定key相同的节点/
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
/到这一步还没返回说明没有查到找与指定key相同的节点，返回null/
return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
7.2 containsKey方法
public boolean containsKey(Object key)

如果此map包含指定key，则返回 true。

/**

如果此map包含指定key，则返回 true。
@param key k
@return 如果此map包含指定key，则返回 true。
*/
public boolean containsKey(Object key) {
//内部就是调用的getNode方法，并判断返回值是不是null来返回结果
//如果getNode返回null，那么返回false，否则返回true
return getNode(hash(key), key) != null;
}
1
2
3
4
5
6
7
8
9
10
11
7.3 containsValue方法
public boolean containsValue(Object value)

如果此map包含指定值，则返回 true。该方法性能比较低，因为对于数组、链表还是红黑树都采用的是顺序遍历，即需要遍历整个哈希表。

/**

如果此map包含指定值，则返回 true。
该方法性能比较低，因为对于数组、链表还是红黑树都采用的是顺序遍历，并且需要遍历整个哈希表。
@param value 指定值
@return 如果此map包含指定值，则返回 true。
*/
public boolean containsValue(Object value) {
Node<K, V>[] tab;
V v;
if ((tab = table) != null && size > 0) {
/循环底层数组/
for (int i = 0; i < tab.length; ++i) {
/循环每一个数组的链表，可能是普通链表，也可能是红黑树链表/
for (Node<K, V> e = tab[i]; e != null; e = e.next) {
/判断相等的条件是：==返回true 或者 equals方法返回true/
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
//遍历全部哈希表还没找到那么返回false
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
7.4 putAll方法
public void putAll(Map<? extends K,? extends V> m)

将指定map的所有数据复制到此map中，只是复制了数据的引用，即两个map的不同节点指向同一个key或者value对象。内部实际上就是循环调用putVal方法！

/**

将指定map的所有数据复制到此map中，只是复制了数据的引用，即两个map的不同节点指向同一个key或者value对象。
@param m 指定map
*/
public void putAll(Map<? extends K, ? extends V> m) {
//内部调用putMapEntries方法
putMapEntries(m, true);
}

/**

将指定map添加到该map集合
@param m 指定map
@param evict 在构造器中调用该方法时传入false，其他方法中(比如put、putAll)调用该方法时传入true。

         实际上该参数在HashMap中没啥用，是留给其子类linkedHashMap用于实现LRU缓存的！

*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取节点数量
int s = m.size();
//如果大于0
if (s > 0) {
/如果本集合table为null,那么初始化/
if (table == null) { // pre-size
float ft = ((float) s / loadFactor) + 1.0F;
int t = ((ft < (float) MAXIMUM_CAPACITY) ?
(int) ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
/否则，如果s大于扩容阈值，那么直接扩容/
else if (s > threshold)
resize();
/循环指定map，实际上就是调用putVal方法将检点一个个的加入到本集合中/
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
7.5 clear方法
public void clear()

清空哈希表。并没有新建数组，而是循环底层数组，将每一个桶位置空。

/**

清空哈希表
*/
public void clear() {
Node<K, V>[] tab;
modCount++;
/并没有新建数组，而是循环底层数组，将每一个桶位置空/
if ((tab = table) != null && size > 0) {
//将size置空
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
7.6 遍历的方法
遍历的方法主要有三个values()、keySet()、entrySet()，都是实现自超级接口Map。因此实际上HashMap和HashTable的遍历方法的底层实现都差不多，实际上获取的一系列键集、值集、键值对等，实际上都是操作的底层数组，因此可以对这个返回的结合进行操作来操作底层数组的数据。

遍历方法的源码详解，在：Java集合—Hashtable的源码深度解析以及应用介绍一文中有详细介绍。

Set< Map.Entry< K,V > > entrySet()

将该映射所有的键值对（键值对类型是Map.entry类型），返回并存放在一个Set 集合当中，获得set集合后可以遍历得到每个项的键值对，然后可以使用Map.entry中的提供的getkey、getValue、setValue等方法

Set< K > keySet()

返回包含该映射所有key的set集合，得到set集合后可遍历得到每个key，再通过：map.get(key)即可得到对应的value值。

Collection< V > values()

返回包含该映射所有的value值的 Collection 集合。通过遍历该集合，可以得到映射的value。但不能得到key。

8 Hashmap 在JDK1.7和1.8的某些区别
8.1 数据结构
JDK1.7的时候使用的是数组+ 单链表的数据结构。JDK1.8及之后时，使用的是数组+链表+红黑树的数据结构。使用红黑树主要时当链表过长时，对某个桶位元素的查找变成了线性时间O(n)，转换为红黑树之后查询时间复杂度从变成O(logN)提高了查找效率。但是也提升了实现难度。
JDK1.8及之后，在使用put方法添加元素时，当添加元素之后链表的长度大于8 、数组长度大于等于64 时（小于64会扩容一次），就会把普通链表转成红黑树的数据结构。
在扩容时，如果原红黑树在split方法中拆分出的红黑树链表长度小于等于6 时，红黑树还原为普通链表；否则，红黑树链表将会转换为红黑树。
在删除元素时，删除元素之前如果红黑树结构满足如下要求之一：root == null || root.right == null || (rl = root.left) == null || rl.left == null，那么红黑树将还原为普通链表！即节点数量在[3,10]之间，红黑树都将可能还原为普通链表！
8.2 链表插入数据方式
JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法。采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。

具体原因在前面添加元素部分有详解！

8.3 扩容机制
添加元素时，JDK1.7是先判断是否需要扩容，然后再插入新数据，JDK1.8是先插入数据，然后判断是否需要扩容。
JDK1.7的扩容要求是：(size >= threshold) && (null != table[bucketIndex])都满足才会扩容，即要求添加节点前（节点数量大于等于阈值并且这个新节点的桶位已经有了节点（即发生哈希冲突）才会扩容；
JDK1.8的扩容要求是++size> threshold即添加节点后++size如果大于扩容阈值就会扩容。
JDK1.7在转移数据时，节点的位置计算采用HashCosde()–>扰动算法–>h&(length-1)的方式重新计算，效率较低，并且转移时也采用头插法转移数据。
JDK1.8在转移数据时，节点的位置通过规律(e.hash & oldCap) == 0来判断新位置处于原始位置还是原始位置+老容量的位置，效率较高，并且转移时也相当于采用尾插法转移数据。
8.4 扰动算法
扰动算法用于进一步降低哈希冲突的概率。JDK1.7采用的扰动算法是四次>>>运算加五次^运算，JDK1.8采用的扰动算法是一次>>>运算加一次 ^ 运算，效率更高！

9 总结
下面我尽量给出一幅考虑多种情况的JDK1.8的HashMap结构图，如果你真的看完了我上面所写的全部内容，那么你应该不会对某些结构感到疑惑：

HashMap是我们使用的最多的集合类之一了。一般用来存放键值对，并且性能比较好。key不能重复，判断两个key是否相等的依据是：（两个key的HashCode返回值相等）并且（两个key使用==比较返回true或者使用equals比较返回true）。它是线程不安全，在并发环境下想要使用可以使用ConCurrentHashMap，关于JUC的源码，我将会在后续博客中一一分析！

写这篇文章花费了本人长达两天的时间，特别是在put和remove方法深入到最底层的红黑树源码的分析过程中，甚至有几次都想到放弃。本人只是一个从传统工科（采矿)转行到计算机行业的Java开发者，而且是在毕业工作了一年之后才尝试转行的，并没有本专业的开发者那么多基础知识储备。

虽然目前转行之后还算过得去，但是仍然记得在当初学习的时候，就觉得HashMap没那么简单，对于某个知识，我不想只会用，还想要理解它的原理。在工作之后，念念不忘，终于在今天还算比较彻底的分析了HashMap的主要方法的源码，但是里面说不定有很多错误，欢迎大家指出来，希望大家一起进步！

数据结构与算法最新文章

【力扣106】从中序与后续遍历序列构造二叉

leetcode 322 零钱兑换

哈希的应用：海量数据处理

动态规划|最短Hamilton路径

华为机试_HJ41 称砝码【中等】【menset】【

【C与数据结构】——寒假提高每日练习Day1

基础算法——堆排序

2023王道数据结构线性表--单链表课后习题部

LeetCode 之反转链表的一部分