• 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 先看看属性

• 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 构造方法

一共四个：

• 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分析扩容机制(重点)

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

putVal方法

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方法（扩容和树化）

扩容

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表

树化

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

如图是一个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集合工具类源码解读（三） --- HashMap4、HashMap的全部内容，更多相关Collection集合工具类源码解读（三）内容请搜索靠谱客的其他文章。