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

<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基本原理和优缺点

一句话讲， 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办法，之后次要脉络是：

第一步调用了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[]数组中了。

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

新的数组容量为原来的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)

你有趣味的话，能够别离画一下这三种状况的图。这里给大家一个图，假如都登程了以上三种状况后果如下所示：

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死循环问题？

在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 公布！