JDK成长记7:3张图搞懂HashMap底层原理

HashMap基本原理和优缺点

一句话讲， HashMap底层数据结构，JDK1.7数组+单向链表、JDK1.8数组+单向链表+红黑树。

HashMap的3个底层原理

在看过了ArrayList、LinkedList的底层源码后，相信你对阅读JDK源码已经轻车熟路了。除了List很多时候你使用最多的还有Map和Set。接下来我将用三张图和你一起来探索下HashMap的底层核心原理到底有哪些？

这一节我们就不一步一步带着大家看源码，直接通过3张源码原理图，给大家讲解HashMap原理图。有了之前的经验，相信你应该有能力自己看懂原理和自己画图了。

首先你应该知道HashMap的核心方法之一就是put。我们带着如下几个问题来看下图：

• • hash值计算的算法是什么？就是key.hashCode()吗？
  • 默认情况下，put第一个元素时候容量大小是多少？扩容阈值又是多少？
  • hash寻址如何进行的？

如上图所示，put方法调用了putVal方法，之后主要脉络是：

1. 第一步调用了hash方法计算hash值。
2. 第二步计算容量和扩容
3. 第三步创建元素

如何计算hash值？

计算hash值的算法就在第一步，如图所示，对key值进行hashCode()后，对hashCode的值进行无符号右移16位和hashCode值进行了异或操作。为什么这么做呢？其实涉及了很多数学知识，简单的说就是尽可能让高16和低16位参与运算，可以减少hash值的冲突（数据结构算法课中可能叫散列碰撞）。

默认容量和扩容阈值是多少？

如上图所示，很明显第二步回调用resize方法，获取到默认容量为16，这个16在源码里是1<<4得到的，1左移4位得到的。之后由于默认扩容因子是0.75，所以两者相乘就是扩容大小阈值16*0.75=12。之后就分配了一个大小为16的Node[]数组，作为Key-Value对存放的数据结构。

最后一问题是，如何进行hash寻址的？

hash寻址其实就在数组中找一个位置的意思。用的算法其实也很简单，就是用数组大小和hash值进行n-1&hash运算，这个操作和对hash取模很类似，只不过这样效率更高而已。hash寻址后，就得到了一个位置，可以把key-value的Node元素放入到之前创建好的Node[]数组中了。

HashMap另外3个底层原理

当你了解了上面的三个原理后，你还需要掌握如下几个问题:

• hash值如果计算的相同该怎么解决冲突？
• HashMap扩容后怎么进行rehash的？
• 指定大小的HashMap，扩容阈值算法是什么？

还是老规矩，看如下图：

• hash值如果计算的相同该怎么解决冲突？

当hash值计算一致，比如当hash值都是1100时，Key-Value对的Node节点还有一个next指针，会以单链表的形式，将冲突的节点挂在数组同样位置。这就是数据结构中所提到解决hash 的冲突方法之一：单链法。当然还有探测法+rehash法有兴趣的人可以回顾《数据结构和算法》相关书籍。

但是当hash冲突严重的时候，单链法会造成原理链接过长，导致HashMap性能下降，因为链表需要逐个遍历性能很差。所以JDK1.8对hash冲突的算法进行了优化。当链表节点数达到8个的时候，会自动转换为红黑树，自平衡的一种二叉树，有很多特点，比如区分红和黑节点等，具体大家可以看小灰算法图解。红黑树的遍历效率是O(logn)肯定比单链表的O(n)要好很多。

总结一句话就是，hash冲突使用单链表法+红黑树来解决的。

• HashMap扩容后怎么进行rehash的？

上面的图，核心脉络是四步，源码具体的就不粘出来了。当put一个之后，map的size达到扩容阈值12，就会触发rehash。你可以看到如下具体思路：

1. 新的数组容量为原来的2倍，比如16-32

2. 新的扩容阈值也是原来的2倍，比如12->24

3. 为新数组分配了空间newTab,原数组oldTab不为空，需要进行rehash操作

4. rehash有3种情况，数组位置如果有值，进行rehash。（这一步是rehash核心中的核心）有如下三种情况：

情况1:如果数组位置只有一个值：使用新的容量进行rehash，即e.hash & (newCap - 1)

情况2:如果数组位置有链表，根据 e.hash & oldCap == 0进行判断，结果为0的使用原位置，否则使用index + oldCap位置,放入元素形成新链表，这里不会和情况1新的容量进行rehash与运算了，index + oldCap这样更省性能。

情况3：如果数组位置有红黑树，根据split方法，同样根据 e.hash & oldCap == 0进行树节点个数统计，如果个数小于6，将树的结果恢复为普通Node，否则使用index + oldCap，调整红黑树位置，这里不会和新的容量进行rehash与运算了，index + oldCap这样更省性能。

你有兴趣的话，可以分别画一下这三种情况的图。这里给大家一个图，假设都出发了以上三种情况结果如下所示：

上面的图，核心脉络是四步，源码具体的就不粘出来了。当put一个之后，map的size达到扩容阈值12，就会触发rehash。你可以看到如下具体思路：

1. 新的数组容量为原来的2倍，比如16-32

2. 新的扩容阈值也是原来的2倍，比如12->24

3. 为新数组分配了空间newTab,原数组oldTab不为空，需要进行rehash操作

4. rehash有3种情况，数组位置如果有值，进行rehash。（这一步是rehash核心中的核心）有如下三种情况：

情况1:如果数组位置只有一个值：使用新的容量进行rehash，即e.hash & (newCap - 1)

情况2:如果数组位置有链表，根据 e.hash & oldCap == 0进行判断，结果为0的使用原位置，否则使用index + oldCap位置,放入元素形成新链表，这里不会和情况1新的容量进行rehash与运算了，index + oldCap这样更省性能。

情况3：如果数组位置有红黑树，根据split方法，同样根据 e.hash & oldCap == 0进行树节点个数统计，如果个数小于6，将树的结果恢复为普通Node，否则使用index + oldCap，调整红黑树位置，这里不会和新的容量进行rehash与运算了，index + oldCap这样更省性能。

你有兴趣的话，可以分别画一下这三种情况的图。这里给大家一个图，假设都出发了以上三种情况结果如下所示：

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

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);
}

上面源码核心脉络，3个if主要是校验了一堆，没做什么事情，之后赋值了扩容因子，不传递使用默认值0.75，扩容阈值threshold通过tableSizeFor(initialCapacity);进行计算。注意这里只是计算了扩容阈值，没有初始化数组。代码如下：

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;
}

竟然不是大小*扩容因子？

n |= n >>> 1这句话，是在干什么？n |= n >>> 1等价于n = n | n >>>1; 而|表示位运算中的或，n>>>1表示无符号右移1位。遇到这种情况，之前你应该学到了，如果碰见复杂逻辑和算法方法就是画图或者举例子。这里你就可以举个例子：假设现在指定的容量大小是100,n=cap-1=99，那么计算过程应该如下：

n是int类型，java中一般是4个字节，32位。所以99的二进制：0000 0000 0000 0000 0000 0000 0110 0011。

最后n+1=128，方法返回，赋值给threshold=128。再次注意这里只是计算了扩容阈值，没有初始化数组。

为什么这么做呢？一句话，为了提高hash寻址和扩容计算的的效率。

因为无论扩容计算还是寻址计算，都是二进制的位运算，效率很快。另外之前你还记得取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。即 hash%size = hash & (size-1)。这个前提条件是除数是2的幂次方。

你可以再回顾下resize代码，看看指定了map容量，第一次put会发生什么。会将扩容阈值threshold，这样在第一次put的时候就会调用newCap = oldThr;使得创建一个容量为threshold的数组，之后从而会计算新的扩容阈值newThr为newCap*0.75=128*0.75=96。也就是说map到了96个元素就会进行扩容。

JDK1.7 HashMap死循环问题？

1. 在JDK1.8引入红黑树之前,JDK1.7由于只有单向链表解决hash冲突，除了遍历性能可能会慢，还有几率在多线程同时扩容，rehash的时候发生死循环问题，造成cpu100%。虽然把hashMap用到多线程很不合理，但是有时候面试总会考这么刁钻的问题。面试圈有时候还是比较复杂的。。。

   造成死循环的这个问题，过程比较复杂，这一节可能讲不完了。这里给大家抛砖引玉下。

   造成死循环的核心脉络有如下几步：

   1、首先原位置得有hash冲突，比如链表元素有4个。

   2、之后需要有2个线程，同时添加元素，均满足扩容条件，进行扩容

   3、一个线程刚刚进行了rehash操作，之后另一个线程开始rehash操作，会形成环向链表。

   4、get操作时候发生无限死循环，cpu可能达到100%

   如下图：

金句甜点

除了今天知识，技能的成长，给大家带来一个金句甜点，结束我今天的分享：坚持的三个秘诀之一目标化。

坚持的秘诀除了上一节提到的视觉化，第二个秘诀就是目标化。顾名思义，就是需要给自己定立一个目标。这里要提到的是你的目标不要定的太高了。就比如你想要增加肌肉，给自己定了一个目标，每天5组，每次10个俯卧撑，你看到自己胖的身形或者海报，很有刺激，结果开始前两天非常厉害，干劲十足，特别奥利给。但是第三天，你想到要50个俯卧撑，你就不想起床，就算起来，可能也会把自己撅死过去......其实你的目标不要一下子定的太大，要从微习惯开始，比如我媳妇从来没有做过俯卧撑，就让她每天从1个开始,不能多，我就怕她收不住，做多了。一开始其实从习惯开始，先变成习惯，再开始慢慢加量。量太大养不成习惯，量小才能养成习惯。很容易做到才能养成，你想想是不是这个道理？

所以，坚持的第二个秘诀就是定一个目标，可以通过小量目标，养成微习惯。比如每天你可以读五分钟书或者5分钟成长记，不要多，我想超过你也会睡着了的.....

最后，大家可以在阅读完源码后，在茶余饭后的时候问问同事或同学，你也可以分享下，讲给他听听。

欢迎大家在评论区留言和我交流。

（声明：JDK源码成长记基于JDK 1.8版本，部分章节会提到旧版本特点）

本文由博客一文多发平台 OpenWrite 发布！