大厂面试爱问的HashMap死锁问题，看这一篇就够了
- JDK 1.7 HashMap源码分析
- put（）方法
- addEntry（）方法
- resize（）方法
- transfer（）方法（重点）
- 死锁演示
- 如何规避
- 使用Hashtable 或 ConcurrentHashMap
- JDK1.8的升级和仍存在的死锁问题
- 升级内容
- 仍可能存在死锁问题
经历过大厂面试或者有所了解的同学都应该知道，HashMap是面试时面试官特别喜欢的问题，除了HashMap的扩容方式，为什么扩容的2的次幂等以外，还经常会问到HashMap死锁的相关问题。最常出现的死锁问题的是在JDK 1.7版本，为了理解死锁问题产生的原因我们来从源码和一些相关概念开始说起。
JDK 1.7 HashMap源码分析
put（）方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(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;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
put（）方法可以总结成以下四个过程：
-
特殊 key 值处理，key 为 null；(在JDK 1.7版本 key可以为null，如果是第一次put会被用头插法存在bucket[0]的位置，在JDK1.8以后则会直接报异常)
-
计算 table 中目标 bucket 的下标；
int i = indexFor(hash, table.length); indexFor的源码如下： static int indexFor(int h, int length) { return h & (length-1);}
实际上是目标hash值和bucket和bucket长度-1，也就是length-1进行“与”运算，当bucket的长度只能是2的次幂的的时候，其实也就相当于目标值对bucket长度进行取余运算，只不过这样效率更高
3. 指定目标 bucket，遍历 Entry 结点链表，若找到 key 相同的 Entry 结点，则做替换；
4. 若未找到目标 Entry 结点，则新增一个 Entry 结点
大家可能不太懂的一个操作是modCount，它是一个记录 map 新增/删除 k-v 对次数的变量。它的主要作用，是对 Map 的iterator()操作做一致性校验，如果在 iterator 遍历操作的过程中，map 的数值有变化，直接抛出ConcurrentModificationException异常。
addEntry（）方法
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);
}
- 查看当前的size是否超过了我们设定的阈值threshold，如果超过且当前的 bucket 下标有链表存在，需要resize()
- bucket扩容为原来两倍，重新计算hash存入不同的bucket
- 采用头插法新增节点
resize（）方法
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
}
- bucket扩容为原来的两倍
- 重新计算hash，数据迁移
transfer（）方法（重点）
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;
}
}
}
- 对链表上的每一个节点遍历，当前节点e不为空时，e的next 指向e在当前bucket下的后一个（e指向的是没有转移的时候的下一个）
- 重新计算e的hash，计算新的对应的bucket下标
- 先将 e.next 指向新 Hash 表的第一个元素，newTable[i]上的值赋给e元素的next属性，e属性再赋值给newTable[i]，这样newTable[i]上的链表新的元素都会靠前，之前的元素相当于后移了
（假如转移前链表顺序是1->2->3，那么转移后就会变成3->2->1）
死锁演示
我们以链表a->b->c->null为例，两个线程 A 和 B，分别做扩容操作。
原表：
A 和 B 各自新增了一个新的哈希 table，在线程 A 已做完扩容操作后，线程 B 才开始扩容。此时对于线程 B 来说，当前结点e指向 a 结点，下一个结点e.next仍然指向 b 结点（此时在线程 A 的链表中，已经是c->b->a的顺序）。按照头插法，哈希表的 bucket 指向 a 结点，此时 a 结点成为线程 B 中链表的头结点，如下图所示：
a 结点成为线程 B 中链表的头结点后，下一个结点e.next为 b 结点。既然下一个结点e.next不为 null，那么当前结点e就变成了 b 结点，下一个结点e.next变为 a 结点。继续执行头插法，将 b 变为链表的头结点，同时 next 指针指向旧的头节点 a，如下图：
此时，下一个结点e.next为 a 节点，不为 null，继续头插法。指针后移，那么当前结点e就成为了 a 结点，下一个结点为 null。将 a 结点作为线程 B 链表中的头结点，并将 next 指针指向原来的旧头结点 b，如下图所示：
此时，已形成环链表。同时下一个结点e.next为 null，流程结束。
图片引用：https://blog.csdn.net/valada/article/details/103359320?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159811189919195264506720%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=159811189919195264506720&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_ecpm_v3~pc_rank_v4-2-103359320.first_rank_ecpm_v3_pc_rank_v4&utm_term=hashmap面试就够了&spm=1018.2118.3001.4187
如何规避
使用Hashtable 或 ConcurrentHashMap
Hashtable 或 ConcurrentHashMap都是线程安全的，不过Hashtable效率低下，ConcurrentHashMap采用了分段锁，效率更高
JDK1.8的升级和仍存在的死锁问题
升级内容
-
由数组+链表的结构改为数组+链表+红黑树。
-
扩容方法从头插法改成了尾插法，元素要么是在原位置，要么是在原位置再移动2次幂的位置，且链表顺序不变
仍可能存在死锁问题
-
多线程put的时候可能导致元素丢失
-
put非null元素后get出来的却是null
