从我学习Java的时候,学到HashMap,我记过的答案是HashMap在Jdk1.8的时候底层实现改为数组+链表+红黑树,当链表长度为8时转为红黑树,红黑树长度减少到6时又转为链表,这样的话在csdn中能找到很多,但他们都没有说清楚。

原因是我最近看到有些文章说数组容量达到64才会触发树化,这就和我固有的认识(错误的)产生了冲突,然后我就开始未知探索之路

以下是我的结论(查看大佬的解析+b站视频双管齐下)

HashMap链表转红黑树的条件:容量大于等于64且链表长度为8才会进行树化,否则只会进行扩容
HashMap数组的扩容机制:键值对个数(size)超过(如果容量是16(默认值),负载因子是0.75(默认值)的话,阈值就是12,要第13个才会扩容)阈值(依次类推,容量32时阈值为24)触发扩容,还有就是当一条链表长度达到8且数组容量小于64也会进行扩容

1.HashMap的put()方法,put()方法里是调用putVal()方法

HashMap<Integer, String> map = new HashMap<>(); //第一次HashMap在第一次调用put()时才会初始化 map.put(1, "小明"); /* //HashMap的属性,table数组,每个索引位置称为桶 transient Node[] table;    ----------------------------------以下是put()方法的代码实现(为了便于查看我把所有注释加了个制表符) //hash:新键值对的hash值,key是键(就是加入的1),value是值(就是小明) final V putVal(int hash, K key, V value, boolean onlyIfAbsent,     boolean evict) { //tab数组:临时的HashMap底层存储数组, //p节点:就是用来存放头节点的 //n是tab.length就是桶的数量 //i是索引位置(也就是桶,桶:我的理解就是还数组索引位置及hash冲突之后的链表) Node[] tab; Node p; int n, i; //对hashMap进行判空(HashMap底层存储数组,是HashMap类的属性) //!!##我有个大大的疑问,第二次put()时,tab不为空不会进入这个if,那n(数组长度)不就是未初始化的状态吗 //!!##这个疑惑已解决(我放在最下面的代码段) if ((tab = table) == null || (n = tab.length) == 0)     //如果为空则调用resize(),初始化     n = (tab = resize()).length; //i = (n - 1) & hash  "n-1"是数组长度-1,然后和hash(hash值)相与,得到传入节点的桶位置 //x mod 2^n = x & (2^n - 1) 这是 HashMap 在速度上的优化，因为 & 比 % 具有更高的效率。 //i就是table数组(hashMap底层的那个数组)的索引,桶的位置 //对桶位置的判空(是否有头节点) if ((p = tab[i = (n - 1) & hash]) == null)     //无头节点则直接把新节点存在桶位置     tab[i] = newNode(hash, key, value, null); else {//有头节点     //泛型类型的变量k是头节点的key     Node e; K k;     //再解释一个p是头节点     //当新加入的节点的hash值和key对象的地址相同(即同一对象)      //或者 两个key的值相等时(地址不同比较对象,这就是作为Key的类要重写hashcode方法和equals方法)     //其实就是做替换value的操作(在下一个的if中操作的)     if (p.hash == hash &&  ((k = p.key) == key || (key != null && key.equals(k))))  e = p;//相等就把头节点的地址(是地址)赋值给临时节点变量e,并进入下一个if #if (e != null) {}#     else if (p instanceof TreeNode)//是否是红黑树的实例  //把Node类型的p强转为TreeNode(红黑树类型),然后调用红黑树的putTreeVal()方法  e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);     else {//只是单纯的链表  for (int binCount = 0; ; ++binCount) {//死循环,写源码的人特别喜欢用for(;;)来写死循环      //##能理解要遍历链表但不明白每次循环调用next节点是如何操作的      if ((e = p.next) == null) {   //加到最后一个节点后面   p.next = newNode(hash, key, value, null);   //加入节点后要判断链表长度是否为8,如果是则调用树化方法(但不一定会树化)   //binCount从0开始自增   //当binCount >=7时   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//树化!!!(但不是马上树化,)treeifyBin(tab, hash);//#####下个代码段我把treeifyBin()方法中有利于本文理解的代码贴出来//会进行这么一个判断,MIN_TREEIFY_CAPACITY:最小树化容量为64//if (tab == null || (n = tab.length)  threshold)     resize(); afterNodeInsertion(evict); return null;    }*/

2.HashMap的树化代码

final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //看这,某条链表长度为8时进入这个方法, //tab肯定不为null,当tab长度小于MIN_TREEIFY_CAPACITY时  //#我对MIN_TREEIFY_CAPACITY的理解(最小树化容量值为64,capacity是容量的意思(在HashMap中       //同样用到这个单词的只有table数组的容量,默认为16), //我看有些博客说什么链表长度为8时和64个节点就树化应该是错误的理解)# if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //所以只有数组容量大于等于64时,链表长度到8时才会树化,把链表转红黑树,其他情况都是扩容     resize();     //下面的代码以后再看了😂 else if ((e = tab[index = (n - 1) & hash]) != null) {     TreeNode<K,V> hd = null, tl = null;     do {  TreeNode<K,V> p = replacementTreeNode(e, null);  if (tl == null)      hd = p;  else {      p.prev = tl;      tl.next = p;  }  tl = p;     } while ((e = e.next) != null);     if ((tab[index] = hd) != null)  hd.treeify(tab); }    }

3.HaspMap的扩容机制

在IDEA中使用debug调试可以很清晰看到HashMap的扩容机制(有些人可能只能看到普通数组而看不到HashMap中的数组,我之前也是,那是因为IEDA中对集合的数据视图进行了设置)

写一个简单的例子,然后debug

  HashMap<String, Integer> map = new HashMap<>(); for (int i = 0; i < 13; i++) {     map.put("小明"+i, i); }

debug截图

当键值对个数也就是map.size()==13时触发扩容

4.第二次put()时n的值

如果对HashMap第二次put()方法没疑惑别浪费时间,路过

模拟第二次put方法时,n在何时赋值?

public static void main(String[] args) { int[] table = {1}; int[] tab; int n; //模拟HashMap第二次put() //首先,进入if的条件判断,tab显然不为空为false,然后在n = tab.length赋值时,n的值已经为1了,不管能不能进{}代码块,n已被赋值 // 所以第二次put()不进入这个if,n也已经等于数组长度了 if ((tab = table) == null || (n = tab.length) == 0) {     //哪怕第二次不执行这条语句,这条语句也要存在,不然编译不通过     //java: 可能尚未初始化变量n     n = 0; } if (n == 0) {} System.out.println("已被赋值n = " + n);//已被赋值n = 1    }

5.最后

小记:

HashMap转红黑树:容量大于等于64且链表长度为8才会进行树化,否则只会进行扩容
HashMap的扩容机制:键值对个数(size)超过(如果容量是16,负载因子是0.75的话,阈值就是12,要第13个才会扩容)阈值触发扩容,还有就是当一条链表长度达到8且数组容量小于64也会进行扩容
最近感悟,HashMap在网上的解析非常多但是参差不齐,好多自己都没debug过,所以遇到不懂的还是得信源码和debug,一定要结合源码,一定要有自己的思考

参考这两个大佬的,看了韩顺平的b站视频才终于懂了debug,开心!!!

参考了[程序员囧辉]史上最详细的 JDK 1.8 HashMap 源码解析

【韩顺平讲Java】Java集合专题

读书笔记网