HashMap的容量与扩容

有几个重要的常量:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//默认的桶数组大小
static final int MAXIMUM_CAPACITY = 1 << 30;//极限值(超过这个值就将threshold修改为Integer.MAX_VALUE(此时桶大小已经是2的31次方了),表明不进行扩容了)
static final float DEFAULT_LOAD_FACTOR = 0.75f;//负载因子(请阅读下面体会这个值的用处)

(一)调用HashMap()构造方法

这个构造方法长这样:

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; //设置一个默认的负载因子,默认为0.75,下面说它有啥用
}

这就完了,然后用于hash的桶数组为null,当我们第一次put的时候,会到达这段代码:

Node<K,V>[] tab; int n;
    //table就是桶数组,初始为null
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

所以会进入resize()方法,到达这段代码:

//取消多余的代码,我直接贴上进入的这个分支的代码
else {
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

newCap的意思是:即将用于hash的桶数组的长度,这里的默认值是16
newThr的意思是:当桶中的键值对的个数超过这个值时就进行扩容,这时候上面提到的负载因子就起作用了,所以这里的newThr为0.75×16 = 12

所以经过这个默认构造方法,并且进行第一次put后,桶数组建立了,桶容量为16,极限值为12。

(二)调用HashMap(int initialCapacity)构造方法

public HashMap(int initialCapacity) {
    //这个方法实际调用另一个构造方法,所以这个构造方法就不分析了,直接看第三个的分析
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

(三)调用HashMap(int initialCapacity, float loadFactor)构造方法

public HashMap(int initialCapacity, float loadFactor) {
    //桶数组的大小小于0时抛异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
    //如果桶数组的大小超过最大值,则简单的将桶容量修改为最大值2的30次方
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //如果负载因子不符合规范,那么抛异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
    this.loadFactor = loadFactor;
    //这个意思是根据桶数组的大小求一个“极限值threshold”,当桶中的键值队个数超过这个大小就进行扩容
    //tableSizeFor方法求得的数字是刚超过initialCapacity的一个2的n次方的数,例如initialCapacity是1000,那么得到的threshold就是1024,这个方法很奇特,我没看懂,感兴趣的自己去研究。
    this.threshold = tableSizeFor(initialCapacity);
}

所以经过这个方法之后,桶容量确定了,极限值也确定了,但是桶数组还是null。
当第一次put时,触发如下代码:

//发现桶数组是null,所以需要新建一个桶数组
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

接着看resize()中触发了哪些代码:

Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//看这里,oldCap会是0
int oldThr = threshold;//看这里,oldThr不会是0,因为有tableSizeFor()方法,确保oldThr至少是1
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
}
//所以肯定会进入这个分支,将桶数组的大小改为极限值大小。然后在下面创建一个newCap大小的桶数组
else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;

然后还会进入下面这个分支:

if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
}

这个分支会按负载因子设置极限值

(四)超过极限值后的扩容

在每次put之后,会有下面这个判断:

if (++size > threshold)
    resize();

就是说超过极限值时会进行扩容,扩容方式如下:

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;
    }
    //如果我们是这样调用:HashMap(7,任意满足条件的值),那么经过第一次调用put()会初始化桶数组的大小和极限值一样,这里即为8。所以这里不会进入这个分支,但是newCap会变为16
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
}
//所以会进入这里
if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
            (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;//计算的出这里的threshold即极限值会由刚才的8变为12(和负载因子大小有关)

接上面这个例子,下一次扩容会如何?

if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    //因为桶容量变为了16,所以这次会进入这个分支,桶容量和极限值都会加倍。
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
}

直到…………
当桶容量加倍到最大值会怎么样?

//因为每次都是加倍,所以最终肯定会加倍到MAXIMUM_CAPACITY,会进入这个分支。
if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return oldTab;
}

桶容量变为最大值时,紧接着的一次扩容只是简单的将极限值修改为Integer.MAX_VALUE。桶数组大小并不会继续加倍

(五)如果HashMap中的键值对数量超过Integer.MAX_VALUE了呢?

我们仔细看一下这段代码:

//这个size类型是int,那么最大就是Integer.MAX_VALUE,所以不会有++size > threshold的情况,往后都不会进行扩容了。
if (++size > threshold)
    resize();

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/116

(0)
geekgaogeekgao博主
上一篇 2020年5月25日
下一篇 2017年11月21日

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

评论列表(2条)

GitHub
分享本页
返回顶部

Warning: error_log(/usr/local/lighthouse/softwares/wordpress/wp-content/plugins/spider-analyser/#log/log-2920.txt): failed to open stream: No such file or directory in /usr/local/lighthouse/softwares/wordpress/wp-content/plugins/spider-analyser/spider.class.php on line 2900