深入解析JDK8HashMap源代码：put方法详解及capacity、size、loadFactor和红黑树转换阈值的设定原理

HashMap

一、HashMap允许key为null&＃xff0c;value为null&＃xff0c;但是key为null只可以为一个&＃xff0c;因为放进去key &＃61; null的新键值对&＃xff0c;再放进去的时候会更新key &＃61; null的value值

二、put(key, value)的过程

return putVal(hash(key), key, value, false, true);


0、创建了HashMap以后&＃xff0c;其capacity为16&＃xff08;仅仅是DEFAULT_INITIAL_CAPACITY值为16但是容量并不为16&＃xff0c;目前里面实际存储键值对的Node数组仍然为空&＃xff09;、loadFactor为0.75&＃xff1b;size&＃xff08;为键值对的个数而不是桶被占用的个数&＃xff09;、threshold为0&＃xff0c;在put第一个值的时候才new Node[16]&＃xff0c;threshold&＃61;16 * 0.75&＃xff1b;

HashMap底层存储数据其实是一个其内部类Node implements Map.Entry的数组

1、key先进行hash运算

&＃xff08;1&＃xff09;如果key为null&＃xff0c;返回0&＃xff1b;

&＃xff08;2&＃xff09;如果不为null&＃xff0c;执行hashcode运算

Ⅰ.如果为普通数据&＃xff08;字符串、数字&＃xff09;&＃xff0c;那么它的hashCode运算为&＃xff1a;

&＃xff08;数字会自动装箱转为包装类&＃xff0c;使用其重写的hashcode运算&＃xff09;

* 字符串对象内部存储为数组&＃xff1b;* int h &＃61; 0* 循环计算&＃xff1a;h &＃61; h*31 &＃43; 字符数组中的字符ASCII值


Ⅱ.如果为Java对象&＃xff0c;一般需要重写hashCode方法&＃xff0c;不重写的话会调用本地方法&＃xff0c;这个方法是C语言实现的&＃xff0c;但是返回值绝对不是对象的内存地址&＃xff1b;

public native int hashCode();


&＃xff08;3&＃xff09;hashCode的返回值hash和hash自己做无符号右移16位后的值做&运算&＃xff08;高位补0&＃xff09;

return (key &＃61;&＃61; null) ? 0 : (h &＃61; key.hashCode()) ^ (h >>> 16);


2、将hash值&＃xff0c;key和value传入putVal()方法中&＃xff0c;开始做散列

• 将hash值 & 容量size- 1&＃xff08;初始为16&＃xff09;&＃xff0c;映射到Node数组上&＃xff0c;判断这个位置是否为null

  • 为null&＃xff0c;说明这个位置没有创建过值&＃xff0c;那么就创建一个Node&＃xff08;hash, k, v, next &＃61; null&＃xff09;的节点放进去&＃xff0c;这里next代表链表中的下一个节点&＃xff0c;然后被修改的次数modcount &＃43; 1&＃xff08;结构上被修改的次数&＃xff0c;这里的被修改次数指的是删除和增加&＃xff0c;不包括更新值&＃xff09;&＃xff0c;size &＃43; 1【注释&＃xff1a;modcount 该字段被Iterator以及ListIterator的实现类所使用&＃xff0c;如果该值被意外更改&＃xff0c;Iterator或者ListIterator 将抛出ConcurrentModificationException异常&＃xff0c;】

    • 如果size超过了threshold&＃xff08;初始为12&＃xff09;&＃xff0c;就将创建一个新的Node(capacity × 2)的数组&＃xff0c;然后将旧的Node数组的所有键值对放进去&＃xff08;放到新数组的过程单独在下面分析&＃xff09;&＃xff0c;让HashMap里面的Node数组成员变量指向这个新的Node对象&＃xff0c;返回null&＃xff08;记住&＃xff0c;插入新的值就是返回null&＃xff0c;更新值时返回老的value&＃xff09;
    • size没超过&＃xff0c;直接返回null

  • 不为null说明这个位置有值&＃xff0c;那么比较老的Node的key和新需要插入的Node的key是否相等&＃xff1b;

    • key相等&＃xff0c;则将原来的value替换为新的&＃xff0c;并将来的老的value返回

    • key不相等

      • 查看当前Node数组位置的节点是不是一个红黑树TreeNode节点&＃xff08;p instanceof TreeNode判断的&＃xff09;&＃xff0c;是的话就按照红黑树节点进行遍历更新或插入数据&＃xff0c;如果是被修改则返回老的值&＃xff0c;如果是被插入数据那么返回null并且modcount &＃43; 1&＃xff0c;size &＃43; 1&＃xff0c;之后判断是否需要扩容

      • 不是红黑树节点遍历该位置是否有链表

        • 有链表&＃xff0c;循环遍历链表中的&＃xff0c;是否有K相等但是V不等的&＃xff0c;如果有就将V替换成新的Value并且返回老的值&＃xff0c;如果没有就在最后位置插入新节点并且modCount &＃43; 1&＃xff0c;size &＃43; 1&＃xff0c;
          • 如果是插入节点&＃xff0c;判断链表长度是否大于8&＃xff0c;如果大于8就扩成红黑树结构
        • 无链表&＃xff0c;说明Node数组这个位置就这一个节点&＃xff0c;把新的节点插入进去并且modCount &＃43; 1&＃xff0c;size &＃43; 1&＃xff0c;

【扩容时如何复制节点到新的Node[]数组&＃xff1a;&＃xff08;暂不考虑红黑树情况&＃xff09;

循环遍历每一个桶

• 如果只有一个节点&＃xff0c;直接hash & newCapacity - 1确定新的桶位置&＃xff08;新的位置要不就是新数组的原下标号桶里&＃xff0c;要不就是在oldCapacity &＃43; 原下标号的桶里&＃xff0c;这个下面代码块部分会解释&＃xff09;;
• 如果不止一个节点&＃xff0c;循环遍历每一个节点&＃xff0c;先hash & oldCapacity&＃xff08;老数组的容量&＃xff09;&＃xff0c;这样是为了判断你的下标需不需要挪到新扩出来的桶去&＃xff0c;举个例子&＃xff1a;

容量16&＃xff08;16-1 &＃61; 1111&＃xff09;&＃xff0c;hash1 &＃61; 10001和hash2 &＃61; 00001的桶位置都在1里面&＃xff0c;但是扩容以后&＃xff0c;容量32&＃xff08;32-1 &＃61; 11111&＃xff09;因为首位数字不同所以就不会在一个桶了&＃xff0c;这样hash & oldCapacity是为了判断你的最高那一位是不是1&＃xff0c;如果是0那你不用挪位置&＃xff0c;如果是1&＃xff0c;那就要挪桶的位置&＃xff0c;挪到oldCapacity &＃43; 当前下标的位置&＃xff08;最高位为1&＃xff0c;做hash运算的时候肯定会变为1XXXX&＃xff0c;就等于oldCap &＃43; 当前下标&＃xff09;


• 挪的过程中就会进行分表&＃xff0c;即把这个老的链表拆开&＃xff0c;一部分留在新数组原下标号的桶里&＃xff0c;一部分放到&＃xff08;oldCapacity &＃43; 当前下标&＃xff09;的桶里

】

三、hashmap一些值设定的原因

1、为什么数值要为2^n个

&＃xff08;1&＃xff09;当哈希表的桶的个数为2^n 的时候&＃xff0c;它的下标最大为 2^n - 1 &＃xff0c;这个时候转为二进制就是111…11的结构&＃xff0c;可以保证与key的hash值做&运算得到的值可以完美投影到其中一个桶上&＃xff0c;这样就不担心是否会投影到桶之外再做另外的处理。

例如当前容量为16&＃xff0c;key的hash值为10001&＃xff0c;我们直接使用16 &＃61; 10000 & 10001 &＃61; 10000 &＃61; 16 >桶的最大下标15&＃xff0c;这个时候就还需要再做其他处理甚至可能需要做二次hash&＃xff0c;那么是很麻烦和浪费时间的&＃xff1b;

&＃xff08;2&＃xff09;可以尽可能的减少碰撞次数&＃xff0c;因为只要两个key的hash值不同&＃xff0c;与111…111的&运算就一定不同&＃xff0c;可以尽可能的避免碰撞

2、为什么加载因子是0.75

这是考虑了时间和空间效率得出的折中方案&＃xff0c;如果为1的时候在扩容那么会增大碰撞率&＃xff0c;如果考虑一下中间值0.5的时候再扩容那么会浪费很多空间&＃xff0c;因此要取一个折中方案。那么是因为0.5 &＃43; 1/ 2 &＃61; 0.75吗&＃xff0c;实际维基百科有一个介绍说&＃xff1a;

对于开放定址法&＃xff0c;加载因子是特别重要因素&＃xff0c;应严格限制在0.7-0.8以下。超过0.8&＃xff0c;查表时的CPU缓存不命中&＃xff08;cache missing&＃xff09;按照指数曲线上升。因此&＃xff0c;一些采用开放定址法的hash库&＃xff0c;如Java的系统库限制了加载因子为0.75&＃xff0c;超过此值将resize散列表。


因此折衷方案来自于这里&＃xff01;

有的博客说是因为那个泊松分布&＃xff0c;在我看来那个泊松分布是说在加载因子为0.75的前提下&＃xff0c;可以保证我们的桶上链表节点的个数大于等于8的可能性几乎为0&＃xff0c;这个更像是说明链表转红黑树的设定阈值为8的原因。

参考原文&＃xff1a;https://blog.csdn.net/NYfor2017/article/details/105454097/?utm_medium&＃61;distribute.pc_relevant.none-task-blog-baidujs-2

3、为什么链表长度大于等于8的时候转为红黑树&＃xff0c;小于等于6的时候转为链表

&＃xff08;1&＃xff09;依据泊松分布&＃xff0c;加载因子为0.75的时候&＃xff0c;链表中的个数为8的可能性为亿分之6&＃xff08;代码中注释所描述&＃xff09;&＃xff0c;所以正常情况下是不会出现这种状况的&＃xff0c;但是如果出现了就说明是非正常情况&＃xff0c;这个时候可能有很多的key碰撞在同一个桶中&＃xff0c;这个时候继续用链表的话查询时间复杂度O&＃xff08;n&＃xff09;效率是很低的&＃xff0c;而红黑树的O(log(n))则要远远优于链表&＃xff0c;举个例子&＃xff0c;1024的链表查询平均时间为512&＃xff0c;而红黑树则仅仅为10。节点数小于8的时候链表的查询时间是很小的&＃xff0c;没必要用红黑树&＃xff0c;而且红黑树调整树结构也需要时间&＃xff0c;节点数也为链表节点数的2倍&＃xff0c;所以没必要使用。

总结&＃xff1a;Ⅰ桶上节点数出现8的概率很低&＃xff0c;出现了说明为非正常情况&＃xff0c;因此要额外处理&＃xff1b;Ⅱ而当大于等于8的时候继续使用链表查询效率会比较低&＃xff0c;改用红黑树会更快&＃xff08;这是以空间换取时间的策略&＃xff09;&＃xff1b;Ⅲ节点数小于8的时候考虑时间和空间效率没必要使用红黑树&＃xff1b;

参考原文&＃xff1a;https://blog.csdn.net/qq_43519310/article/details/102887039

&＃xff08;2&＃xff09;那为什么6是树转链表的阈值&＃xff1a;因为达到了8的时候如果一个桶上频繁的增删节点可能节点数会不停的在8和7变动&＃xff0c;那么阈值设定为7就要不停的链表和树互转&＃xff0c;这个时候耗费时间空间&＃xff0c;所以给它一个缓冲空间设定阈值为6的时候再转链表&＃xff0c;达到6的时候说明节点数在向减少的趋势发展&＃xff0c;所以设定为6了&＃xff1b;