HashMap的容量与扩容

末蓝、 2022-07-25 16:55 233阅读 0赞

## HashMap的容量与扩容 ##

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

**（一）调用HashMap()构造方法**

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

这就完了，然后用于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);
    }

补充说明：也就是说容量只能是2的整数倍。  
所以经过这个方法之后，桶容量确定了，极限值也确定了，但是桶数组还是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();

参考博文：[http://blog.csdn.net/gaopu12345/article/details/50831631][http_blog.csdn.net_gaopu12345_article_details_50831631]

[http_blog.csdn.net_gaopu12345_article_details_50831631]: http://blog.csdn.net/gaopu12345/article/details/50831631