我是靠谱客的博主 专注发夹,这篇文章主要介绍Collection集合工具类源码解读(三) --- HashMap4、HashMap,现在分享给大家,希望可以做个参考。

文章目录

  • 4、HashMap
    • 4.1 先看看属性
    • 4.2 构造方法
    • 4.3 从put分析扩容机制(重点)
      • putVal方法
      • resize方法(扩容和树化)
        • 扩容
        • 树化
      • 扩容机制总结
    • 4.4 get方法
    • 4.5 remove方法
    • 4.6 replace

往期:

  • Collection集合工具类源码解读(一) — ArrayList 和 Vector
  • Collection集合工具类源码解读(二) — LinkedList

4、HashMap

重头戏来咯,老惯例,先写个demo,debug

public class HashMapDemo {
    public static void main(String[] args) {
       HashMap<Object, Integer> map = new HashMap<>();
        //HashMap<Object, Integer> map = new HashMap<>(2, 2);
        map.put("AAA",1);
        map.put("BBB",2);
        map.put("CCC",3);
        map.put("CCC",4);
        for (int i = 5; i <= 12; i++) {
            map.put(new Person(),i);
        }
        map.put(new Person(),13);
        map.put(new Person(),14);
        map.put(new Person(),15);
    }

    static class Person{
        String name;

        @Override
        public int hashCode() {
            return 100;
        }
    }
}

4.1 先看看属性

image-20220110175945945

image-20220110184758369

  • DEFAULT_INITIAL_CAPACITY:默认初始容量为16
    • 注意:刚new出来是0,往里添加数据后第一次resize()才到16,等下分析
  • MAXIMUM_CAPACITY:最大的容量:2的30次方
  • DEFAULT_LOAD_FACTOR :默认加载因子loadfactor:0.75
    • 用来计算扩容门槛,比如现在容量为16,16*0.75=12,即table满了12个容量就扩容,一次扩两倍
  • TREEIFY_THRESHOLD:默认树化门槛:8
  • UNTREEIFY_THRESHOLD:默认从树转换回链表的门槛:6
  • MIN_TREEIFY_CAPACITY:最小树化容量:64
    • 注意:①jdk1.8之后hashmap才是数组+链表+红黑树,jdk1.7和之前都是数组+链表,没有红黑树
    • ②必须满足table容量到64,并且其中table数组中的一个格子链接了长度为8的链表,这时候该链表才会树化,转换为红黑树

4.2 构造方法

image-20220111105333487

一共四个:

  • public HashMap():默认无参,loadfactor = 0.75
  • public HashMap(int initialCapacity) :设置初始容量,loadfactor = 0.75
  • public HashMap(int initialCapacity, float loadFactor):设置初始容量和loadfactor
    • 注意:loadfactor需要在0~1范围内,否则永远不会扩容 (后续分析)
  • public HashMap(Map<? extends K, ? extends V> m):往hashmap中插入另一个map

4.3 从put分析扩容机制(重点)

image-20220111122707281

  1. put进去后先算key的hash值,如果key为空,hash为0,否则就用key的hashcode异或key右移16位
  2. 然后是进入putVal方法: 这个方法很重要,需要细说一下

putVal方法

image-20220111124138609

image-20220111124812136

  1. tab在判断时赋值,把原先的table赋给了tab,第一次进入putVal时,table为空,走进第一个if( 第一次put必然
    • 进行 第一次resize
  2. 其他情况就是table不为空
    1. 如果该hash对应的table[i]位置为空:就直接放进去
    2. 如果该位置已经有元素了:
      1. 判断第一个元素的hash以及key和想要put进来的元素的hash以及key 是否相等,相等就让e = 这个相等的元素
      2. 判断这个位置连接的是否是红黑树:是就走红黑树的方法putTreeVal
      3. 否则就循环遍历这条链表,找是否有hash以及key 相等的元素,
        1. 有相等的就让e = 这个相等的元素
        2. 没有相等的就找到这条链表的尾部,追加到尾部
    3. 最后如果e!=null 即找到了一个key和hash都相等的元素,那么就替换调原来的值,修改为最新的值(所以hashmap往里put两个相同的key,值最后为最新的那个

resize方法(扩容和树化)

扩容

image-20220111134936935

image-20220111153104434image-20220111155641810

image-20220111155710015

  1. 进来之后先拿到原来的大小oldCap,原来的扩容门槛oldThr,
  2. 大括号是第一个if语段
    1. 原来的容量不为空:在oldCap不超过最大容量MAXIMUM_CAPACITY的情况下,将容量和门槛左移一位:意思是扩容直接翻2倍
    2. 原来的容量为空,但是门槛不为空:新的容量就是原来门槛的大小
    3. 原来容量为空,门槛也为空:(第一次resize):设置容量为16,门槛为16*0.75=12
  3. 第二个if语段,判断newThr是否还是等于0
    1. 在上一个if语段里,如果进入了oldCap>0,且oldThr=0的情况下,newThr翻2倍任然是0,所以在这里需要再次判断
    2. 将newThr设置为newCap*loadFactor
  4. 然后把threshold = newThr写回属性里,new一个新大小的Node数组,将table指向新的数组
  5. 然后再判断oldTab还有不有值,有就复制过来
  6. 最后返回新的table表

树化

再来讲一下扩容什么时候变成树的

image-20220111161344005

image-20220111162544487

如图是一个demo,默认构造方法hashmap的扩容门槛threhold是12,Person类的hashcode都是一致的,所以能插在同一索引位置上

所以:执行完断点前面的程序后,size已经满足了12,且Person那条链表长度以及到达了8,如图

image-20220111162817006

image-20220111161955425

image-20220111162248130

  • 在put第13个值时,打断点进去,发现其执行了treeifyBin(tab,hash),是因为他的链表长度超过了树化的长度TREEIFY_THRESHOLD = 8

    最终执行完之后可以看到,容量扩到了32,门槛到了24

  • 同样的,put14的时候,容量会扩到64,门槛到48,过程不截图了

  • 在put 15 的时候,注意,在此之前已经满足①链表长度>=8 ②table表容量64意思是要开始树化了

    同样的,进入treeifyBin(tab,hash),但是这次走else if,进行红黑树化,如图:

    treeify()就是对原来的树进行红黑树的格式化了,就不走进去了

image-20220111163910096

image-20220111164625304

最后发现,原来的Node已经被重构成了TreeNode


扩容机制总结

image-20220111165319872

4.4 get方法

image-20220111171412792

image-20220111171428421

  • get:
    • 调用getNode,如果查到有值就返回该值,查不到就返回null
  • getOrDefault:
    • 调用getNode,如果查到有值就返回该值,查不到就返回设置的默认值

4.5 remove方法

image-20220111172519009

  • remove(Object key):删除一个KV。调用removeNode方法,分析写在图上了,显而易见

4.6 replace

image-20220111172743695

  • replace(key,oldValue,newValue):找到key,oldvalue对应的结点替换这个值
  • replace(key,value):找到key对应的结点替换这个值

最后

以上就是专注发夹最近收集整理的关于Collection集合工具类源码解读(三) --- HashMap4、HashMap的全部内容,更多相关Collection集合工具类源码解读(三)内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(60)

评论列表共有 0 条评论

立即
投稿
返回
顶部