文档章节

HashMap死循环及JDK1.8的resize()如何维护链表顺序

那只是一股逆流
 那只是一股逆流
发布于 2017/03/01 20:07
字数 1435
阅读 297
收藏 0

HashMap死循环

我记得第一次听到HashMap会有死循环的问题是两年前,我们团队有一个学长实习回来给我们说有个同事因为没有注意到HashMap在多线程可能会造成死循环而造成了一些损失。后面就对这个问题很感兴趣,然后趁着今天整理资料就顺便记录一下,虽然偷懒了,逃 = -=

什么造成的

我们知道HashMap不是线程安全的,那么具体到代码,是哪部分代码的原因呢? 我本来想写一篇博客介绍如何死循环产生的原因及过程,然后再查资料的时候发现了美团点评的这篇博客:**Java 8系列之重新认识HashMap**中介绍死循环的部分已经写的非常清楚了,就不想做重复工作了 = -=,哈哈 但是呢,最主要的问题解决了,我就只好分析一下JDK1.8中是如何做到扩容后链表依然保持着原来的顺序喽~哈哈

resize()方法

JDK1.8的改变

相较于JDK1.7,在1.8中resize()方法不再调用transfer()方法,而是直接将原来transfer()方法中的代码写在自己方法体内; 当然表面上我们能看到方法的减少,其实还有一个重大改变,那就是:扩容后,新数组中的链表顺序依然与旧数组中的链表顺序保持一致!

数组长度的技巧

在分析源码之前,我们还需要知道HashMap底层数组的一些优化: 数组长度总是2的倍数,扩容则是直接在原有数组长度基础上乘以2。

为什么要这么做?有两个优点:

  1. 通过与元素的hash值进行与操作,能够快速定位到数组下标 相对于取模运算,直接进行与操作能提高计算效率。在CPU中,所有的加减乘除都是通过加法实现的,而与操作时CPU直接支持的。
  2. 扩容时简化计算数组下标的计算量 因为数组每次扩容都是原来的两倍,所以每一个元素在新数组中的位置要么是原来的index,要么index = index + oldCap,假设

数组长度:2,key:3 0 0 0 1 0 0 1 1 结果为 0 0 0 1 = 1 所以数组下标为1;

扩容后,数组长度:4,key:3 0 0 1 1 0 0 1 1 结果为 0 0 1 1 = 3 = 原来的index + oldCap = 1 + 2


即确定元素在新数组的下标时,我们只需要检测元素的hash值与oldCap作与操作的结果是否为0:为0,那么下标还是原来的下标;为1,那么下标等于原来下标加上旧数组长度。

我们来看关键代码(resize()方法完整代码附后):

//如果扩容后,元素的index依然与原来一样,那么使用这个head和tail指针
Node<K,V> loHead = null, loTail = null
//如果扩容后,元素的index=index+oldCap,那么使用这个head和tail指针
Node<K,V> hiHead = null, hiTail = null
Node<K,V> next;
do {
    next = e.next;
    //这个地方直接通过hash值与oldCap进行与操作得出元素在新数组的index
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        //tail指针往后移动一位,维持顺序    
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        //tail指针往后移动一位,维持顺序    
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {
    loTail.next = null;
    //还是原来的index
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    //index = index + oldCap
    newTab[j + oldCap] = hiHead;
}

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 thresh
        newCap = oldThr;
    else {               // zero initial threshold signifies usin
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPA
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMU
                  (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, old
                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;
                        //这个地方很巧妙,直接通过e.hash & oldCap得出e在newTab中的位置;
                        //因为table是2倍扩容,所以只需要看hash值与oldCap进行与操作,结果为0,那么还是原来的index;否则index = index + oldCap
                        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;
                        //还是原来的index
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        //index 变为 index + oldCap
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

附加题

JDK 1.8 是否会出现类似于 JDK 1.7中那样的死循环呢? 我感觉有可能也会出现类似问题。 今下午想了很久,最后还是没有得到一个清晰的答案; 以后有了答案再补回来~

参考资料

© 著作权归作者所有

共有 人打赏支持
那只是一股逆流
粉丝 9
博文 22
码字总数 26214
作品 0
南岸
后端工程师
私信 提问
JDK1.8 不一样的HashMap

前言 HashMap想必大家都很熟悉,JDK1.8 的 HashMap 随便一搜都是一大片一大片的,那为什么还要写呢,我会把它精简一下,一方面有利于自己的学习,另一方面希望让大家更好理解核心内容。本篇主...

小坏怎么被用了
01/05
0
0
HashMap在JDK1.8中并发操作,代码测试以及源码分析

HashMap在JDK1.8中并发操作不会出现死循环,只会出现缺数据。测试如下: 1 package JDKSource; 2 3 import java.util.HashMap; 4 import java.util.Map; 5 import java.util.concurrent.Tim......

wenbochang
08/05
0
0
Java 8系列之重新认识HashMap

转自:美团点评技术团队--Java 8系列之重新认识HashMap 摘要 HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java Developmet Kit)版本的更新,JDK1.8对HashM...

放了一周的酸梅汤
2017/11/05
0
0
Java 深入分析HashMap

内部实现 搞清楚HashMap,首先需要知道HashMap是什么,即它的存储结构-字段;其次弄明白它能干什么,即它的功能实现-方法。下面我们针对这两个方面详细展开讲解。 存储结构-字段 从结构实现来...

我爱春天的毛毛雨
11/14
0
0
Java HashMap的工作原理 及各种Map区别

一、Java HashMap的工作原理 jdk1.7下HashMap数据结构:数组加链表,链表长度没有8的限制; jdk1.8 HashMap数据结构:数组+链表+红黑树;链表超过8会转存为红黑树; 1.jdk1.8 中HashMap的put...

盼望明天
2015/03/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring源码学习笔记-1-Resource

打算补下基础,学习下Spring源码,参考书籍是《Spring源码深度解析》,使用版本是Spring 3.2.x,本来想试图用脑图记录的,发现代码部分不好贴,还是作罢,这里只大略记录下想法,不写太细了 ...

zypy333
今天
10
0
RestClientUtil和ConfigRestClientUtil区别说明

RestClientUtil directly executes the DSL defined in the code. ConfigRestClientUtil gets the DSL defined in the configuration file by the DSL name and executes it. RestClientUtil......

bboss
今天
17
0

中国龙-扬科
昨天
2
0
Linux系统设置全局的默认网络代理

更改全局配置文件/etc/profile all_proxy="all_proxy=socks://rahowviahva.ml:80/"ftp_proxy="ftp_proxy=http://rahowviahva.ml:80/"http_proxy="http_proxy=http://rahowviahva.ml:80/"......

临江仙卜算子
昨天
11
0
java框架学习日志-6(bean作用域和自动装配)

本章补充bean的作用域和自动装配 bean作用域 之前提到可以用scope来设置单例模式 <bean id="type" class="cn.dota2.tpye.Type" scope="singleton"></bean> 除此之外还有几种用法 singleton:......

白话
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部