0.6、HashMap 源码学习-新增节点、扩容机制、红黑树转化机制

超、凢脫俗 2022-01-07 16:31 321阅读 0赞

### 文章目录 ###

*   *   *  前言
         *  HashMap 源码学习的基础准备工作
         *  学习方式
         *  版本声明：本文源码基于JDK1.8
         *  基本策略和方式
         *   *  从线到面的策略
             *  借助测试代码
             *  几个重要的内部变量
         *  进入源码
         *   *  从key定位到数组的位置
             *   *  第一步：对key.hashCode()的封装
                 *  第二步：将hash值定位到数组的具体位置
             *  新加节点触发的一系列逻辑
             *   *  源码:数组为null或长度为0 引发扩容
                 *  源码:map非空节点数大于扩容阈值引发扩容
                 *  源码:红黑树判断中引发扩容
                 *  源码：链表节点数等于8时转红黑树-未必真转
                 *  源码:新增节点 IfAbsent 的逻辑
             *  看put(key,value)和putIfAbsent(key,value)的返回值
         *  参考链接

### 前言 ###

> 体能状态先于精神状态，习惯先于决心，聚焦先于喜好。

### HashMap 源码学习的基础准备工作 ###

> [HashMap 的一些基础知识][HashMap]

### 学习方式 ###

> 笔者通过 一小段测试代码，然后开启 debug 运行模式，对 HashMap 代码逻辑进行跟踪。  
> 这样的好处非常明显，类似于拆毛衣，顺着一根线一直拽。

### 版本声明：本文源码基于JDK1.8 ###

> 本文展示的源码来自JDK1.8

### 基本策略和方式 ###

#### 从线到面的策略 ####

> 向 HashMap 对象放入第一个键值对时引起第一次扩容-从 null 到默认容量；  
> 向HashMap 对象放入第13个元素时，触发 扩容阈值 的扩容；  
> “Aa”.hashCode()和"BB".hashCode()结果一样，观察链表产生逻辑；  
> HashMap对象可以存储 null 值，null 值作为 key，按照hashCode()=0处理  
> HashMap同一个key只允许占用一个节点位置-后来者覆盖前者

#### 借助测试代码 ####

> 这代码可不是乱扔的 ,而是专门为debug 设计的，在关键位置设置 debug ,跟踪代码将有事半功倍的效果。

@Test
    /** * 观察一些基本流程 */
    public void testHashMap() { 
    	HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
    	//观察 HashMap 数组初始化-开始HashMap对象数组为null
    	map.put(1, 1);
    	//添加第2-第11个元素
    	for(int i=2;i<=12;i++) { 
    		map.put(i, i);
    	}
    	//观察key值覆盖-返回旧值
    	System.out.println(map.put(12, 1212));
    	//观察第一次扩容-添加第13个元素
    	map.put(13, 13);
    }
    
    /* * 观察新键值对放入链表 */
    @Test
    public void testLink(){ 
    	HashMap map=new HashMap();
    	map.put("Aa","AA");
    	map.put("BB","BB");
    	map.get("Aa");
    }
    
     /* * IfAbsent 在value时无效 * IfAbsent的作用是，如果key已经存在则不允许覆盖，但是当value为null时，这个命令无效 */
    @Test
    public void testAbsent(){ 
        HashMap map=new HashMap();
    
        map.put("Aa","AA");
        map.put("BB",null);
        System.out.println(map.get("Aa"));
        System.out.println(map.get("BB"));
        //map.put("BB","CC");
        map.putIfAbsent("Aa","Aa2");
        map.putIfAbsent("BB","BB2");
        System.out.println(map.get("Aa"));//不会被替换
        System.out.println(map.get("BB"));//会被替换
    }

#### 几个重要的内部变量 ####

> HashMap 内部维护了几个重要的变量，用于在新加元素时进行是否扩容、是否链表转红黑树的判断。

/**默认数组长度:16*/
    int DEFAULT_INITIAL_CAPACITY 
    /** 最大容量*/
    int MAXIMUM_CAPACITY 1<<30
    /**加载因子:扩容时判断.有缩容吗?貌似没有*/
    float DEFAULT_LOAD_FACTOR = 0.75f ;
    /**链表新增节点数达到8个时,该链表改为红黑树*/
    int TREEIFY_THRESHOLD = 8;
    /**红黑树节点减少达到6个时,红黑树恢复为链表结构*/
    int UNTREEIFY_THRESHOLD = 6;
    
    /** * 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 *（即 将链表 转换成红黑树） * 否则，若桶内元素太多时，则直接扩容，而不是树形化 * 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD * */
    int MIN_TREEIFY_CAPACITY = 64;
    /**目前 HashMap 包含的所有非空节点数*/
    transient int size;

### 进入源码 ###

#### 从key定位到数组的位置 ####

> 哈希表在存储元素前，需要通过hash散列函数对新元素的位置进行计算，一般的对象都是 hashCode（）方法，不同的类型可能会覆盖重写。  
> 在源码中，HashMap 对key在数组中的定位分为了两步，第一步是对 hashCode（）进行了二次封装，第二部是用 & 运算确定第一步hash值在数组中的下标，从而确定这个key在数组中的位置。

##### 第一步：对key.hashCode()的封装 #####

/**HashMap 新增元素调用 hash（key） 方法计算hash值*/
    public V put(K key, V value) { 
         return putVal(hash(key), key, value, false, true);
     }
     /**hash()函数*/
    static final int hash(Object key) { 
          int h;
          //如果新增键值对key为null，则hash值为0,
          //否则计算 key.hashCode(),然后和 key.hashCode()>>>16 进行 ^运算
          //int在Java中为32位，>>>16 将得到一个前16位为0后16位为原先hashCode（）值高16位的组合值-（补码的角度）
          //这样在key不为null时，相当于key的原hash值与hash值补码的高16位进行 ^运算
          //1111 1111
          //0000 1111
          //1111 0000
          //最终结果是 原hash值补码的高16位不变，后16位进行随机变化
          //这样处理的原因是为了进一步增大hash值的分散程度
          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }

##### 第二步：将hash值定位到数组的具体位置 #####

> HashMap 内部有一个 Node 节点类型的数组，新增节点可以保存到数组上，也可能保存到数组节点连接的链表或红黑树上。  
> 对于新增节点，需要先判断该节点对应数组的哪一个位置。

/**HashMap 新增元素调用 hash（key） 方法计算hash值 hash(key)计算出了hash值*/
    public V put(K key, V value) { 
      return putVal(hash(key), key, value, false, true);
     }
    
    /**在 putVal 方法内部*/
    ···
    //tab 用于临时取代数组
    //n则为数组的当前长度
    //p用于获取当前key对应的数组位置的节点-结果可能为null
    Node<K,V>[] tab; int n;Node<K,V> p
    ···
    tab = table;
    n = tab.length;
    ···
    //这里展示 hash 值如何对应到 数组的某一个位置
    //n为数组的长度，之前强调其为2的倍数，其不小于16，
    //那么 n-1 用二进制表示就是 10000-1 100000-1 1000000-1
    //即 1111 11111 111111
    //使用这个值对 hash 值进行 & 运算的结果 正好是在数组下标的范围内 0-15，0-31,0-63
    //这样就定位到 key 在数组中的位置了
    //额外插一句，在jdk1.7之前，这里的算法不是位运算，而是除法，对计算机来说，
    //位运算的效率显然是最高的,这也是jdk1.8的一个优化举措
    if ((p = tab[i = (n - 1) & hash]) == null)
    ···

#### 新加节点触发的一系列逻辑 ####

> 源码使用了这样的策略：  
> 1、借助临时变量保存HashMap对象当前数组等数据。  
> 2、对当前临时变量进行判断。  
> 3、如果需要扩容则新建一个数组，然后重hash，将新数组赋值给原数组变量。  
> 4、如果不涉及扩容，而是新增节点，则分为三种情况。  
> 4.1、新节点，数组位置为null，则直接将节点保存到数组；  
> 4.2、如果新节点hash定位的数组位置不为null,则需要将其添加到该位置对应的节点后面，判断该节点是普通节点还是红黑树节点，如果是普通节点，则将其添加到链表末端，如果在添加完毕后链表长度达到8，那么再次判断数组长度是否大于64，如果满足这俩条件，则该链表转化为红黑树，否则触发扩容  
> 4.3、如果新节点hash定位的数组位置不为null,则需要将其添加到该位置对应的节点后面，判断该节点是普通节点还是红黑树节点，如果是红黑树节点，则将其添加到红黑树中  
> 5、对于key相同的旧节点覆盖的逻辑：  
> 5.1、如果一个旧键值对的value为null，那么只要新节点的key和旧节点key相同，该value一定会被替换为新值  
> 5.2、如果使用 hashMap.putIfAbsent(“Aa”,“Aa2”);命令，只有key不存在于旧节点中时，才会将新键值对保存到map，但是5.2同样遵循5.1的规则  
> 5.3、对于 put(key,value),如果key对应节点已存在,不论key是不是null,新节点就会覆盖旧节点的value,即使value一样,或者value为null  
> put之后返回被替换的旧值,对于非覆盖新增新的节点返回null,对于null还是返回null  
> key为null,节点存在链表数组0的位置,因为hashcode=0  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jlc3RjeHg_size_16_color_FFFFFF_t_70]

##### 源码:数组为null或长度为0 引发扩容 #####

> java.util.HashMap.putVal

![在这里插入图片描述][20190630145100311.png]

##### 源码:map非空节点数大于扩容阈值引发扩容 #####

> java.util.HashMap.putVal  
> 注意：这里的非空节点指定是被调用者保存的节点的数目，而不是初始化时空数组时的状态，HashMap允许保存一个key为null的键值对，这个调用者保存的空节点是被包含的。  
> 源码使用 int size 来做记录

![在这里插入图片描述][20190630145354584.png]

##### 源码:红黑树判断中引发扩容 #####

> java.util.HashMap.treeifyBin  
> 在调用 treeifyBin(tab, hash);将链表转红黑树时，该方法会在增加一个判断  
> 即数组不为null 并且，数组长度 > 64

static final int MIN_TREEIFY_CAPACITY = 64;

![在这里插入图片描述][20190630145655195.png]

##### 源码：链表节点数等于8时转红黑树-未必真转 #####

> java.util.HashMap.putVal  
> 源码使用for循环计数，当计数值达到7（因为是从0开始计数，故节点数为8个）时，会调用 treeifyBin方法，当数组满足长度大于64时将会转化为红黑树

static final int TREEIFY_THRESHOLD = 8;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jlc3RjeHg_size_16_color_FFFFFF_t_70 1]

##### 源码:新增节点 IfAbsent 的逻辑 #####

> java.util.HashMap.putVal  
> IfAbsent =true 表示与新节点相同key的旧节点不会被覆盖，但是当旧节点的value值为null时，ifAbsent的设置是无效的  
> 在HashMap中，put(K,V) 命令 ifAbsent=false；putIfAbsent(K<V)命令，ifAbsent=true  
> 真正替换原节点的逻辑是在 afterNodeAccess(e); 中完成的  
> ![在这里插入图片描述][20190630150553963.png]

#### 看put(key,value)和putIfAbsent(key,value)的返回值 ####

> 从 put 返回值看 hashMap添加节点过程  
> 新节点返回null,覆盖节点返回旧值-不管是否允许覆盖  
> 如果put或者puIfAbsent 的key是null, 肯定会覆盖,只要覆盖就返回旧值(value),即使旧值为null

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jlc3RjeHg_size_16_color_FFFFFF_t_70 2]

### 参考链接 ###

> \[1\]、https://blog.csdn.net/DZ266912/article/details/78233465  
> \[2\]、https://blog.csdn.net/DZ266912/article/details/78233777  
> \[3\]、https://blog.csdn.net/dz266912/article/details/78278570

[HashMap]: https://blog.csdn.net/bestcxx/article/details/93912614
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jlc3RjeHg_size_16_color_FFFFFF_t_70]: /images/20211220/f2e520aada6f49cda7da39b76d41bb28.png
[20190630145100311.png]: /images/20211220/c1b64ed429f94565a00e556d34444004.png
[20190630145354584.png]: /images/20211220/4d6cd2c9ec6e4d168c052f101095837d.png
[20190630145655195.png]: /images/20211220/6e9abbf65fe94021b94c6ac94541840b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jlc3RjeHg_size_16_color_FFFFFF_t_70 1]: /images/20211220/79da39b1772841448c56b820caa2bc70.png
[20190630150553963.png]: /images/20211220/7b1d5d9cc691487fb5f95f640da17bc8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jlc3RjeHg_size_16_color_FFFFFF_t_70 2]: /images/20211220/a2d3c80f7ad746f0a3226925410414ba.png