如何设置 HashMap 初始化大小

关注

发布于: 2021 年 06 月 03 日

在开发编码的过程，经常会遇到使用HashMap的场景。在第一版的阿里巴巴 Java 开发手册中，有建议在集合初始化时，指定集合的初始值大小。在看到此建议之前，大多数的使用时不会自己指定HashMap的初始值大小，即便是在已知其中会存放的元素的数量；而在看到此建议后，知道了需要指定初始值大小，而这个初始值大小指定为多少才合适？比如已知HashMap会存放 3 个元素时，指定的初始值大小是多少。在 CR 中发现，很多人指定初始值大小与存放的元素数量大小一样，这样的做法实际上是不合理的。对于初始化大小值怎么定，在阿里 Java 开发手册（嵩山版）中已给出说明，如下：

从上可知initialCapacity的计算公式，下面简单介绍下为什么是这样计算的。

说明

指定合理的initialCapacity的即，在已知HashMap会存放的元素的数量时设置的容量不会引起扩容，扩容意味着重建 hash 表（耗时）。

HashMap 中几个属性值说明

capacity:容量，Node 数组的大小（桶的数量），值为 2 的 N 次幂

threshold:扩容阈值，等于 capacity * load factor 当 size 大于此值时进行扩容

loadFactor：负载因子，默认为 0.75f

capacity 与 initialCapacity 的关系

HashMap设置初始容器的构造方法如下，也就是程序员可以指定initialCapacity

  public HashMap(int initialCapacity) {.        // DEFAULT_LOAD_FACTOR = 0.75f        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    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);    }

复制代码

其中默认负载因子DEFAULT_LOAD_FACTOR=0.75f，最大容量 MAXIMUM_CAPACITY=2^30。

在上面的构造方法中，会设置HashMap的负载因子loadFactor为默认的0.75f；以及设置扩容阈值 threshold，通过tableSizeFor(initialCapacity)方法设置:

  /**     * Returns a power of two size for the given target capacity.     */    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;    }

复制代码

tableSizeFor 方法最终返回是，比给定 cap 值大且最接近的 2 的幂次方的整数，比如 cap=3，tableSizeFor(3)=4;cap=4，tableSizeFor(4)=4;cap=7，tableSizeFor(7)=8

>>>无符号右移，右移时不关注符号位，右移后前面补 0

从上可知，在使用new HashMap(int initialCapacity)初始化HashMap时，会根据initialCapacity设置阈值threshold，threshold的值为比initialCapacity大且最接近的 2 的幂次方的整数。

那与 capacity 值的关系呢？可通过下面方法查看：

  final int capacity() {        return (table != null) ? table.length :            (threshold > 0) ? threshold :            DEFAULT_INITIAL_CAPACITY;    }

复制代码

当new HashMap(int initialCapacity)初始化HashMap时，还未 put 元素时，table==null，那么 capacity 的值就等于上面计算出的threshold，即capacity的值为比initialCapacity大且最接近的 2 的幂次方的整数。

知道了capacity的值以及loadFactor，可以反过来计算出当HashMap的元素达到多少时会触发扩容。

所以，除了直接使用最上面给出的公式计算出initialCapacity，还可以这样，三步反推法：

1.取大于（需要存储的元素数量）且最接近的 2 的幂次方的整数，即为 C1，比如要存储 3 个元素，则 C1=4；
2.计算 C1 * loadFactor，记为 L1，比如要存储 3 个元素，则 L1=3；
3.比较 L1 与（需要存储的元素数量），如果 L1<（需要存储的元素数量）,说明会触发扩容，则 initialCapacity 取大于 C1 且最接近 C1 的 2 的幂次方的整数；如果 L1>=（需要存储的元素数量）,说明不会触发扩容，则 initialCapacity 取 C1。

看起来有点绕，其实就是反推，用起来也比较方便，最终的效果与公式计算的是一样的。

扩容

从上面的构造方法可以看出HashMap在初始化时不会去初始化 table，table 数组的初始化发生在第一次执行 put 时；在接下来的 put 中，当元素的数量大于阈值（capacity * load factor）则会触发扩容。

  public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);    }
    /**     * Implements Map.put and related methods.     *     * @param hash hash for key     * @param key the key     * @param value the value to put     * @param onlyIfAbsent if true, don't change existing value     * @param evict if false, the table is in creation mode.     * @return previous value, or null if none     */    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node<K,V>[] tab; Node<K,V> p; int n, i;        // 第一次put时table == null,会调用resize()        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);        else {            Node<K,V> e; K k;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof TreeNode)                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);            else {                for (int binCount = 0; ; ++binCount) {                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash);                        break;                    }                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            if (e != null) { // existing mapping for key                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;        if (++size > threshold)            resize();        afterNodeInsertion(evict);        return null;    }

复制代码

初始化 table

如上所示：

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

复制代码

如下图所示，oldThr = threshold 为初始化 HashMap 时设置的阈值 threshold（根据 initialCapacity）,此时 oldCap 是为 0。找到下图中的两个红色框，第一个红色框中 newCap = oldThr = threshold 及 newCap 等于初始化时计算的 threshold 值；第二个红色框会创建一个数组，数组大小为 newCap 也就是 threshold 值。

也就是说，在第一次 put 会新建一个 table 数组，数组的大小为 threshold 的值（大于 initialCapacity 且最接近 2 的幂次方的整数）。

需要注意的是，在使用 new HashMap(int initialCapacity)时会初始化设置 threshold（大于 initialCapacity 且最接近 2 的幂次方的整数），在接下来的第一次 put 时会对 threshold 值进行更新，也就是上图 resize 中的这一段逻辑：

    if (newThr == 0) {            // 计算新的阈值            float ft = (float)newCap * loadFactor;            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                      (int)ft : Integer.MAX_VALUE);        }        threshold = newThr;

复制代码

通过下面这个例子可以更清晰的看出来：

public class MapDemo {
    public static void main(String[] args) throws Exception {        HashMap<String, String> map = new HashMap<>(4);        System.out.println("初始化HashMap后，threshold:" + getThreshold(map));        map.put("book1", "java");        System.out.println("第一次put后，threshold:" + getThreshold(map));    }
    /**     * 通过反射获取HashMap的threshold值     * @param map     * @return     * @throws Exception     */    private static int getThreshold(HashMap map) throws Exception {        Field field = map.getClass().getDeclaredField("threshold");        field.setAccessible(true);
        int threshold = field.getInt(map);
        return threshold;    }}

复制代码

输出结果如下：

初始化 HashMap 后，threshold:4 第一次 put 后，threshold:3

扩容

扩容时机：在每一次 put 时，都会通过++size 是否大于 threshold 来决定是否调用 resize()方法，也就是当 Map 中键值对的数量加 1 大于阈值时会进行扩容。

每次扩容会创建一个老的 table 两倍大的数组，如下图 newCap = oldCap << 1:

特殊情况

假设已知且确认要插入HashMap中的元素数量正好等于某 2 的幂次方 * 0.75，比如元素个数为 3（4*0.75）、6（8*0.75）、12（16*0.75）等时，使用公式计算出来的 initialCapacity 值分别为 5、9、17，实际上 initialCapacity 的值分别设置为 4、8、16 也不会触发扩容。当然，使用上述公式计算出来的 5、9、17 也是不会触发扩容，只是会多用一些内存空间且保留了继续插入元素不会马上触发扩容。当且仅当，可确定要插入元素数量满足上述条件这种特殊情况时是这样。

如果使用前面介绍的三步反推法，即可得出最省空间的值。

总结

本文介绍了在开发时，已知 HashMap 将插入的元素数量时，怎么去计算 initialCapacity 初始容量赋值，一种是在阿里开发手册中给出的公式 initialCapacity = (需要存储的元素个数 / 负载因子) + 1；另一种是三步反推法。同时，介绍了 HashMap 初始化的过程，初始创建 table 数组的过程，阈值 threshold 在 HashMap 初始化及第一次 put 时的变化；以及扩容的时机和每次扩容的大小，但对于扩容 rehash 的过程没有进行详细展开。

通过本文，可以在开发中合理的初始化 HashMap 的初始容量 initialCapacity。

ps 建议 initialCapacity 尽量取 2 的幂次方，虽然不取 2 的幂次方效果也一致,initialCapacity=5 和 initialCapacity=8 的效果是一样的，但建议使用 initialCapacity=8。

发布于: 2021 年 06 月 03 日阅读数: 20

原文链接:【http://xie.infoq.cn/article/a94966070683b4677ce1cf2ce】。文章转载请联系作者。

Hex

关注

还未添加个人签名 2018.05.24 加入

还未添加个人简介

发布

暂无评论

创作场景

如何设置 HashMap 初始化大小

说明

HashMap 中几个属性值说明

capacity 与 initialCapacity 的关系

扩容

初始化 table

扩容

特殊情况

总结

Hex

评论