Java中HashMap 初始化时容量（参数）如何设置合适？

2022-07-12 22:22:02

问题引入

注：本文代码源自java 9。

阿里的插件对于初始化HashMap时，调用无参构造方法，提示如下：
那么问题来了，如果已知需要向 map 中 put n次，那么需要设定初始容量为多少？
单纯的我今天上午还认为是合理的容量是 n + 1 即可，直到看了源码；
应注意，map.size 获取的是当前map中键值对的个数，而不是容量。

当初始化的时候，没有指定容量，情况如何？

直接调用如下构造函数（无参）

    /**

     * Constructs an empty {@code HashMap} with the default initial capacity

     * (16) and the default load factor (0.75).

     */

    public HashMap() {

        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

    }

首先应该清楚，loadFactor 是装载因子（通俗来讲，若值为0.5f，那么当map元素达到容量*0.5f的时候，就应该做扩容等操作）
HashMap对象实际上只有 threshold（临界值，阈值）属性，每次put()后，需要比较的是阈值与size（map中已有键值对的个数）
至于容量属性，实际上各个方法中用的是 transient Node<K,V>[] table; 中 table 的长度
Hashmap结构可参考 http://www.importnew.com/20386.html
本构造方法上说明：构造了一个空的HashMap，默认容量为16，装载因子为0.75。
然而可以清楚地看到，此构造方法只是将常量 DEFAULT_LOAD_FACTOR赋值给装载因子，但没有设定容量。
当调用put()时，如下方式设定了初始容量。
调用 putVal(hash(key), key, value, false, true)

public V put(K key, V value) {

        return putVal(hash(key), key, value, false, true);

    }

在putVal()中，进入第一个if，调用resize()

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

               boolean evict) {

    Node<K,V>[] tab; Node<K,V> p; int n, i;

    if ((tab = table) == null || (n = tab.length) == 0)

        n = (tab = resize()).length;

   //省略无关代码

}

在下方代码中，oldCap 与 oldThr 初始都为0，故直接进入else{}

final Node<K,V>[] resize() {

    Node<K,V>[] oldTab = table;

    int oldCap = (oldTab == null) ? 0 : oldTab.length;

    int oldThr = threshold;

    int newCap, newThr = 0;

    if (oldCap > 0)

       //省略无关代码

    else if (oldThr > 0) // initial capacity was placed in threshold

        //省略无关代码

    else {               // zero initial threshold signifies using defaults

        newCap = DEFAULT_INITIAL_CAPACITY;//设定 newCap  = 16

        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//设定 newThr  = 16 * 0.75 = 12

    }

        threshold = newThr;//将对象的 threshold（临界值，阈值） 属性设置为 newThr

            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

        table = //将对象的 table 属性设置为刚实例化的 newTab

        //省略无关代码

        return newTab;//并返回

综上，默认无参的构造方法设定装载因子为0.75f，初始容量为16在调用put()时，设置为16。

当我们指定容量为n的时候，情况如何？

即: Map<String,String> map = new HashMap<>(n);
当指定容量时，调用如下构造方法：

/**

     * Constructs an empty {@code HashMap} with the specified initial

     * capacity and the default load factor (0.75).

     *

     * @param  initialCapacity the initial capacity.

     * @throws IllegalArgumentException if the initial capacity is negative.

     */

    public HashMap(int initialCapacity) {

        this(initialCapacity, DEFAULT_LOAD_FACTOR);

    }

此方法将自定义容量作为参数1，将默认常量0.75f作为参数2，调用如下构造方法。

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);

}

此方法先做了对于容量与装载因子值的合理性做了判断与处理；
设定装载因子值为0.75f，设置threshold 属性为 tableSizeFor()参数为n时的返回值。
对于tableSizeFor(initialCapacity)，如下：

static final int tableSizeFor(int cap) {

    int n = cap - 1;

    n |= n >>> 1;

    n |= n >>> 2;

    n |= n >>> 4;

    n |= n >>> 8;

    n |= n >>> 16;

    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}

也就是传入 n 的时候，返回了第一个比 n 大的 2的幂（2.4.8.16.32.64...）的数，例 n为 10，返回16；n为17 返回 32.
具体实现原理可参考：http://blog.csdn.net/fan2012huan/article/details/51097331
同上，对于在put方法中，对象的table属性仍然为null，还是需要resize()；
本次调用与上次不同在于，threshold属性已经被赋值，假设值为 m(m>0)；

final Node<K,V>[] resize() {

    Node<K,V>[] oldTab = table;

    int oldCap = (oldTab == null) ? 0 : oldTab.length;//oldCap 值 为 0

    int oldThr = threshold;//oldThr 值 为 m，m > 0

    int newCap, newThr = 0;

    if (oldCap > 0) {

        //省略无关代码

    }

    else if (oldThr > 0) // initial capacity was placed in threshold

        newCap = oldThr;//newCap 被赋值为 m

     //省略无关代码

    if (newThr == 0) {

        float ft = (float)newCap * loadFactor;//ft为m*0.75

        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

                  (int)ft : Integer.MAX_VALUE);

        //在newCap 与ft 小于最大容量时(不满足时不讨论)，执行  newThr  = ft

    }

    threshold = newThr;//threshold 被再次赋值为 ft--->m*0.75

    @SuppressWarnings({"rawtypes","unchecked"})

        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

    table = newTab;//容量赋值为 m

    //省略无关代码

    return newTab;

}

综上：当我们构造新的HashMap的时，传入容量为n（假设为9），构造方法根据n得到阈值m（16）

当调用put()时，直接将阈值设置为m*0.75（12），将容量设置为 m（16）
也就是说，当n不是2的幂的时候，会根据n找到合适的数 m，并认为m是新的容量，阈值是m*0.75！

说了那么多，初始化的时候，到底怎么设置参数n

如下是put方法的最后一步，需要进行的如下方式的验证：

if (++size > threshold)

            resize();

为了防止调用resize()，需要保证元素数量小于阈值（不可等于！）。
综上，需要根据调用put(key,value)的次数count（准确的说是key不重复时），找到第一个比 n 大的 2的幂的数m

判断装载因子loadFactor（默认0.75）*m是否仍然不小于count，若满足则设置为count，否则设置为2*m或者m+1
例1，当我们需要在map里面装 100个元素时，已知128是第一个大于100并且是2的幂的数，但128*0.75 = 96 还是小于100，

那么显然129-256(闭区间)作为初始化的参数更合适。
例2，当我们需要在map里面装 80个元素时，已知128是第一个大于80并且是2的幂的数，且128*0.75 = 96 还是大于80，

那么显然64-128(左开右闭)作为初始化的参数更合适。
例3，当我们需要在map里面装 12个元素时，应选用16为初始容量！

参考文章：http://blog.csdn.net/fan2012huan/article/details/51087722

http://yikun.github.io/2015/04/01/Java-HashMap工作原理及实现/

https://www.cnblogs.com/coderxuyang/p/3718856.html

码农公寓

问题引入

当初始化的时候，没有指定容量，情况如何？

当我们指定容量为n的时候，情况如何？

说了那么多，初始化的时候，到底怎么设置参数n

相关文章