一, JDK1.7 中 HashMap 扩容死锁问题
我们首先来看一下 JDK1.7 中 put 方法的源码
我们打开 addEntry 方法如下, 它会判断数组当前容量是否已经超过的阈值, 例如假设当前的数组容量是 16, 加载因子为 0.75, 即超过了 12, 并且刚好要插入的索引处有元素, 这时候就需要进行扩容操作, 可以看到 resize 扩容大小是原数组的两倍, 仍然符合数组的长度是 2 的指数次幂
我们再进入 resize 方法如下, 它首先会对之前的数组容量进行判断, 看是否已经达到了数组最大容量, 如果没有, 后面会进行数组的转移操作, 即 transfer 方法
我们先来看一下进行转移操作的方法, JDK1.7 中 HashMap 存在死锁问题的原因也主要集中在这
假设我们有这样一个 HashMap, 如下
现在需要对其进行扩容操作 (假设已经达到扩容阈值, 忽略其他元素)
根据源码中, 此时会产生连个指针, 一个 e 指针, 指向当前节点, 另一个节点为 next, 指向 e 的下一个节点, 即 e.next, 如下图所示
源码中的 if 判断实现的是重哈希, indexFor 操作实现的是重新定位当前节点在新数组中的位置, 我们来看一下新数组
假设此时还是定位到数组 3 号位
接着看源码
e.next = newTable[i]
, 即将 e.next 节点指向了扩容后数组的的 3 号位, 因为这是刚创建的新数组, 还是空数组, 因此 e.next = null, 此时指向如下图所示
接着执行下一步 newTable[i] = e, 即将当前节点 e 赋值给刚在新数组找到的新节点, 如下图所示
最后一步 e = next, 即:
至此, while 循环的第一遍结束, 此时 e 指向杨过这个节点, 很明显不为空, 会进行第二次循环, 重复以上操作, 最后产生的效果为:
可以杨过和小龙女两个节点的位置发生了改变了 (这也是 HashMap 为什么无序的原因)
以上为单线程下进行扩容, 并不会产生线程安全问题, 但是如果是多线程进行扩容呢
我们假设现在有两个线程同时对数组扩容, 每个线程都存在两个指针, 线程 1 为 e 和 next, 线程 2 为 e2 和 next2
假设此时线程 2 运行到如下红色框中的代码时线程阻塞了, 对应上图则是 e2 指向了小龙女, next2 指向了杨过
因为线程 2 被阻塞了, 其后面的代码就没法继续执行了, 而此时线程 1 也进入方法进行扩容, 扩容后的结果就是单线程时扩容后的结果, 如上图所示, 此时相比于扩容前的 HashMap, 杨过和小龙女位置已经调换
此时刚刚被阻塞的的线程 2 被唤醒了, 注意此时线程 2 中两个指针的指向, 如下图所示
此时线程 2 执行
e.next = newTable[i]
这一行, 即 e2 的下一个节点指向其扩容的新数组, 如下图所示:
再执行下面的 newTable[i] = e, 即将小龙女这个节点填入数组中, 如下
现在指向最后一步 e = next, 由于此时 next2 还指向线程 1 扩容后数组中的杨过节点, 因此现在 e2 和 next2 都指向杨过节点
接着第二次循环, 结果如下:
现在进行第三次循环, 仍然是
e.next = newTable[i]
这一行, 此时的 newTable[i] 是杨过节点, 因此这步的结果就是小龙女节点又指回了杨过节点
此时又执行 e = newTable[i], 结果如下:
最后一步执行完后两个指针都指向了空
此时新扩容的数组也形成了一个环
以上就是 HashMap 扩容时死锁的原因
二, JDK1.8 中对 HashMap 的优化
先看一下 JDK8 中 HashMap 源码
- 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;
- // 如果是 LinkedHashMap 实现的话, 会使用红黑树作为数据结构, 调用其 putTreeVal()
- else if (p instanceof TreeNode)
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- else {
- for (int binCount = 0; ; ++binCount) {
- // 找到最后一个 next 不会 null 的位置, 插入元素
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- // 如果树的深度大于阀值 - 1, 则重新调整, 平衡二叉树
- if (binCount>= TREEIFY_THRESHOLD - 1) // -1 for 1st
- treeifyBin(tab, hash);
- break;
- }
- // 找到元素存在, 直接进入后续更新
- 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;
- // LinkedHashMap 预留
- afterNodeAccess(e);
- return oldValue;
- }
- }
- // 修改 + 1
- ++modCount;
- // 容量超过阀值, 扩容
- if (++size> threshold)
- resize();
- // LinkedHashMap 预留
- afterNodeInsertion(evict);
- return null;
- }
当容量超过阈值时进行扩容操作, 我们进入 resize 方法, 源码如下
- /**
- * Initializes or doubles table size. If null, allocates in
- * accord with initial capacity target held in field threshold.
- * Otherwise, because we are using power-of-two expansion, the
- * elements from each bin must either stay at same index, or move
- * with a power of two offset in the new table.
- *
- * @return the table
- */
- 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; // double threshold
- }
- else if (oldThr> 0) // initial capacity was placed in threshold
- newCap = oldThr;
- else { // zero initial threshold signifies using defaults
- 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 { // preserve order
- // 这里定义了两组头和尾指针
- Node<K,V> loHead = null, loTail = null;
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- do {
- next = e.next;
- // 使用当前结点的 hash 值与就数组的长度做与运算, 如果是 0 则是低位
- if ((e.hash & oldCap) == 0) {
- if (loTail == null)
- loHead = e;
- else
- loTail.next = e;
- loTail = e;
- }
- else {// 如果是 16 则是高位
- 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;
- }
可以看出, 当对数组进行迁移时, 这里定义了两组指针, 分别是低位头和尾, 高位头和尾, 举个例子就能看出为什么要这么做, 假设旧数组的长度为 16
数组长度 0000 0000 0000 1000
hash 值 0101 1011 1111 1011 (随机)
与运算结果只有两种
- 0000 0000 0000 1000 ---------16
- 0000 0000 0000 0000 ---------0
与运算的结果只存在 0 和 16 两种可能, 接着往下面的源码看, 如果是 0 则是低位, 如果是 16 则是高位
这里就假设与运算的结果为 0, 那么数组的指向则变成这样:
接着执行下面的代码, 将低位头部 loHead 赋值给新数组, 在前面我们可以看到 j 为遍历旧数组的索引, 这样, 就将高位的所有结点都移动到了新数组
接下来,
newTable[j] = loHead
将高位的尾部置空, 再将高位的头部放到新数组的 j + oldCap 索引处 (当前索引 + 旧数组的长度), 比如说现在的索引是 3, 再加上数组长度 16, 最后就是将高位放到新数组的索引为 19 的地方去, 这样, 位置图就成了如下:
到此, 转移结束, 避免了 JDK1.7 的使用两个指针可能出现的死环问题
总结: 在 JDK1.8 之后, HashMap 底层的数组扩容后迁移的方法进行了优化. 把一个链表分成了两组, 分成高为和低位分别去迁移, 避免了死环问题. 而且在迁移的过程中并没有进行任何的 rehash(重新记算 hash), 提高了性能. 它是直接将链表给断掉, 进行几乎是一个均等的拆分, 然后通过头指针的指向将整体给迁移过去, 这样就减小了链表的长度.
来源: https://www.cnblogs.com/baolingye/p/11688667.html