HashMap的扩容机制

【饿了么、美团】外卖红包领取地址 >> 能省一点是一点

前提:基于1.8的源码进行分析。

ArrayList的扩容机制

与ArrayList中类似,HashMap也是使用数组进行数据的存储的,使用的是Node<K,V>[] table;
而与ArrayList不同的是,HashMap除了容量(table.length)外,还有2个额外的属性,threshold扩容阈值和loadFactor负载因子,且由于HashMap的存数据的特殊性(通过hash决定存在数组的哪个位置,hash冲突则在同个位置使用链表或红黑树存储),所以即使HashMap存储超过容量,也是没有问题的,那为什么要自动扩容呢?原因是为了尽量让数据均匀的分散在table这个数组中。

同样观察HashMap的2个构造函数源码:

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

无参的构造函数,只是简单指定了loadFactor负载因子,其他啥都没干。
指定初始容量和负载因子的构造函数,对负载因子和阈值进行了一个指定,其中阈值会通过tableSizeFor函数(HashMap中tableSizeFor方法解析)进行一个计算,这个函数的作用是计算出一个大于等于初始容量且为 2的N次方的最小整数。

为什么是2的N次方呢?
因为当table的长度为2的N次方时,可以保证 hash(key) & (length - 1) == hash(key) % length 这个等式成立,方便计算。

当我们往HashMap中添加数据时,最终调用的是putVal这个函数,看一下这个函数的源码(省略了部分代码)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        //第一次初始化table数组,进行扩容
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        //table数组对应hash后位置上无数据,直接设值
        tab[i] = newNode(hash, key, value, null);
    else {
        //table数组对应hash后位置上有数据,涉及数据的处理(key一致则替换,不一致转成链表或红黑树)
        HashMap.Node<K,V> e; K k;
        //此处省略部分代码
    }
    ++modCount;
    if (++size > threshold)
        //当前数据大于阈值,进行扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

可以看出HashMap是先插入数据,后进行扩容(如果需要的话)的。其中扩容的逻辑主要在resize函数中:

final HashMap.Node<K,V>[] resize() {
    HashMap.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;
        }
        //老容量大于0,直接翻倍扩容;老容量大于默认初始化容量,阈值也直接翻倍
        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
        //老容量为0,但阈值不为0,对应指定了初始容量的构造函数,新容量直接等于阈值(这里的阈值的值为tableSizeFor函数算出来的值)
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        //老容量和阈值都为0,对应无参构造函数,新容量和阈值分别等于默认值
        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;
    @SuppressWarnings({"rawtypes","unchecked"})
    //创建新的数组用于数据存储
    HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
    table = newTab;
    if (oldTab != null) {
        //重新分布数据代码,省略
    }
    return newTab;
}

扩容的逻辑主要是,根据已有数据的情况,计算出新的容量newCap和新阈值newThr,然后进行对应的数组的初始化,具体的逻辑见注释。
其中,新容量是直接使用左位移进行翻倍扩容,当老容量大于默认初始容量时,新阈值也是直接翻倍扩,否则会通过乘法的形式进行计算,也就是说,新阈值他不一定会是一个非常准确的数值(因为一直翻倍的话,肯定有精度问题,但是效率肯定比使用乘号提升了不少,至于为什么是大于默认初始容量的时候可以这么干,暂未看懂)

拿到新的容量newCap之后,就是创建新的数组用于存储数据,以及将老数据重新分布迁移到新数组的过程,这里的逻辑也挺复杂的,不过不在扩容的范畴中,至此HashMap的扩容就结束了。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

恰好时光 复古玻璃园艺雾化喷壶气压式盆栽多肉浇花家用室内小号洒水壶 透明
¥17.90
Daisy Leaf 日本304不锈钢漱口杯 情侣洗漱杯旅行牙刷杯牙缸儿童刷牙杯水杯
¥26.90
ROSELEX 飞机杯自慰器男用便携式夹吸器具透明手动慢玩成人情趣性用品玩具
¥44.00
普斯盾(pusidun)儿童口罩男童女童中小学生3-12岁一次性口罩三层防护细菌率大于95%独立包装50只蓝色
¥15.92
得力(deli) 函数科学计算器大学生考试考研专用多功能一建二建注会考试初高中生三角工程函数计算机器 1700P白色【航天联名款/240种功能】
¥23.90
曼秀雷敦 柔融盈润护唇膏-完熟白桃味 3.3g(滋润双唇 清新保湿 )
¥34.90
艾薇床头罩 全包床头套软包简约现代防尘北欧通用床头罩木床靠背套 松柏绿1.5m床
¥48.90
宠医森 宠物狗狗猫咪驱虫药体内外同驱滴剂打虫药幼猫幼犬去跳蚤蜱虫虱子除虫药 体外驱虫/1支/盒(猫用)
¥24.00