转载

通俗易懂的HashMap(Java8)源码解读！

开局一张图

要点

Java8对Java7的HashMap做了修改，最大的区别就是利用了红黑树。
Java7的结构中，查找数据的时候，我们会根据hash值快速定位到数组的具体下标。但是后面是需要通过链表去遍历数据，所以查询的速度就依赖于链表的长度，时间复杂度也自然是O(n)
为了减少2中出现的问题，在Java8中，当链表的个数大于8的时候，就会把链表转化为红黑树。那么在红黑树查找数据的时候，时间复杂度就变味了O(logN)

结构

结构图

描述

数组中存放的是节点。
如果是链表，就是Node节点，红黑树的话则是TreeNode节点。
在Node节点中，都是keyt,value,hash,next这几个属性，和Java7的基本一样。
我们根据存放在数组中的节点的类型，判断是红黑树还是链表

构造方法

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
复制代码

这个构造方法初始化了阈值和负载因子。

在构造方法中，是不会指定HashMap的容量大小的，就算是用 HashMap(int initCapacity) 的构造方法，传入的数运算之后的结果后面只是初始化阈值，并没有马上构建内部的数组，至于初始化内部数组只有第一次put的时候才会执行，初始化阈值是用来方便后面put的时候初始化数组。具体的还得需要读者往下看，只是说明下内部数组并不是在构造函数执行就已经初始化了。

tableSizeFor

这个函数就是将传进来的数向上取到最接近2的幂次的数(包括等于)。比如传入15，返回则是16；传入18，返回32。传入32，返回32。我们来看看他如何实现吧！

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
复制代码

解释

在解释源码之前我先说一下，传入一个cap，可能它不是2的几次幂，要找到大于等于cap的最小的2的幂

怎么找呢？我们看看开始举的例子(这里先把18-1先，至于这个-1后面会讲)

00000000，00000000， 00000000， 0001 0001 十进制：17

00000000，00000000， 00000000， 0010 0000 十进制：32

再看32-1的二进制是多少，和32和17的对比一下

00000000，00000000， 00000000， 00 10 0000 十进制：32

00000000，00000000， 00000000， 000 1 1111 十进制：31

00000000，00000000， 00000000， 000 1 0001 十进制：17

我们看到只要将17的后面5位全部变为1，那么就成31的二进制，后面再+1就可以变为32，这就达到我们的目的了！一句话说，这个函数的目的就是从最左边的1开始往右，都要变为1，后面再+1就可以达到我们想要的目的了！

过程

n|=n>>>1

由于n大于0，那么在二进制中高位肯定有一位是1，那么无符号右移1位与自己相或，那么肯定是接近原来数的后面的数变为1.比如10xxxx，那么运算 n|= n>>>1之后，肯定是11xxxx。

n|=n>>>2

在上面的例子中，n已经由10xxxx变为11xxxx了。那么我们们要让后面xxxx继续变为1，此时有两位是1，那么就让xxxx的前两位继续和11相或呗。所以无符号右移两位再与自己相或，就可以从11xxxx变为1111xx了。

那么现在有4个1，那么后面就移4位。变为8个1，就移8位....

依次类推。

如果要把32位变为全1的话，只要先把前16位变为1，那么后面右移16位就可以把32位全部变为1啦。

我们也可以看到，32位的1肯定是超过MAXIMUM_CAPACITY(1<<30),那么后面结果就会变为MAXIMUM_CAPACITY啦。

给大家看个图把，或许会更加清楚(用的是别人图)。其实上面说得很清楚啦！

概括

这里说下为什么传进来要先减1。有前面我们都知道，

相信上面的解释和例子中你都应该理解吧！ 二进制最左边的1开始往右，都要变为1 。如果传进来的刚好是2的m次幂，那么后面的n的二进制会变为1+上m个1，那返回的时候再+1的话，就变为1加上m+1个0了。 那么就变为传进来的数字的两倍了 。比如说传进32，二进制为1 00000 ,1后面5个0。后面是n变为1 11111 ，返回的时候+1，那么就返回1 000000 ，对应的十进制就是64了。这显然不符我们的逻辑。

至于其它不是2的几次幂的数，不管减不减1，只要最 左边的那个1位置没变 ，右边不管是什么，到后面都是可以变为大于等于传进来的数的最小的2的幂的。

所以综上，传进来的cap-1，就是为了防止传进来的cap是刚好的2的幂次数，避免后面返回的时候翻倍。

Put

public V put(K key, V value) {
    //关于hash函数，后面会说
    return putVal(hash(key), key, value, false, true);
}

//---------putVal

//onlyIfAbsent如果为true的表示的是：如果key不存在就存入，存在就不存入
//为false：key存在也存入，只不过会覆盖旧值，然后把旧值返回
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
     	//第一次put，会执行下面的if里面的 resize()
     	//第一次resize就是相当于初始化， 一般都会设置为16，后面扩容就不一样了。
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
     	//假设是第一次扩容，(n-1) & hash 相当于 hash对 n 求模
     	//这里也就是将hash值对15求模就可以随机得到一个下标啦
     	//如果这个位置没有值，那么就直接初始化一下Node并且放在hash映射到的位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
     	//这里hash映射的数据已经有节点啦
        else {
            Node<K,V> e; K k;
            //如果第一个节点就是我们想要找的那个节点，那么e就执行这第一个节点
            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);
            //到这里，就是想要放入的key可能在第一个节点后边或者这个key在链表中也不存在
            else {
                //这里binCount进行计数，主要是为了记录是否到达8个节点从而进行变形为红黑树
                for (int binCount = 0; ; ++binCount) {
                    //如果到达最后一个节点，也就是这个key不存在的情况
                    if ((e = p.next) == null) {
                        //新键节点放在链表的尾节点的后面，此时e已经为null
                        p.next = newNode(hash, key, value, null);
                        //如果此时节点已经到达7个，那么加入这个节点就成为8个了，那么就进行转化为红黑树啦
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        //这里有两种情况 1 是成功加入链表尾部，并且总数没超过8 ，2是 加入节点之后，总数到达8，那么就转为红黑树，就退出循环了 
                        break;
                    }
                    //put的时候，如果key已经存在在链表中，那么就退出，后面再进行 覆盖 操作
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //这里是一直没找到，遍历链表的操作
                    p = e;
                }
            }
            //这里e不为null的情况就是put的key已经在之前的链表中，
            //为null的话就是不在之前的链表中并且已经加入到之前链表的尾部
            if (e != null) { 
                V oldValue = e.value;
                //1 这个onlyIfAbsent之前也说过，为false就可以 覆盖 旧值
                //2 或者之前就没有值
                //1 或者 2 就执行下面的if
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //这个函数只在LinkedHashMap中用到, 这里是空函数
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
     	//如果增加这个节点之后，超过了阈值，那么就进行扩容
        if (++size > threshold)
            resize();
     	//这个函数只在LinkedHashMap中用到, 这里是空函数
        afterNodeInsertion(evict);
        return null;
    }

复制代码

hash方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码

在java中, hash函数是一个native方法, 这个定义在Object类中, 所以所有的对象都会继承.

public native int hashCode();
复制代码

因为这是一个本地方法, 所以无法确定它的具体实现, 但是从函数签名上可以看出, 该方法将任意对象映射成一个整型值.调用该方法, 我们就完成了 Object -> int 的映射

在hash的实现中我们看到

如果key为null，那么这个值就是放在数组的第一个位置的。
如果key不为null，那么就会先去key的hashCode右移16位然后再与自己异或。

大家可能关于第2点有点疑问

其实也就是说，通过让hashcode的高16位和低16位异或，通过高位对低位进行了干扰。目的就是为了让hashcode映射的数组下标更加平均。下面这段是引用论坛的匿名用户的解释，个人觉得解释得很详细

作者：匿名用户

链接： www.zhihu.com/question/20…

来源：知乎

我们创建一个hashmap，其entry数组为默认大小16。现在有一个key、value的pair需要存储到hashmap里，该key的hashcode是0ABC0000（8个16进制数，共32位），如果不经过hash函数处理这个hashcode，这个pair过会儿将会被存放在entry数组中下标为0处。下标=ABCD0000 & (16-1) = 0。然后我们又要存储另外一个pair，其key的hashcode是0DEF0000，得到数组下标依然是0。想必你已经看出来了，这是个实现得很差的hash算法，因为hashcode的1位全集中在前16位了，导致算出来的数组下标一直是0。于是，明明key相差很大的pair，却存放在了同一个链表里，导致以后查询起来比较慢。 hash函数的通过若干次的移位、异或操作，把hashcode的“1位”变得“松散”，比如，经过hash函数处理后，0ABC0000变为A02188B，0DEF0000变为D2AFC70，他们的数组下标不再是清一色的0了。 hash函数具体的做法很简单，你画个图就知道了，无非是让各数位上的值受到其他数位的值的影响。

在源码中我们看到 h&(n-1) 的操作，其实这样是和 h % n 一样的。只不过是一个很大的求模的时候会影响效率，但是通过位运算就快很多啦！

resize

resize()用于HashMap的 初始化数组 和 数组扩容 .
数组扩容之后，容量都是之前的2倍
进行数据迁移

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
     	//如果是初始化，oldTab肯定null，反之就不是null
        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
        }
     	//这里调用new HashMap(initCapacity)，第一次put
        else if (oldThr > 0) 
            //指定了容量,比如initCapacity指定了22，那么newCap就是32
            newCap = oldThr;
     	//这里调用new HashMap(),第一次put
        else { 
            //容量就是默认类内部指定的容量，也就是16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //默认的加载因子是0.75，所以阈值就是16*0.75 = 12
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
     	//这里的情况是 调用了new HashMap(initCapacity)或者
     	//new HashMap(initCapacity,loadFactor)的情况
     	//因为上面的两个构造函数都会初始化 loadFactor
     	//就是根据新的容量初始化新的阈值
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
     
     
     	//创建新的数组，赋给table,也就是实现了扩容
        @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;
                //获取对应数组位置的节点，如果为null表示没节点
                //否则就转移
                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 {
                        //这里定义了两个链表，lo和hi
                        //此时 e 就是数组所对应的第一个节点
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        //下面这个do-while就是遍历数组当前位置的链表，然后
                        //根据某些规则，把链表的节点放在扩容后的数组的不同位置
                        do {
                            //获取e的下一个节点
                            next = e.next;
                            //下面的解释可能有点难懂，待会看下面的解释再看这里即可
                            //1 如果节点hash运算后是老位置，那么就用lo链表存储
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //2 那么就是新位置，就用hi链表存储
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //这里很简单，lo链表不为空，那么数组的老位置就放lo的头结点
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //hi链表不为空，那么数组的老位置就放hi的头结点
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
复制代码

下面用一张图解释下数据转移的过程。

扩容解释

现在来解释下resize源码中的疑问

大家可能对 (e.hash & oldCap) == 0 这个判断有点迷糊，下面就来解释下。

n = (tab = resize()).length;

if ((p = tab[i = (n - 1) & hash]) == null)

由put方法的这两个语句我们知道，这里是通过 hash和数组的长度-1相与 得到节点映射到数组的哪个位置的。

一：

其实很简单，n就是数组的长度，我们都知道，在HashMap中的数组长度肯定是2的m方。那么n-1在二进制中就是m个全1咯，比如说数组的长度是16，16就是2的4次方，那么16-1 = 15 就是4个全1（2进制） “1111”

没扩容前就是用hash（key）之后得到的hash值与 (n-1)相与得到位置， 在上面的例子中也就是取出hash值的低4位 ，结果为a。(结果肯定在0-15之间)
扩容后，数组变为之前的2倍，那么数组的长度就成为32了，二进制就是100000，那么照葫芦画瓢， 同一个 hash值 与(32-1)相与得到位置。也就是 取出hash值的低5位 ，结果为b。(结果肯定在0-31之间)

二：

由1和2得知， b的二进制比a的二进制多了1位 ，前面4位是相同的。并且在二进制中，不是0就是1。

如果多出的1位是0，那么b和a是一样的。比如a 为1001，b是01001，那么a和b是相等的，也就是说 同一个节点在新数组的位置就是旧数组的原来的位置。
如果多出的1位是1，那么b比a就是多了2的m次方。比如a 也是1001，十进制是9，b是11001，十进制是25，那么b就比a多了2的4次方，而这个2的4次方刚好就是原来数组的长度oldCap。也就是说也就是说同一个节点在新数组的位置就是旧数组的原来的位置加上2的4次方(没扩容的数组的长度（oldCap) )。

所以我们得出结论，只要我们可以判断扩容之后b比a多的那一位是1还是0(在例子中也就是第5位)，就可以得出同一个节点在新数组的哪个位置了，一句话总结就是。数组扩容后，同一个节点要么在原来的位置，要么在原来的位置加上没扩容的数组的长度（oldCap）。

那么我们如何得到b比a多的那一位到底是啥呢？很简单，就是 用hash值和oldCap相与即可 ！比如说这里的oldCap为16，那么二进制就是1后面加上m个0，也就是10000，也就是第m+1位为1，用hash值与oldCap相与， 就可以得出hash值的第5位是啥啦 ，那么就可以根据前面的"二"去判断节点到底在新数组哪个位置啦。

读者们看到这里，就可以继续回到源码的1处去看，这时候应该就会豁然开朗啦！