Collection集合工具类源码解读（三） --- HashMap

文章目录

4、HashMap

4.1 先看看属性4.2 构造方法4.3 从put分析扩容机制(重点)

putVal方法resize方法（扩容和树化）

扩容树化扩容机制总结 4.4 get方法4.5 remove方法4.6 replace
往期：

Collection集合工具类源码解读（一） — ArrayList 和 VectorCollection集合工具类源码解读（二） — linkedList 4、HashMap

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

public class HashMapDemo {
    public static void main(String[] args) {
       HashMap map = new HashMap<>();
        //HashMap 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 先看看属性

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：默认树化门槛：8UNTREEIFY_THRESHOLD：默认从树转换回链表的门槛：6MIN_TREEIFY_CAPACITY：最小树化容量：64

注意：①jdk1.8之后hashmap才是数组+链表+红黑树，jdk1.7和之前都是数组+链表，没有红黑树②必须满足table容量到64，并且其中table数组中的一个格子链接了长度为8的链表，这时候该链表才会树化，转换为红黑树 4.2 构造方法

一共四个：

public HashMap()：默认无参，loadfactor = 0.75public HashMap(int initialCapacity) ：设置初始容量，loadfactor = 0.75public HashMap(int initialCapacity, float loadFactor)：设置初始容量和loadfactor

注意：loadfactor需要在0~1范围内，否则永远不会扩容（后续分析） public HashMap(Map m)：往hashmap中插入另一个map 4.3 从put分析扩容机制(重点)

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

进行第一次resize 其他情况就是table不为空

有相等的就让e = 这个相等的元素没有相等的就找到这条链表的尾部，追加到尾部

resize方法（扩容和树化）扩容

扩容直接翻2倍

在上一个if语段里，如果进入了oldCap>0，且oldThr=0的情况下，newThr翻2倍任然是0，所以在这里需要再次判断将newThr设置为newCap*loadFactor

树化

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

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

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

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

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

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

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

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

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

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

扩容机制总结

4.4 get方法

get：

调用getNode，如果查到有值就返回该值，查不到就返回null getOrDefault：

调用getNode，如果查到有值就返回该值，查不到就返回设置的默认值 4.5 remove方法

remove(Object key)：删除一个KV。调用removeNode方法，分析写在图上了，显而易见 4.6 replace

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

Collection集合工具类源码解读（三） --- HashMap

Java相关栏目本月热门文章