关于java:JDK成长记73张图搞懂HashMap底层原理

44次阅读

共计 8933 个字符，预计需要花费 23 分钟才能阅读完成。

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>HashMap 基本原理和优缺点 </span></h3></div>

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

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>HashMap 的 3 个底层原理 </span></h3></div>

在看过了 ArrayList、LinkedList 的底层源码后，置信你对浏览 JDK 源码曾经驾轻就熟了。除了 List 很多时候你应用最多的还有 Map 和 Set。接下来我将用三张图和你一起来摸索下 HashMap 的底层外围原理到底有哪些？

这一节咱们就不一步一步带着大家看源码，间接通过 3 张源码原理图，给大家解说 HashMap 原理图。有了之前的教训，置信你应该有能力本人看懂原理和本人画图了。

首先你应该晓得 HashMap 的外围办法之一就是 put。咱们带着如下几个问题来看下图：

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

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

第一步调用了 hash 办法计算 hash 值。
第二步计算容量和扩容
第三步创立元素

如何计算 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[]数组中了。

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>HashMap 另外 3 个底层原理 </span></h3></div>

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

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。你能够看到如下具体思路：

新的数组容量为原来的 2 倍，比方 16-32
新的扩容阈值也是原来的 2 倍，比方 12->24
为新数组调配了空间 newTab, 原数组 oldTab 不为空，须要进行 rehash 操作
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。你能够看到如下具体思路：

新的数组容量为原来的 2 倍，比方 16-32
新的扩容阈值也是原来的 2 倍，比方 12->24
为新数组调配了空间 newTab, 原数组 oldTab 不为空，须要进行 rehash 操作
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 个元素就会进行扩容。

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>JDK1.7 HashMap 死循环问题？</span></h3></div>

在 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 版本，局部章节会提到旧版本特点）