一、摘要
HashMap是使用频率高、用于保存键值对映射的容器类。自JDK8始HashMap引入红黑树，调整优化哈希算法，性能相比JDK7有进一步提升。同时，对JDK7中存在多线程操作导致死循环的问题进行修复。本文基于JDK10的源码进行介绍，代码格式进行轻微调整以便阅读。
相关阅读：
二、类签名
假设键值对能正确分散到不用桶中，那么访问get()和put()方法消耗时间近似为一个时间常数。哈希表全遍历性能与哈希桶(table长度)、Node节点(键值对)数量成比例。因此不合适把初始capacity设置太大，或负载因子值load-factor(默认0.75)设置过小。
1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
作为通用参数，默认负载因子能很好地平衡时间开销和内存开销之间关系。高负载因子值(如>0.75)能减少内存空间开支，但会增加查找的时间开销。如果在构建时正确指定哈希表初始容量，后期可完全避免重哈希操作，换句话说就是令插入操作更高效。
在类注释里提到几个技术点：
- 实现Map<K,V>接口；
- HashMap支持空键和空值；
- HashMap线程不安全；
与HashMap一并谈论较多的是开发于早期的HashTable，后来被建议使用前者替代，但并不妨碍两者横向比较：
- HashTable不支持键或值为null，而HashMap支持；
- HashTable线程安全，与
ConcurrentHashMap一样适用多线程； - 均实现Map<K,V>接口，具有相当的Map操作能力；
- 均不保证元素写入与读出顺序的一致性；
上文提到，HashMap本身不是线程安全的，可通过以下方式包装实例：
1
Map m = Collections.synchronizedMap(new HashMap(...));
或把HashMap替换为ConcurrentHashMap保证线程安全。
三、常量值
默认初始化大小
1
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
HashMap容纳元素最大容量
1
static final int MAXIMUM_CAPACITY = 1 << 30;
默认负载因子
1
static final float DEFAULT_LOAD_FACTOR = 0.75f;
从链表转换为红黑树的阈值
1
static final int TREEIFY_THRESHOLD = 8;
从红黑树退到链表的阈值
1
static final int UNTREEIFY_THRESHOLD = 6;
整个哈希表容量超过此值，且链表长度超过TREEIFY_THRESHOLD才树化
1
static final int MIN_TREEIFY_CAPACITY = 64;
四、数据成员
哈希桶表，长度为2的n次幂，不超过MAXIMUM_CAPACITY
1
transient Node<K,V>[] table;
已保存元素数量
1
transient int size;
结构性或元素数量变化总次数
1
transient int modCount;
下次表扩容阈值，计算自： threshold = capacity * load factor
1
int threshold;
负载因子
1
final float loadFactor;
五、节点
5.1 桶节点
数据成员Node<K,V>[] table，实现Map.Entry<K,V>接口。
节点中的成员变量 key ，和 key 对应的哈希值 hash 均使用 final 修饰。因为 key 的哈希值 hash 决定了该节点在哈希桶的索引，两者是一对一的关系。
假设，节点原始键为 keyA0 ，经过计算放入了索引为 0 的桶。随后，该节点的键修改为 keyB2，新哈希值对应桶为 2，但实际没有移动节点。那么就会出现，使用 keyB2 在桶 2 里找不到该节点，使用 keyA0 在桶 0 里由于键不相同而不能命中。最终，该节点将成为野节点飘在哈希表中。
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
static class Node<K,V> implements Map.Entry<K,V> {
// 节点键的哈希值，见小节：5.2 桶索引计算
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; }
// 这是Entry的哈希值，key和value分别取哈希值再进行异或
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// 存入的newValue会替换oldValue，并返oldValue
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
// 同一个对象
if (o == this) {
return true;
}
// 检查对象o是否为Map.Entry的子类
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o; // 显式类型转换
// 另一个Node的key-value与此Node的对比
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
哈希冲突解决方法常见有两种：开放地址法和拉链法。通过节点字段Node<K,V> next保存下一个节点的引用，推断出HashMap用拉链法处理哈希冲突问题。
5.2 桶索引计算
通常，判断Hash算法是否高效的方式，是看元素是否均匀分放到不同桶中，最好一个桶存放一个元素。即使存放更多元素，也希望每个桶能均匀存放相同数量。如果哈希算法不佳，导致一个桶中存放元素数量特别多，将严重影响存取性能。
为降低碰撞几率，需设置负载因子 loadFactor(默认值0.75)。假设用默认桶数量capacity(初始值16)，通过threshold = capacity * loadFactor可知当键值对数量超过12时触发扩容。
当然，通过单纯使用大量桶，即便不经优化的哈希算法，也能把元素相对均匀地放在不同桶中，类似通过空间换时间。而JDK的HashMap经过长期验证和修改，已在空间和时间两者取得平衡。
1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
过往的HashMap在桶数量较少时，连续值经过哈希运算很容易被分配到相同的桶，从而导致哈希碰撞。JDK8把哈希值高16位与低16位进行异或运算。在不降低性能的前提下充分利用有限的条件提高混淆度，尽力把元素分配到不用桶。
同时由源码可知key == null的元素一定会放在第一个哈希桶中。
下图展示hashCode高低位运算：
这种运算方式有以下好处：
- 满足速度、功效、位分散质量等条件；
- 避免使用%操作的同时，令位运算发挥更好效果；
- 避免性能损耗，开销较低
5.3 计算哈希表大小
通过给定值计算得相等或更大且大小为2^n的数值：
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;
}
下面假设cap为15，通过tableSizeFor()计算：
当流程进行到n|=n>>>4，后续步骤运算结果已经固定不变。参数cap为15计算得到最终结果为16。
六、成员方法
6.1 构造方法
指定初始容量值和负载因子值
1
2
3
4
5
6
7
8
9
10
11
12
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);
}
指定初始容量值，并使用默认负载因子值0.75。注意，初始容量值只能为非负数
1
2
3
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
构造空HashMap，默认初始容量为16，默认负载因子为0.75。其他参数使用默认值
1
2
3
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
通过给定Map创建新的HashMap。负载因子默认为0.75，容量值为足够保存m中键值对的大小。若m为null抛出NullPointerException
1
2
3
4
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
6.2 查询
根据键和哈希值查找对应键值对
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
final Node<K,V> getNode(int hash, Object key) {
// tab: 哈希表
// first: 桶内首节点
// n: 哈希桶索引
// k: 临时Node变量
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 &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 查找桶内其他节点
if ((e = first.next) != null) {
// 桶内节点以红黑树的方式保存，用红黑树的方法查找节点
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);
}
}
// 哈希表没有元素，或没有找到对应Node
return null;
}
返回key对应的value，若key没有对应映射则返回null
1
2
3
4
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
查询是否包含该键对应的值
1
2
3
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
6.3 插入
onlyIfAbsent 为true时新值不会替换已存在的旧值，evict 为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
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
final V putVal(int hash,
K key, V value,
boolean onlyIfAbsent,
boolean evict) {
// tab: 局部变量哈希表，即HashMap.table[];
// n: 哈希表长度，即tab[].length;
// i: 哈希桶索引，即(n - 1) & hash;
// p: 哈希桶首Node，即tab[i]
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table == null 或 table.length == 0，构建新哈希表
if ((tab = table) == null || (n = tab.length) == 0) {
// resize()里新哈希表会在方法内赋值给table
// 后返回哈希表引用并赋值给tab
n = (tab = resize()).length;
}
// 通过hash值确定哈希桶
if ((p = tab[i = (n - 1) & hash]) == null) {
// table[index]为null，创建新Node并放入数组该位置
tab[i] = newNode(hash, key, value, null);
} else {
// table[index]不为null，表示桶内已有至少一个Node
// e: 临时保存节点
// k: 桶首节点键
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {
// 确定节点p.key哈希与插入节点k.key哈希是否相同
e = p;
} else if (p instanceof TreeNode) {
// 桶首节点继承自TreeNode，调用红黑树的putTreeVal()
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
} else {
// 把节点插入到哈希桶链表队尾，FIFO。JDK7或之前版本是头插法
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 创建新节点，尾插法保存到链表尾
p.next = newNode(hash, key, value, null);
// 桶内节点数超过TREEIFY_THRESHOLD，需要转为红黑树，并退出迭代
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 找到key完全相同的节点，直接替换此节点的value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 相同key已有oldValue存在
if (e != null) {
V oldValue = e.value;
// onlyIfAbsent为true，当存在oldValue映射到key就不用newValue替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 返回已存在value，若value不存在则返回值为null
return oldValue;
}
}
// 增加修改次数
++modCount;
// 已保存元素数量超过阈值扩容哈希表
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
存入键值对，若此前已存在一个键值对，会返回上一个值，否则返回null
1
2
3
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
6.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
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// m为null则抛出NullPointerException
int s = m.size();
if (s > 0) {
if (table == null) {
// 如果本HashMap为null，用m的大小决定本HashMap的初始大小
float ft = ((float)s / loadFactor) + 1.0F;
// 检查是否超过大小限制
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 向上规整
if (t > threshold)
threshold = tableSizeFor(t);
} else if (s > threshold) {
// HashMap不为null，扩容一倍
resize();
}
// 依次遍历m的节点，存入本HashMap
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
// onlyIfAbsent为false
putVal(hash(key), key, value, false, evict);
}
}
}
调用方法 putMapEntries()，evict 参数为 true
1
2
3
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
6.5 扩容
通过此方法扩大哈希表容量，每次扩容都会增大table长度，已有节点需重哈希放入新哈希桶内。
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
final Node<K,V>[] resize() {
// 旧哈希表
Node<K,V>[] oldTab = table;
// 旧哈希表长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧表扩容阈值
int oldThr = threshold;
// 新容量，下一个阈值
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 超过数量上限则不再扩容
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {
// 扩充为原来两倍: 左移原值乘以2，右移原值除以2
newThr = oldThr << 1;
}
} else if (oldThr > 0) {
// 哈希表没有创建，但是已设定扩容阈值，则用该阈值去初始化
newCap = oldThr;
} else {
// aka: oldCap == 0 && oldThr == 0
// 哈希表既没有初始化，也没有设置初始阈值，则通过默认值进行初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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) {
// 在新哈希表中给元素e选桶
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) {
// 把红黑树的元素放到新表
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
} else {
// 桶内有多个元素且结构为链表，使用以下优化算法:
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) {
// 低位新哈希桶首个元素，e赋值给loHead
loHead = e;
} else {
// 低位新哈希桶后续元素，接到loTail的下一个位置
loTail.next = e;
}
// 调整loTail引用
loTail = e;
}
else {
if (hiTail == null) {
// 高位新哈希桶首个元素，e赋值给hiHead
hiHead = e;
} else {
// 高位新哈希桶后续元素，接到hiTail的下一个位置
hiTail.next = e
}
// 调整hiTail引用
hiTail = e;
}
} while ((e = next) != null);
// 链表存入低位哈希桶
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 链表存入高位哈希桶
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab; // 扩容完毕，返回新哈希表
}
下面举例一个旧表：
- 第一行是数值
oldCap，这个例子是4； - 第二行是每个数值的
e.hash； - 第三行是位运算
(e.hash & oldCap) == 0得出红色数字；
扩容后的新表，对比旧表中的数字：
- 位运算为
0的放在原桶索引位置oldIndex - 位运算为
1的放在新桶索引位置oldIndex+oldCap
于是从运算前旧表oldCap为4换新表newCap为8，且元素全部经过重哈希放入新桶中：
6.6 树化节点
把链表转换为红黑树：首先把链表的节点更换为红黑树节点，然后把整条链变形为红黑树
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
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 链表长度不超过MIN_TREEIFY_CAPACITY则仅进行扩容，不转换为红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 头节点hd，尾节点tl
TreeNode<K,V> hd = null, tl = null;
do {
// 更换链表节点为红黑节点链表
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 头节点非空，转换红黑节点链表为红黑树
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
6.7 删除
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
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，且桶首节点不为null
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;
// 匹配桶首节点
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);
}
}
// 遍历节点不为空，表示找到目标节点
// 若matchValue为true，则需同时匹配key-value
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 {
// 非链表头结点元素，相当于把node解除链接
p.next = node.next;
}
++modCount; // 哈希表修改次数加一
--size; // 移除一个元素
afterNodeRemoval(node);
return node;
}
}
return null;
}
matchValue 为 false，movable 为 true
1
2
3
4
5
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
6.8 清空
把桶首节点元素与哈希表解链接，桶内的链表或红黑树由虚拟机回收
1
2
3
4
5
6
7
8
9
10
11
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
// 已保存元素数量复位
size = 0;
// 链表或红黑树与哈希表解除连接
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
6.9 包含
如果是红黑树，则调用 find(int h, Object k, Class<?> kc)，本方法仅为链表所用。
查找 value 不像 key：
- key 能先算出其hash值并跳到对应桶进行查找；
- 而 value 只能遍历整张表所有元素逐一对比；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
// 依次遍历每个哈希桶
for (Node<K,V> e : tab) {
// 遍历哈希桶内所有节点
for (; e != null; e = e.next) {
// 查找是否存在保存了该value的节点e
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
// 哈希表为空，或没有找到匹配键值对
return false;
}
6.10 计算容量
- 哈希表不为空，返回哈希表长度；
- 哈希表为空但
threshold大于0，返回threshold； - 否则返回默认初始化大小16
1
2
3
4
5
final int capacity() {
return (table != null) ? table.length :
(threshold > 0) ? threshold :
DEFAULT_INITIAL_CAPACITY;
}
七、红黑树节点
TreeNode是HashMap的静态内部类
1
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
TreeNode的UML：
7.1 数据成员与构造方法
数据成员
1
2
3
4
5
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左子树
TreeNode<K,V> right; // 右子树
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 节点颜色: 红色或黑色
构造方法
1
2
3
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
7.2 获取根节点
沿着TreeNode.parent遍历到根节点
1
2
3
4
5
6
7
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
7.3 移动根节点
保证树的根节点一定是哈希桶的第一个元素
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
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
// 根节点非空、哈希表不为空、桶首节点不为空
if (root != null && tab != null && (n = tab.length) > 0) {
// 根据哈希值查哈希桶
int index = (n - 1) & root.hash;
// 获取桶首元素
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 桶首元素不是红黑树的根节点，则开始移动节点
if (root != first) {
// eq. root.next
Node<K,V> rn;
// 根节点赋值到桶首元素
tab[index] = root;
// 根节点的前一个节点
TreeNode<K,V> rp = root.prev;
// root.next不为空，把root.prev赋值给root.next.prev，相当于把root节点解除链接
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
// root.prev不为空，则root.prev.next = root.next，相当于把root节点解除链接
if (rp != null)
rp.next = rn;
// 桶首节点不为空，把根节点作为桶首节点的上一个节点
if (first != null)
first.prev = root;
// 原桶首节点现在作为root的下一个节点
root.next = first;
// 首节点没有prev
root.prev = null;
}
// 检查处理后的红黑树树是否符合标准
assert checkInvariants(root);
}
}
7.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
32
33
34
35
36
37
38
39
40
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
// 左叶子pl，有叶子pr
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) {
// 节点的哈希值大于需查找的哈希值h，h和左叶子比较
p = pl;
} else if (ph < h) {
// 节点的哈希值小于需查找的哈希值h，h和右叶子比较
p = pr;
} else if ((pk = p.key) == k || (k != null && k.equals(pk))) {
// hash值相同，且value也相同，当前节点就是要查找的节点，返回
return p;
} else if (pl == null) {
// 左叶子为空，则切换到右叶子
p = pr;
} else if (pr == null) {
// 右叶子为空，则切换到左叶子
p = pl;
} else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0) {
// p.hash == h && p.key != k && pl != null && pr != null
// 通过compareComparables比较pk和k大小，dir小于0，走左子树，否则走右子树
p = (dir < 0) ? pl : pr;
} else if ((q = pr.find(h, k, kc)) != null) {
// 进入右叶子递归查找
return q;
} else {
// 切换到左叶子，进入左叶子递归查找
p = pl;
}
} while (p != null);
// 整棵树查找结束，没有找到目标节点，返回null
return null;
}
1
2
3
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
7.5 大小比较
节点的键没有实现Comparable接口，或键通过compareTo比较相同时，需要通过此方法比较大小
1
2
3
4
5
6
7
8
9
10
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
// 通过类名进行compareTo比较，不同则用此结果
// a为null，或b为null，或两个对象类名对比相同，就用hashCode值比较，小于等于返回-1，否则返回1
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
7.6 构建红黑树
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
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null; // 根节点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
// 正在遍历节点的下一个节点
next = (TreeNode<K,V>)x.next;
// 置空左右节点
x.left = x.right = null;
// 根节点为空，把当前节点作为根节点，且节点颜色为黑色
if (root == null) {
x.parent = null;
x.red = false;
root = x;
} else { // 已存在根节点
K k = x.key; // 当前节点的key
int h = x.hash; // 当前节点的value
Class<?> kc = null; // key的类型，KeyClass
for (TreeNode<K,V> p = root;;) { // 从根节点开始遍历
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) // p.hash大于节点x.hash，放在节点p左侧
dir = -1;
else if (ph < h) // p.hash小于节点x.hash，放在节点p右侧
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 先通过compareComparables比较，当dir == 0，
// 还需要进行下面多一轮比较决定放在左子树还是右子树
dir = tieBreakOrder(k, pk);
// 到这里dir只可能是1或-1
TreeNode<K,V> xp = p; // xp意为：xParent
// 如果左子树或右子树为空，就地插入，否则进入下一次for循环查找
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0) {
xp.left = x; // 放在父节点左子树
} else {
xp.right = x; // 放在父节点右子树
}
root = balanceInsertion(root, x);
break;
}
}
}
}
// 把红黑树根节点放在哈希桶首位
moveRootToFront(tab, root);
}
7.7 去树化
把红黑树转换为链表形式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
final Node<K,V> untreeify(HashMap<K,V> map) {
// 链表头指针hd，链表尾指针tl
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
// 把红黑树节点更换为普通链表节点
Node<K,V> p = map.replacementNode(q, null);
// 然后把所有节点按照遍历的顺序依次串起来
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd; // 返回一条链表
}
7.8 插入树节点
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
// @param map HashMap
// @param tab 哈希桶
// @param h 元素哈希值
// @param k 元素key
// @param v 元素value
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
// 查找根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
// 从根节点开始遍历，p为当前节点，<k,v>为对比节点
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1; // 对比元素比当前节点的哈希值大，进入左子树比较
else if (ph < h)
dir = 1; // 进入右子树比较
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p; // 当前节点的key和value都和元素相同，即当前节点就是需要找的节点
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
// 分别从左子树和右子树找
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;
}
// 没有遍历到和哈希值h相同的节点
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
// 创建新节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x; // 作为左子树
else
xp.right = x; // 作为右子树
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 插入平衡，并调整根节点到树顶
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
7.9 移除树节点
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
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
tab[index] = first = succ;
else
pred.next = succ;
if (succ != null)
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
root = root.root();
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // 退化
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // 查找继承节点
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // 交换颜色
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
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;
}
}
if (movable)
moveRootToFront(tab, r);
}
7.10 分割
把红黑树分割为高位桶和低位桶，如果分割后桶内元素数量较少，桶内哈希表会退化为链表。
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
// @param map 哈希表
// @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;
// 重链接到高位列表或低位列表，且保持基本顺序
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
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;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD) // 低位桶元素数量少于UNTREEIFY_THRESHOLD
tab[index] = loHead.untreeify(map); // 桶内元素减少，去树化
else {
tab[index] = loHead;
if (hiHead != null)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map); // 桶内元素减少，去树化
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
7.11 翻转左子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
// r = p.right
// pp = p.parent
// rl = p.right.left
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) { // 左旋节点的右子树不为空
if ((rl = p.right = r.left) != null) // 把p.right.left = p.right
rl.parent = p; // p.right.left.parent = p
if ((pp = r.parent = p.parent) == null)
(root = r).red = false; // 根节点颜色为黑
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
7.12 翻转右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
// l = p.left
// pp = p.parent
// lr = p.left.right
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) { // 右旋节点的左子树不为空
if ((lr = p.left = l.right) != null) // 把p.left.right = p.left
lr.parent = p; // p.left.right.parent = p
if ((pp = l.parent = p.parent) == null)
(root = l).red = false; // 根节点颜色为黑
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
7.13 平衡插入
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
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// 新插入节点为红节点
x.red = true;
// xp： 当前节点的父节点
// xpp： 当前节点的爷爷节点
// xppl：当前节点的左叔节点
// xppr：当前节点的右叔节点
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// 节点为根节点，更根据红黑树条件来说，根节点一定为黑色
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) { // 父节点是爷爷节点的左子树
if ((xppr = xpp.right) != null && xppr.red) { // 右叔叔节点非空，且为红色
xppr.red = false; // 右叔叔为黑色
xp.red = false; // 父节点为给色
xpp.red = true; // 爷爷节点的红色
x = xpp; // 爷爷作为下轮处理的节点
}
else {
// 该节点为父节点的右节点
if (x == xp.right) { // 当前节点是父节点的右子树
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent; // 获取爷爷节点
}
// 父节点不为空
if (xp != null) {
xp.red = false; // 父节点为黑色
if (xpp != null) {
xpp.red = true; // 爷爷节点为红色节点
root = rotateRight(root, xpp); // 爷爷节点右旋
}
}
}
}
else {
if (xppl != null && xppl.red) { // 左叔节点非空且为红色
xppl.red = false; // 左叔节点为红色
xp.red = false; // 父节点为黑色
xpp.red = true; // 爷爷为红色
x = xpp;
}
else { // 左叔节点为空，或为黑色
if (x == xp.left) { // 当前节点为做孩子
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false; // 黑色父节点
if (xpp != null) {
xpp.red = true; // 爷爷节点为红色
root = rotateLeft(root, xpp);
}
}
}
}
}
}
7.14 平衡删除
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
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (x.red) {
x.red = false;
return root;
}
else if ((xpl = xp.left) == x) {
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;
else {
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
}
else {
if (sr == null || !sr.red) {
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
}
else { // 对称
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
7.15 递归检查
检查操作完成的红黑树是否合法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
八、参考链接
- 美团技术团队 - Java 8系列之重新认识HashMap
- I-team - 死磕Java之聊聊HashMap源码(基于JDK1.8)
- StackOverflow - Does HashTable maintains the insertion order?
- StackOverflow - Why Hashtable does not allow null keys or values?
- 知乎 - JoonWhee - HashMap讲解(上)
- CSDN - chenssy - 【死磕Java并发】—–J.U.C之ConcurrentHashMap红黑树转换分析