HapMap 中的 get 和 put 方法在 O(1) 的时间内即可完成，如此快速存取方式到底是怎么实现的？本文将对 HashMap 中的主要方法（get、put、resize）进行说明，对应的版本为 JDK 1.8。不过，为了更加详细的了解 HashMap 的优化过程，同时也会与 JDK 1.7 中的 HashMap 进行比较，从而对 HashMap 有一个较为全面的认识。
总览
HashMap 是基于哈希表以key-value的映射方式实现的，一对key-value可以组成类型为Node（JDK 1.8）的存储对象（JDK 1.7 称为 Entry）。这些Node存储在数组中，其中key和value均可以为 null（即最多只允许一条记录的 key 为 null，而允许多条记录的 value 为 null），key是唯一的，即当有重复的key存在时，后面的 put(KEY, “b”) 会覆盖之前的 put(KEY, “a”)，而value是可以重复的。通过 HashMap 中的 hash 方法可以知道，在计算键的哈希值时，null 键的哈希值返回的是 0。
此外，HashMap 是无序的，同时也是非线程安全的，因为在 JDK 1.7 版本中，数组+链表（头插法）的形式会造成线程安全问题，即链表容易形成环，同时也对之前版本做了许多优化。例如，当链表长度大于 8 时会将链表转换成红黑树；重写了resize方法，在复制元素时避免重新计算键的哈希值以此提高效率等。
而哈希表的实现方式是基于数组，假如知道了某个元素的索引，则可以在 O(1) 的时间内找到对应的元素。某个对象可以通过哈希函数得到存储地址，这些存储地址就是数组的索引，通过对应的索引就可以从数组中找到对应的值。
但如果两个元素分别在进行哈希函数的时候产生了相同的存储地址，则需要通过开放地址法、链地址法、再散列函数法等解决此的问题，而 HashMap 采用数组+链表（JDK 1.8 尾插法）+红黑树的形式就是基于链地址法进行实现的。如下图所示：
在使用 HashMap 进行增、删、查操作的时候，首先需要通过计算从而定位到元素所在桶（数组）的位置，假如直接在桶中找到了则返回，否则再从链表中查找该元素。如果之前的链表已经转化成红黑树了，则需要在桶位置的基础上，直接在红黑树中进行查找。
下面结合源码进行说明。
实现原理
存储单元 Node
Node类实现了Map.Entry接口，该Entry表示键值对的映射关系，上图中的每个矩形框代表了一个Node，通过对key的hashCode进行哈希运算，可以得到该Node在数组中的具体位置。数组是 HashMap 的主干，而链表则是为了解决由相同哈希值造成的哈希冲突问题。
如果数组中的某个位置没有形成链表，即当前Node的next为null，则说明该位置还没有造成冲突，这对于查找、添加操作来说是很快的，在 O(1) 时间内可以完成。但如果数组中的当前位置上已经有了链表，对于添加操作来说，则需要对链表进行遍历，如果存在相同的key则将其覆盖，否则进行添加。所以，链表存在的越少，则操作越快。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 用来定位数组索引的位置
final K key; // 键
V value; // 值
Node<K,V> next; // 链表中的下一个 Node
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() { ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
|
此外，还有一个需要注意的细节，如下所示：
1
|
transient Node<K,V>[] table;
|
每个键值对会被放进一个桶数组当中，而这里对桶数组的声明采用了 transient 关键字，意为转瞬即逝的、暂时的。在 Java 中，被该关键字所修饰的变量默认是不会被进行序列化的。通过阅读这篇文章之后，总结一下使用 transient 关键字修饰 table 的原因。
HashMap 通过实现readObejct/writeObject两个方法自定义了序列化等内容，反而没有使用默认的序列化机制。不采用默认的序列化的原因在于：
- 桶数组 table 在多数情况下无法被填满，此时对其进行序列化时，会产生空间的浪费；
- 同一个
键值对在不同的 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下进行反序列化操作，table 可能会发生错误。
由于 HashMap 中的 get、put、remove 是根据 hash 找到键所在的桶位置，如果没有覆写 hashCode 方法，则通过计算 hash 时最终调用的是 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是被 native 修饰的，在不同的 JVM 下会有不同的实现，从而产生的 hash 可能不同，即同一个键在不同的 JVM 下可能会产生不同的 hash。所以这里的 table 被 transient 修饰，使其不被序列化。
构造函数
HashMap 的源码中一个有 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
|
// 第一个构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// 第二个构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 第三个构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// 第四个构造函数
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
|
我们平时使用的new HashMap<>()就是第三个构造函数，这里面涉及一些属性，由于这些属性与后文的扩容、get 方法、put 方法以及 resize 方法相关，所以在这里进行说明。如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// 默认初始化容量是 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 默认负载因子是 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final float loadFactor;
// 当前 HashMap 所能容纳键值对数量的最大值，超过这个值，则需扩容
// 其中 threshold = capacity * loadFactor
int threshold;
transient int modCount;
transient int size;
|
在第一个构造方法中有两个参数是可以自定义的：initialCapacity 和 loadFactor，即初始化容量（默认是 16）和负载因子（默认是 0.75）。
其中，threshold是 HashMap 所能容纳的最大数据量Node的个数，也就是键值对的个数。而loadFactor反应了桶数组的填满程度，也就是桶数组的使用情况。在数组长度一定的情况下，负载因子loadFactor越大，则所能容纳的键值对的个数就越多。通知调节负载因子，可以使程序在时间和空间上具有不同的表现。例如：
- 调低负载因子，则 HashMap 所能容纳的键值对数量变少，空间利用率低，即空间给浪费了，表中的数据过于稀疏。扩容时，将
旧键值对存储到新键值对的时候，键和键之间产生的碰撞会下降，链表的长度会变短，即以空间换时间；
- 调高负载因子，则 HashMap 所能容纳的键值对数量变多，空间利用率高，但碰撞也高，链表的长度变长，效率降低，即以时间换空间。
而size表示 HashMap 中实际存在的键值对数量，modCount用于记录 HashMap 内部结构发生变化，如 put、remove 等操作。
你可以看到，第一个构造方法的最后两句，初始化了loadFactor和threshold，但有一个初始化阈值函数tableSizeFor需要说明一下，如下所示：
1
2
3
4
5
6
7
8
9
|
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
|
可以看到，一开始将传入的参数 initialCapacity （二进制为 32 位）进行减一操作赋值给 n，然后分别将 n 的二进制位向右无符号移动 1、2、4、8、16 位，再与 n 进行或操作。最后比较 n 与 0 的大小关系，如果 n 小于 0 的话，则返回 1，否则，再次比较 n 与 MAXIMUM_CAPACITY（1 « 30 = 1073741824）的大小关系。如果 n 超过了 MAXIMUM_CAPACITY，则函数返回 MAXIMUM_CAPACITY，否则将返回 n + 1。这个看起来比较简单。
上面这段代码用于返回大于或等于 cap 的最小的 2 的幂。例如cap = 13，则返回16；cap = 16，则返回16；cap = 17，则返回32。
hash 方法
对于任意的对象，只要它的hashCode()的返回值相同，则hash()方法返回的值也是相同的。这里首先进行了h = key.hashCode()，然后将h的高位参与运算，即h ^ (h >>> 16)。通过这种方式，可以将h的高位与低位进行异或操作，以此加大低位信息的随机性，从而增大hash的复杂度。
由于hashCode产生的hash是 int 类型，共 32 位，左边为高 16 位，右边为低 16 位，所以需要向右移 16 位。同时，对于数组长度较小的情况，也能考虑到高位和低位都参与到hash的运算中，同时不会有太大的开销。
1
2
3
4
|
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
|
get 方法
get() 方法的流程如下：
- 首先定位键值对所在桶（数组）的位置；
- 如果桶上的 key 是要查找的 key，则直接就找到了；
- 如果桶上的 key 不是要查找的 key，则查看后续节点；
- 如果后续节点是红黑树结构，则使用红黑树的查找方法进行查找；
- 如果后续节点是链表结构，则遍历链表进行查找。
源码如下所示：
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
|
// 此 get() 调用了 getNode() 方法，在传入 key 之前计算了 key 的 hash
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
// 是否直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果数组中的 key 不是要查找的 key 的话，则查看后序节点
if ((e = first.next) != null) {
// 如果 first 是红黑树，则调用红黑树的查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 遍历链表进行查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
|
从代码中可以看出，HashMap 底层采用 Node 数组（桶）来存储键值对，当进行 get 操作取出一个 Node 时，先通过 hash 算法计算其在桶（数组）中的位置，然后通过 equals 方法在红黑树或者链表中进行查找。
其中，对于获得桶（数组）的位置，也就是计算数组中的索引，如下：
1
2
|
确定桶（数组）的索引：index = (n - 1) & hash;
桶（数组）在索引 index 上的键值对：first = tab[(n - 1) & hash];
|
通过与运算来得到当前对象在桶（数组）中的位置，而 HashMap 底层数组的长度（这里的 n 指的是数组的长度，我们用 length 表示）总是 2 的整数次幂（下面会说为什么）。当数组的长度是 2 的整数次幂时，(n - 1) & hash 操作等价于对数组长度（length）取模运算，由于取模会用到除法运算，所以通过与运算代替取模。
为什么桶（数组）的长度一定要是 2 的整数次幂？
-
- length 为 2 的整数次幂的话，hash & (length - 1) 就相当于对 length 取模，这样就保证了散列的均匀，同时也提升了效率；
-
- length 为 2 的整数次幂的话，结果是偶数，而 length - 1 为奇数，奇数的最后一位是 1，这样就能保证 hash & (length - 1) 操作的最后一位可能为 0 也可能为 1（取决于 hash 的值），即
与操作后的结果可能是奇数也可能是偶数，这样可以保证散列的均匀性。而如果 lenght 是奇数的话，length - 1就会是偶数，偶数的最后一位是 0，这样 hash & (length - 1) 的结果最后一位一定是 0，即只能为偶数，此时的 hash 值就会被散列到桶（数组）的偶数下标的位置上，这便浪费了大约一半的空间。
-
- 因此，将 length 设置为 2 的整数次幂，是为了使不同的 hash 值发生碰撞的概率变小，使得元素能够在桶（数组）中大致呈均匀分布。
put 方法
put() 方法调用了 putVal() 方法，只不过在调用之前对 key 进行了 hash 操作。整体流程是：首先找到需要插入的桶的位置，即判断待插入的键值对属于哪个桶，如果该桶的位置为空，则直接插入即可。如果不为空，则需要查看链表中是否已经存在了该键值对，如果没有存在的话，则将键值对链接到链表的尾部（尾插法），如果已经存在的话，则更新键值对。当然，具体的流程比这复杂的多，还应涉及到红黑树的查找过程。如下图所示：
整体流程如下：
- 1). 判断键值对数组 table[i] 是否为空或 null，是的话则执行 resize() 进行扩容；
- 2). 如果不满足上述条件，则根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i] == null，则直接创建新节点进行添加，再转向 6)；如果 table[i] 不为空，则转向 3)；
- 3). 判断 table[i] 的首个元素是否和 key 一样，是的话直接覆盖 value，否则转向 4)，这里的相同指的是 hashCode 和 equals；
- 4). 判断 table[i] 是否为 treeNode（红黑树），如果是红黑树，则在树中直接插入键值对，如果不是红黑树，则转向 5)；
- 5). 遍历 table[i]，判断链表长度是否大于 8，如果大于 8 则将链表转换成红黑树，在红黑树中执行插入操作，否则插入到链表中；若遍历的过程中 key 已经存在了，则直接覆盖即可；
- 6). 插入成功后，判断实际存在的键值对的数量 size 是否大于最大容量 threshold，如果超过了，则进行扩容。
源码如下所示：
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
|
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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) 等到插入新数据时才初始化桶数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤 2) 如果桶中不包含键值对节点的引用，则说明之前没有数据插入过，
// 那么就直接新建一个键值对节点，将其插入到对应的桶中即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤 3) 如果键的值以及节点对应的 hash 等于链表中的第一个键值对节点，
// 则用 e 指向该键值对
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤 4) 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤 5) 当不满足上面的情况时，则就来到了链表
else {
// 遍历链表，统计长度
for (int binCount = 0; ; ++binCount) {
// 链表中不包含要插入的键值对节点时，则将该节点插在链表的最后（尾插法）
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度大于或等于树化阈值时，则进行树化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果为 true，则说明当前的链表已经包含了待插入的键值对，已经存在的话则直接覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判断要插入的键值对是否在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步骤 6) 键值对的数量超过阈值时，则进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
|
resize 扩容方法
当 HashMap 中的数组无法装载更多的元素时，则需要对扩大数组的长度，即进行 resize 扩容操作。数组本身并不能进行自身扩容，而是使用一个大的数组替换已有的小的数组。由于 HashMap 中的数组的长度是 2 的幂，阈值大小是数组的长度与负载因子的乘积，当键值对的数量超过阈值后，则进行扩容。在扩容的时候，会按照当前数组长度的 2 倍进行扩容，阈值也变为原来的 2 倍，完成以后需要重新计算键值对的位置，以将它们移动到合适的位置上去。
整体流程：
- 计算新的桶数组的容量 newCap 和新的阈值 newThr；
- 根据 newCap 创建新的桶数组，并进行初始化操作；
- 将旧桶数组中的
键值对映射到新的桶数组中：
- 如果节点类型是 TreeNode 类型，则需要将红黑树进行拆分；
- 如果节点类型是链表类型，按照原来的顺序进行分组，即组内节点的相对位置保持不变。
源码如下所示：
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
|
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果 table 不为空，则说明已经初始化过了
if (oldCap > 0) {
// 如果当前 table 的容量已经超过了最大容量，则无法进行扩充
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果没有超过最大值，则扩充为原来的 2 倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
// 初始化时，将 threshold 的值赋给 newCap
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 当调用无参的构造方法时，桶数组的容量为默认容量
// 阈值为默认容量与默认负载因子的乘积
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的 resize 上限，按照阈值的计算公式进行计算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的桶数组，并对桶数组进行初始化操作
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果旧的桶数组不为空，则遍历桶数组，将键值对映射到新的桶数组中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果桶上只有一个键值对，则直接插入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 在将键值对映射到新的桶数组中过程中，假如之前桶的引用是红黑树结构，则需要对红黑树进行拆分
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 如果之前是采用链表处理冲突的，则将链表节点按原顺序进行分组
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 将分组后的链表映射到新的桶中
// 原索引放到桶里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引 + oldCap 放到桶里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
|
JDK 1.7 中在扩容的时候需要重新计算 hash，这无疑增加了计算量，效率较低。而 JDK 1.8 则对其进行了改进，在扩充 HashMap 的时候，只需要看看原来的 hash 值新增的那个 bit 位是 1 还是 0 就好了，如果是 0 的话，则索引没变，如果是 1 的话，则索引变成原索引 + oldCap。
假设原始的容量是 16，原始的位置在 23，进行(n-1) & hash的时候，计算结果为00111；扩容后容量变为原来的两倍，即 32，再次计算(n-1) & hash得到10111。由于旧的容量16-1=15(1111)比新的容量32-1=31(11111)在比特位上多了一位，并且新增的这个比特位是1，所以新的索引将变成23+16。
这样做的好处是可以保证扩容后每个桶上的节点数必定小于或等于原来桶上的节点数，能够确保不会出现更严重的冲突。
这里需要注意的是：以上过程没有谈到链表的树化过程，即没有详细的谈到满足什么样的条件链表才转化成红黑树。当然，通过阅读红黑树（TreeNode）的源码可知，其中有两个重要的参数：TREEIFY_THRESHOLD = 8 和 MIN_TREEIFY_CAPACITY = 64。当桶数组的容量小于 64 时，会优先进行扩容，而不是树化操作。
所以，在扩容的过程中，链表转化成红黑树的操作（树化操作）要同时满足两个条件：
- 链表的长度 ≥ TREEIFY_THRESHOLD；
- 桶数组的容量 ≥ MIN_TREEIFY_CAPACITY。
当桶数组的容量较小时，在加入新节点的时候，产生哈希碰撞的概率会比较高，此时新节点会链接到链表的尾部，从而链表的长度较长。这个时候应该进行桶数组的扩容，而不是进行树化操作。链表较长的原因是由桶数组容量小造成的，当容量较小时，优先进行扩容可以避免一系列不必要的树化操作。从另一方面来说，在桶数组容量较小的时候，扩容会比较频繁，扩容时需要拆分红黑树并重新进行映射，所以尽量不要在桶数组容量比较小的情况下进行树化操作。
当然，在链表转化成红黑树的过程中，需要比较两个键对象的大小，首先会根据键与键之间的 hash 大小进行比较，如果相同的话则调用 Comparable 的 compareTo 方法进行比较，如果还是相同的话，则需要调用 tieBreakOrder 方法进行比较。
tieBreakOrder 方法相当于在竞技比赛中的加时赛一样，在正常情况下没有分出胜负，则再追加若干比赛，直至分出胜负。
链表转化成红黑树后，原链表中的顺序仍然会在红黑树中通过 next 和 prev 指针进行保留，目的是为了当红黑树需要进行链化操作的时候提供便利。
在扩容后，普通的节点需要重新进行映射，而红黑树当然也需要映射。在 HashMap 中，由于之前 next 和 prev 指针的保留，在对红黑树进行重新映射时，就可以直接按照链表的方式进行映射，而不是先将红黑树转化成链表之后再映射。这里有一个红黑树转链表的阈值UNTREEIFY_THRESHOLD = 6，在重新映射红黑树之后，会将红黑树拆分成两条由 TreeNode 组成的链表，如果链表长度小于等于 6，则将 TreeNode 类型的链表转化成普通的 Node 类型的链表。否则如果链表长度大于 6，则重新将 TreeNode 链表进行树化操作。
遍历
对于 HashMap 的遍历方法，一搬可以使用 map.keySet() 或 map.entrySet() 两种方式，在使用 foreach 进行遍历的时候，底层会转化成使用迭代器的方式。
使用 map.keySet() 进行遍历时，会获得 KeySet 对象，然后通过 KeySet 的迭代器进行遍历。这里需要注意一下遍历的过程：首先会找到包含链表引用的桶，然后对该桶指向的链表进行遍历，遍历完成后，继续寻找下一个包含链表引用的桶，再次对该桶指向的链表进行遍历，直至遍历完最后一个桶。
remove 方法
remove 方法首先需要定位到桶的位置，然后遍历链表找到键值对相等的节点，最后将其删除。如下所示：
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
|
// 在 remove 方法的内部调用了 removeNode 方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
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;
// 定位桶的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e;
K k;
V v;
// 如果键的值与链表的第一个节点相等，则将 node 指向该节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 如果当前是红黑树，则调用红黑树的方法查找需要删除的节点
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 如果当前是链表，则遍历链表，找到需要删除的节点
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 删除节点，并调整链表或红黑树的结构
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
|
参考