HashMap初始化大小怎么定

在开发编码的过程，经常会遇到使用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。