hashmap 的扩容和树形化

川长思鸟来 2021-09-21 01:58 194阅读 0赞

### 一、树形化 ###

//链表转红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;
    //红黑树转链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    /** *最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树） *否则，若桶内元素太多时，则直接扩容，而不是树形化 *为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD **/
    static final int MIN_TREEIFY_CAPACITY = 64;

第一个和第二个变量没有什么问题，关键是第三个：是表示只有在数组长度大于64的时候，才能树形化列表吗？

> 实际上，这两个变量是应用于不同场景的。

链表长度大于8的时候就会调用treeifyBin方法转化为红黑树，但是在treeifyBin方法内部却有一个判断，当只有数组长度大于64的时候，才会进行树形化，否则就只是resize扩容。

> 为什么呢？

因为链表过长而数组过短，会经常发生hash碰撞，这个时候树形化其实是治标不治本，因为引起链表过长的根本原因是数组过短。执行树形化之前，会先检查数组长度，如果长度小于 64，则对数组进行扩容，而不是进行树形化。

所以发生扩容的时候是在两种情况下

*  超过阈值
 *  链表长度超过8，但是数值长度不足64

--------------------

### 二、扩容机制 ###

hashmap内部创建过程  
构造器（只是初始化一下参数，也就代表着只有添加数据的时候才会构建数组和链表）—调用put方法—put方法会调用resize方法（在数组为空或者超过阈值的时候，put方法调用resize方法）

hashmap是如何扩容的

**1.hashmap中阈值threshold的设定**

刚开始，阈值设定为空

*  当未声明的hashmap的大小的时候，阈值设定就是默认大小16\*默认负载因子0.75=12
 *  当声明hashmap的大小的时候，**会先调用一个函数把阈值设定为刚刚大于设定值的2的次方（比如说设定的大小是1000，那阈值就是1024），然后在resize方法中，先把阈值赋给容量大小，然后在把容量大小\*0.75在赋值给阈值。**

代码如下：

Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) { 
                if (oldCap >= MAXIMUM_CAPACITY) { 
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {                // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) { 
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;

**2.数据转移**

*  当数组为null的时候，会创建新的数组
 *  当数组不为空，会把容量和阈值均\*2，并创建一个容量为之前二倍的数组，然后把原有数组的数据都转移到新数组。

假设扩容前的 table 大小为 2 的 N 次方，元素的 table 索引为其 hash 值的后 N 位确定  
扩容后的 table 大小即为 2 的 N+1 次方，则其中元素的 table 索引为其 hash 值的后 N+1 位确定，比原来多了一位

*  转移数据不在跟1.7一样重新计算hash值（计算hash值耗时巨大），只需要看索引中新增的是bit位是1还是0,
    
     *  若为0则在新数组中与原来位置一样，
     *  若为1则在新 原位置+oldCap 即可。

--------------------

### 三、容量计算公式 ###

扩容是一个特别耗性能的操作，所以当程序员在使用 HashMap 的时候，估算 map 的大小，初始化的时候给一个大致的数值，避免 map 进行频繁的扩容。

HashMap 的容量计算公式 ：size/0.75 +1 。

原理就是保证，阈值（数组长度\*0.75）>实际容量