概述
从本文你可以学习到：
- 什么时候会使用 HashMap ？他有什么特点？
- 你知道 HashMap 的工作原理吗？
- 你知道 get 和 put 的原理吗？
equals() 和 hashCode() 的都有什么作用？
- 你知道 hash 的实现吗？为什么要这样实现？
- 如果 HashMap 的大小超过了负载因子 (load factor) 定义的容量，怎么办？
- 为什么 HashMap 的容量是 2 的 n 次幂的形式？
在说明这些问题的同时， 我从 JDK7 —— JDK8 的 HashMap 的变化来说明开发人员对这个数据结构的优化，重点放在了 put() 函数 和 resize() 函数，还结合了《码出高效》这本书指出了 HashMap 在并发情况下表现出来的问题。
注意：源码可能与 JDK 中实际代码略有不同， 这里面 JDK7 版以《码出高效》为准，JDK8 版本以网络版本为准，意在说明某个函数功能， 便于理解。
两个重要参数说起
在HashMap中有两个很重要的参数，容量(Capacity)和负载因子 (Load factor) 。
Capacity 就是 bucket 的大小，Load factor就是 bucket 填满程度的最大比例。如果对迭代性能要求很高的话，不要把 capacity 设置过大，也不要把 load factor 设置过小。当 bucket 中的 entries 的数目大于 capacity *load factor 时，就需要调整 bucket 的大小为当前的2倍。
put函数的实现
put函数大致的思路为：
- 对key的
hashCode() 做 hash ，然后再计算 index ;
- 如果没碰撞直接放到 bucket 里；
- 如果碰撞了，以链表的形式存在 buckets 后；
- 如果碰撞导致链表过长 (大于等于
TREEIFY_THRESHOLD )，就把链表转换成红黑树；
- 如果节点已经存在就替换 old value (保证 key 的唯一性)；
- 如果 bucket 满了 (超过
load factor * current capacity)，就要 resize。
具体代码的实现如下：
JDK7 的 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
| public V put(K key, V value) {
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size++ >= threshold) && (null != table[bucketIndex])){
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash. K key, V value, int bucketIndex){
Entry<K,V> e = table[bucketIndex]; （***）
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
size++;
}
|
关于并发的问题：
如上源码， 在 createEntry() 方法中，新添加的元素直接放在 slot 槽（ slot 哈希槽，table[i] 这个位置）使新添加的元素在下一次提取后可以更快的被访问到。 如果两个线程同时执行 (***) 处时， 那么一个线程的赋值就会被另一个覆盖掉， 这是对象丢失的原因之一。 我们构造一个 HashMap 集合，把所有元素放置在同一个哈希桶内， 达到扩容条件后，观察一下 resize() 方法是如何进行数据迁移的。示例代码和图可参考《码出高效》P204。
JDK8 的 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
| 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;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e;
K k;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
|
可以看出，JDK 7 是先对 size++ 进行检查， 如果超过阈值， 则扩容，最后把节点放入 table。
而 JDK 8 相反，先把节点放入， 放入后的 size 若超出， 则扩容。
hash 与 hashCode()
在 get 和 put 的过程中，计算下标时，先对 hashCode 进行 hash 操作，然后再通过 hash 值进一步计算下标，如下图所示：
hash计算下标
关于 hash 函数 与 hashCode 的关系，这里，为了避免碰撞，JDK7 进行了四次扰动，JDK8 简化了这个操作，只是高低位做了异或，但核心思想都是增强 hash 中各位的相关性，减少碰撞。
JDK7 中的 hash
1
2
3
4
5
6
7
8
9
10
11
12
| final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
|
JDK8 中的 hash
1
2
3
4
| static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
|
扩容（超级重要！）
JDK7 的扩容分析
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
| void resize(int newCapacity) {
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
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;
}
}
}
|
关于并发的问题：
如果 resize 完成， 执行了 table = newTable ，则后续的元素就可以在新表上进行插入操作。如果多个线程同时执行了 resize ，每个线程又都会 new Entry[newCapcity] 这是线程内的局部数组对象，线程之间是不可见的。迁移完成后，resize 的线程会赋值给 table 线程共享变量，从而覆盖其他线程的操作，因此在“新表”中进行插入操作的对象会被无情抛弃。总结一下， HashMap 在高并发场景中， 新增对象丢失原因是：
- 并发赋值时被覆盖。
- 已遍历区间新增元素会丢失。
- “新表被覆盖”。
- 迁移丢失。在迁移过程中， 有并发时， next 被提前置成 null。
JDK8 的扩容分析
例如我们从 16 扩展为 32 时，具体的变化如下所示：
resize引起的hash
因此元素在重新计算 hash 之后，因为 n 变为 2 倍，那么 n-1 的 mask 范围在高位多 1bit (红色)，因此新的 index就会发生这样的变化：
index
因此，我们在扩充 HashMap 的时候，不需要重新计算 hash ，只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是0的话索引没变，是 1 的话索引变成 “原索引 + oldCap”。可以看看下图为 16 扩充为 32 的 resize 示意图：
resize
这个设计确实非常的巧妙，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1bit 是 0 还是 1 可以认为是随机的，因此 resize 的过程，均匀的把之前的冲突的节点分散到新的 bucket 了。
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
| 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)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
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)
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)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
|
此段代码来源：CSDN博客，采取了一些删改，注释太多太影响阅读。。
JDK 7 与 JDK 8 中关于 HashMap的对比
- JDK 8 为红黑树 + 链表 + 数组的形式，当桶内元素大于 8 时，便会树化；
- hash 值的计算方式不同 (jdk 8 简化)；
- 1.7 table 在创建 hashmap 时分配空间，而 1.8 在 put 的时候分配，如果 table 为空，则为 table 分配空间；
- 在发生冲突，插入链中时，7 是头插法，8 是尾插法；
- 在 resize 操作中，7 需要重新进行 index 的计算，而 8 不需要，通过判断相应的位是 0 还是 1，要么依旧是原 index，要么是 oldCap + 原 index。
总结
我们现在可以回答开始的几个问题，加深对 HashMap 的理解：
- 什么时候会使用 HashMap？他有什么特点？
是基于 Map 接口的实现，存储键值对时，它可以接收 null 的键值，是非同步的，HashMap 存储着 Entry(hash, key, value, next) 对象。
- 你知道 HashMap 的工作原理吗？
通过 hash 的方法，通过 put 和 get 存储和获取对象。存储对象时，我们将 K / V 传给 put 方法时，它调用 hashCode 计算 hash 从而得到 bucket 位置，进一步存储，HashMap 会根据当前 bucket 的占用情况自动调整容量 (超过 Load Facotr 则 resize 为原来的 2 倍)。获取对象时，我们将 K 传给 get ，它调用 hashCodeO() 计算 hash 从而得到 bucket 位置，并进一步调用 equals() 方法确定键值对。如果发生碰撞的时候，Hashmap 通过链表将产生碰撞冲突的元素组织起来，在 Java 8 中，如果一个 bucket 中碰撞冲突的元素超过某个限制 (默认是 8 )，则使用红黑树来替换链表，从而提高速度。
- 你知道 get 和 put 的原理吗？equals() 和 hashCode() 的都有什么作用？
通过对 key 的 hashCode() 进行 hashing，并计算下标 ( (n-1) & hash )，从而获得 buckets 的位置。如果产生碰撞，则利用 key.equals() 方法去链表或树中去查找对应的节点
- 你知道hash的实现吗？为什么要这样实现？
在 Java 1.8 的实现中，是通过 hashCode() 的高 16 位异或低 16 位实现的：(h =k.hashCode()) ^ (h >>> 16) ，主要是从速度、功效、质量来考虑的，这么做可以在 bucket 的 n 比较小的时候，也能保证考虑到高低 bit 都参与到 hash 的计算中，同时不会有太大的开销。
- 如果 HashMap 的大小超过了负载因子 ( load factor ) 定义的容量，怎么办？
如果超过了负载因子 (默认0.75)，则会重新 resize 一个原来长度两倍的 HashMap，并且重新调用 hash 方法。
- 为什么 capcity 是 2 的幂？
因为 算 index 时用的是(n-1) & hash，这样就能保证 n-1 是全为 1 的二进制数，如果不全为 1 的话，存在某一位为 0，那么 0，1与 0 与的结果都是 0，这样便有可能将两个 hash 不同的值最终装入同一个桶中，造成冲突。所以必须是 2 的幂。
更多数据结构
请访问我的博客-数据结构分类
