深入分析HashMap
1. 传统 HashMap 的缺点
JDK 1.8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。
当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个 时候 HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了优势。
针对这种情况,JDK 1.8 中引入了红黑树(查找时间复杂度为 O(logn))来优化这个问题。
[TOC]
2. JDK1.8中HashMap的数据结构
HashMap 是数组+链表+红黑树(JDK1.8 增加了红黑树部分)实现的
2.1. 新增红黑树
1 |
|
2.2. 红黑树的三个关键参数
TREEIFY_THRESHOLD | UNTREEIFY_THRESHOLD | MIN_TREEIFY_CAPACITY |
---|---|---|
一个桶的树化阈值 | 一个树的链表还原阈值 | 哈希表的最小树形化容量 |
static final int TREEIFY_THRESHOLD = 8 | static final int UNTREEIFY_THRESHOLD = 6 | static final int MIN_TREEIFY_CAPACITY = 64 |
当桶中元素个数超过这个值时需要使用红黑树节点替换链表节点 | 当扩容时,桶中元素个数小于这个值就会把树形的桶元素 还原(切分)为链 表结构 | 当哈希表中的容量大于这个值时,表中的桶才能进行树形化 否则桶内元素太多时会扩容,而不是树形化 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD |
2.3. 新增操作: 桶的树形化 treeifyBin()
- 在 Java 8 中,如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 ),就使用
红黑树来替换链表,从而提高速度。 这个替换的方法叫 treeifyBin() 即树形化。
1 |
|
上述操作做了这些事:
根据哈希表中元素个数确定是扩容还是树形化
如果是树形化遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系
然后让桶第一个元素指向新建的树头结点,替换桶的链表内容为树形内容
3. 分析 HashMap 的 put 方法
3.1. HashMap 的 put 方法执行过程可以通过下图来理解
判断键值对数组 table[i]是否为空或为 null,否则执行 resize()进行扩容;
根据键值 key 计算 hash 值得到插入的数组索引 i,如果 table[i]==null,直接新建节点添加, 转向6,如果 table[i]不为空,转向3;
判断 table[i]的首个元素是否和 key 一样,如果相同直接覆盖 value,否则转向4,这里的相 同指的是 hashCode 以及 equals;
判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树,如果是红黑树,则直接在树中插 入键值对,否则转向5;
遍历 table[i],判断链表长度是否大于 8,大于 8 的话把链表转换为红黑树,在红黑树中执 行插入操作,否则进行链表的插入操作;遍历过程中若发现 key 已经存在直接覆盖 value 即可;
插入成功后,判断实际存在的键值对数量 size 是否超多了最大容量 threshold,如果超过, 进行扩容。
JDK1.8HashMap 的 put 方法源码
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
62public V put(K key, V value) {
// 对 key 的 hashCode()做 hash
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:tab 为空则创建
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
// 步骤2:计算 index,并对 null 做处理 if((p=tab[i=(n-1)&hash])==null)
tab[i] = newNode(hash, key, value, null);
else{
Node<K, V> e;
K k;
// 步骤3:节点 key 存在,直接覆盖 value if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤4:判断该链为红黑树
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);
//链表长度大于 8 转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
{
treeifyBin(tab, hash);
}
break;
}
// key 已经存在直接覆盖 value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步骤6:超过最大容量 就扩容
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict);
return null;
}JDK1.7HashMap 的 put 方法源码
1 |
|
3.2. HashMap 在 JDK 1.8 中新增的操作: 红黑树中查找元素 getTreeNode()
JDK1.8 中 hashMap getNode 操作
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/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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;
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);
}
}
return null;
}- HashMap 的查找方法是 get(),它通过计算指定 key 的哈希值后,调用内部方法 getNode();
- 这个 getNode() 方法就是根据哈希表元素个数与哈希值求模(使用的公式是 (n - 1)
&hash)得到 key 所在的桶的头结点,如果头节点恰好是红黑树节点, 就调用红黑树节点的 getTreeNode() 方法,否则就遍历链表节点。
- getTreeNode 方法使通过调用树形节点的 find()方法进行查找:
1
2
3final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}由于之前添加时已经保证这个树是有序的,因此查找时基本就是折半查找,效率很高。
这里和插入时一样,如果对比节点的哈希值和要查找的哈希值相等,就会判断 key 是否相
等,相等就直接返回;不相等就从子树中递归查找。
3.3. JDK1.8 VS JDK1.7 扩容机制
- 下面举个例子说明下扩容过程。假设了我们的 hash 算法就是简单的用 key mod 一下表的大小(也就是数组的长度)。其中的哈希桶数组 table 的 size=2, 所以 key = 3、7、5,put 顺 序依次为 5、7、3。在 mod 2 以后都冲突在 table[1]这里了。这里假设负载因子 loadFactor=1, 即当键值对的实际大小 size 大于 table 的实际大小时进行扩容。接下来的三个步骤是哈希桶 数组 resize 成 4,然后所有的 Node 重新 rehash 的过程。
- 下面我们讲解下 JDK1.8 做了哪些优化。经过观测可以发现,我们使用的是 2 次幂的扩展(指长 度扩为原来 2 倍),所以,元素的位置要么是在原位置,要么是在原位置再移动 2 次幂的位置。 看下图可以明白这句话的意思,n 为 table 的长度,图(a)表示扩容前的 key1 和 key2 两种 key 确定索引位置的示例,图(b)表示扩容后 key1 和 key2 两种 key 确定索引位置的示例, 其中 hash1 是 key1 对应的哈希与高位运算结果。
元素在重新计算 hash 之后,因为 n 变为 2 倍,那么 n-1 的 mask 范围在高位多 1bit(红色),因 此新的 index 就会发生这样的变化:
因此,我们在扩充 HashMap 的时候,不需要像 JDK1.7 的实现那样重新计算 hash,只需要看 看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了,是 0 的话索引没变,是 1 的话索引变成“原 索引+oldCap”,可以看看下图为 16 扩充为 32 的 resize 示意图
这个设计确实非常的巧妙,既省去了重新计算 hash 值的时间,而且同时,由于新增的 1bit 是 0 还是 1 可以认为是随机的,因此 resize 的过程,均匀的把之前的冲突的节点分散到新的 bucket 了。这一块就是 JDK1.8 新增的优化点。
参考资料:
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!