原创

HashMap 测试「链表转红黑树以及扩容」

准备

首先创建了类 TreeNodeHashMap, 提供内部类MapKey。

MapKey:重写了hashCode使得hashCode碰撞极高. 在hashCode() 中,所有数字,hashCode全部给1,为了复现碰撞极高, 且更容易树化(超过8)。 非数字的均为2.
由于在TreeNodeHashMap测试的key都为数字,所以每次key的hashCode都相同, 都为1.实现了hashCode碰撞的目的。
TreeNodeHashMap: 在main方法中,实现了测试的逻辑。

代码及分析

public static void main(String[] args) {
        Map<MapKey,String> map = new HashMap<MapKey, String>();
        //第一阶段, hashCode的值全为 1
        for (int i = 0; i < 6; i++) {
            map.put(new MapKey(String.valueOf(i)), "A");
        }

        //第二阶段, hashCode的值全为 1
        for (int i = 0; i < 10; i++) {
            map.put(new MapKey(String.valueOf(i)), "A");
        }

        //第三阶段, hashCode的值全为 1
        for (int i = 0; i < 50; i++) {
            map.put(new MapKey(String.valueOf(i)), "A");
        }

        //第四阶段, hashCode的值全为 2
        map.put(new MapKey("Z"), "B");
        map.put(new MapKey("J"), "B");
        map.put(new MapKey("F"), "B");
        System.out.println(map);
    }

逐个阶段通过debug,查看map中的数据。
注意,在使用IDEA查看map的数据时,要设置view as Object.
debug-model.jpeg

第一阶段

  • 操作: 插入0-5总计6条数据, hashCode的值全为 1, 赋值6次。
  • 表现:1.1: 插入0-5总计6条数据, 这个时候桶中bin的数量小于TREEIFY_THRESHOLD,此时,没有发生任何非常规操作(树化、扩容等)。
    此时, HashMap中, 各属性值为下述:
    table: 
      16位长度的数组。
      有效数组节点: 1个。
      该有效节点上,链表长度为6. 头结点key=0, 尾结点key=5
    
    hashmap-table.png
    entrySet: 长度为6
    size=6
    modCount=6
    threshold=12
    loadFactor=0.75
    
    hashmap-3.png

第二阶段

这个时候该数组节点上,还是链表的数据结构。

  • 操作: 插入0-9总计10条数据。hashCode的值全为 1, 赋值10次。
  • 表现:
    • 2.1: 在进行数据i=0-5的前6条数据插入时,所有的属性(包含size、modCount、threshold)均不变。
    • 2.2: 进行i=6-7的第7、8条数据插入时,size=8、modCount=8、threshold=12。table: 16位长度的数组。
    • 2.3: 进行i=8的第9条数据插入时,size=9、modCount=9、threshold=24。table: 32位长度的数组。
      此处触发putVal方法中下述逻辑且满足tab.length < MIN_TREEIFY_CAPACITY(64), 导致扩容一次。threshold翻倍。
      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
             treeifyBin(tab, hash);
      
    • 2.4: 进行i=9的第10条数据插入时,size=10、modCount=10、threshold=48。table: 64位长度的数组。
      此处触发putVal方法中逻辑同上, 导致扩容一次。threshold翻倍。
      hashmap-5.png

第三阶段

  • 这个时候桶中bin的数量size)ormodCount大于了TREEIFY_THRESHOLD(8)且tab.length大于了MIN_TREEIFY_CAPACITY(64) ,因此,会树化。
  • 操作: 插入0-49总计50条数据。hashCode的值全为 1, 赋值50次。
  • 表现:
    • 3.1: 在进行数据i=0-9的前10条数据插入时,属性threshold不变,仍未48, 不扩容,不树化。table: 64位长度的数组。
    • 3.2: 进行i=10的第11条数据插入时(此时size=10、modCount=10, 才会触发根节点的treeifyBin操作)。此时,会触发树化
      这时,size=11、modCount=11、threshold=48。table: 64位长度的数组。第一个节点的链表被转换为了TreeNode.
      hashmap-6.png
    • 3.3: 在进行数据i=11-47的数据插入时,属性threshold不变,仍未48, 不扩容,。table: 64位长度的数组。第一个节点的为树 TreeNode.
    • 3.4: 在进行数据i=48的第49条数据插入时,触发if (++size > threshold)逻辑,导致扩容。 size=49、modCount=49、threshold=96
      if (++size > threshold)
            resize();
      
    • 3.5: 进行i=49的第50条数据插入时,无其他操作。

对这个输出map的值,可以看到是乱序的,因为是使用树形结构进行存储的。
hashmap-6-1.png

第四阶段

  • 这个阶段主要是测试,如果一个桶采用了树形结构存储,其他桶是不是也采用树形结构存储。结论是,如果其他桶中bin的数量没有超过TREEIFY_THRESHOLD,则用链表存储,如果超过TREEIFY_THRESHOLD ,则用树形存储。
  • 此时table已中第一个是红黑树,第二个依然是链表。
    所以由链表变成红黑树也只是当前桶挂载的bin会进行转换,不会影响其它桶的数据结构
    hashmap-7.png

源代码:
Demo: 测试链表转红黑树以及扩容

正文到此结束
广告是为了更好的提供数据服务
本文目录