关于HashMap默认容量的选择

集合是Java日常开发中经常会使用到的，而作为一种典型的K-V结构的数据结构，HashMap对于Java开发者一定不陌生。

在日常开发中，经常会像如下方式创建一个HashMap：

Map<String, String> map = new HashMap<String, String>();
1

但是，大家有没有想过，上面的代码中，我们并没有给HashMap指定容量，那么，这时候一个新创建的HashMap的默认容量是多少呢？为什么呢？

什么是容量

在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，插入和删除容易。HashMap就是将数组和链表组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组。

在HashMap中，有两个比较容易混淆的关键字段：size和capacity ，这其中capacity就是Map的容量，而size称之为Map中的元素个数。

简单打个比方：HashMap就是一个“桶”，那么容量（capacity）就是这个桶当前最多可以装多少元素，而元素个数（size）表示这个桶已经装了多少元素。

如下代码：

Map<String, String> map = new HashMap<String, String>();

map.put("hollis", "hollischuang");



Class<?> mapType = map.getClass();

Method capacity = mapType.getDeclaredMethod("capacity");

capacity.setAccessible(true);

System.out.println("capacity : " + capacity.invoke(map));



Field size = mapType.getDeclaredField("size");

size.setAccessible(true);

System.out.println("size : " + size.get(map));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

输出结果：

capacity : 16、size : 1
1

上面定义了一个新的HashMap，并向其中put了一个元素，然后通过反射的方式打印capacity和size，其容量是16，已经存放的元素个数是1。

通过前面的例子可以发现，创建一个HashMap的时候，如果没有指定其容量，那么会得到一个默认容量为16的Map，那么，这个容量是怎么来的呢？又为什么是这个数字呢？

容量与哈希

要想讲清楚这个默认容量的缘由，首先要知道这个容量有什么用？

我们知道，容量就是一个HashMap中"桶"的个数，那么，当我们想要往一个HashMap中put一个元素的时候，需要通过一定的算法计算出应该把他放到哪个桶中，这个过程就叫做哈希（hash），对应的就是HashMap中的hash方法。

hash方法的功能是根据Key来定位这个K-V在链表数组中的位置的。也就是hash方法的输入应该是个Object类型的Key，输出应该是个int类型的数组下标。如果让你设计这个方法，你会怎么做？

我们只要调用Object对象的hashCode()方法，该方法会返回一个整数，然后用这个数对HashMap的容量进行取模就行了。

如果真的是这么简单的话，那HashMap的容量设置就会简单很多了，但是考虑到效率等问题，HashMap的hash方法实现还是有一定的复杂的。

hash的实现

接下来就介绍下HashMap中hash方法的实现原理。参照文章：Map中的hash()解析

具体实现上，由两个方法 int hash(Object k) 和 int indexFor(int h, int length) 来实现。

hash ：该方法主要是将Object转换成一个整型。
indexFor ：该方法主要是将hash生成的整型转换成链表数组中的下标。

为了聚焦本文的重点，只来看一下indexFor方法。先来看下Java 7（Java8中虽然没有这样一个单独的方法，但是查询下标的算法和Java 7一样的）中该实现细节：

static int indexFor(int h, int length) {

    return h & (length-1);

}
1
2
3
4
5

indexFor方法其实主要是将hashcode换成链表数组中的下标。其中的两个参数h表示元素的hashcode值，length表示HashMap的容量。那么return h & (length-1) 是什么意思呢？

其实，他就是取模。Java之所有使用位运算(&)来代替取模运算(%)，最主要的考虑就是效率。

位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

那么，为什么可以使用位运算(&)来实现取模运算(%)呢？这实现的原理如下：

X % 2^n = X & (2^n – 1)
1

假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。

此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。

从2进制角度来看，X / 8相当于 X >> 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。

上面的解释不知道你有没有看懂，没看懂的话其实也没关系，你只需要记住这个技巧就可以了。或者你可以找几个例子试一下。

6 % 8 = 6 ，6 & 7 = 6
10 & 8 = 2 ，10 & 7 = 2
1
2

运算过程如下：

所以，return h & (length-1);只要保证length的长度是2^n 的话，就可以实现取模运算了。

所以，因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高，所以HashMap在计算元素要存放在数组中的index的时候，使用位运算代替了取模运算。之所以可以做等价代替，前提是要求HashMap的容量一定要是2^n 。

那么，既然是2^n ，为啥一定要是16呢？为什么不能是4、8或者32呢？

关于这个默认容量的选择，JDK并没有给出官方解释，作者也没有在网上找到关于这个任何有价值的资料。

根据作者的推断，这应该就是个经验值（Experience Value），既然一定要设置一个默认的2^n 作为初始值，那么就需要在效率和内存使用上做一个权衡。这个值既不能太小，也不能太大。

太小了就有可能频繁发生扩容，影响效率。太大了又浪费空间，不划算。

所以，16就作为一个经验值被采用了。

在JDK 8中，关于默认容量的定义为：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// aka 16 ，其故意把16写成1<<4，就是提醒开发者，这个地方要是2的幂。值得玩味的是：注释中的 aka 16 也是1.8中新增的，

那么，接下来再来谈谈HashMap是如何保证其容量一定可以是2^n 的呢？如果用户自己设置了的话又会怎么样呢？

关于这部分，HashMap在两个可能改变其容量的地方都做了兼容处理，分别是指定容量初始化时以及扩容时。

指定容量初始化

通过HashMap(int initialCapacity)设置初始容量的时候，HashMap并不一定会直接采用我们传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。(1->1、3->4、7->8、9->16)

在JDK 1.7和JDK 1.8中，HashMap初始化这个容量的时机不同。JDK1.8中，在调用HashMap的构造函数定义HashMap的时候，就会进行容量的设定。而在JDK 1.7中，要等到第一次put操作时才进行这一操作。

看一下JDK是如何找到比传入的指定值大的第一个2的幂

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;
1
2
3
4
5
6
7

上面的算法目的其实就是：根据用户传入的容量值（代码中的cap），通过计算，得到第一个比他大的2的幂并返回。

请关注上面的几个例子中，蓝色字体部分的变化情况，或许你会发现些规律。5->8、9->16、19->32、37->64都是主要经过了两个阶段。

Step 1，5->7
Step 2，7->8
Step 1，9->15
Step 2，15->16
Step 1，19->31
Step 2，31->32
1
2
3
4
5
6

对应到以上代码中，Step1：

n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
1
2
3
4
5

对应到以上代码中，Step2：

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

Step 2 比较简单，就是做一下极限值的判断，然后把Step 1得到的数值+1。

Step 1 怎么理解呢？其实是对一个二进制数依次向右移位，然后与原值取或。其目的对于一个数字的二进制，从第一个不为0的位开始，把后面的所有位都设置成1。

随便拿一个二进制数，套一遍上面的公式就发现其目的了

1100 1100 1100 >>>1 = 0110 0110 0110
1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
1110 1110 1110 >>>2 = 0011 1011 1011
1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
1111 1111 1111 >>>4 = 1111 1111 1111
1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
1
2
3
4
5
6

通过几次无符号右移和按位或运算，我们把1100 1100 1100转换成了1111 1111 1111 ，再把1111 1111 1111加1，就得到了1 0000 0000 0000，这就是大于1100 1100 1100的第一个2的幂。

好了，现在解释清楚了Step 1和Step 2的代码。就是可以把一个数转化成第一个比他自身大的2的幂。

但是还有一种特殊情况套用以上公式不行，这些数字就是2的幂自身。如果数字4套用公式的话。得到的会是 8，不过其实这个问题也被解决了，具体验证办法及JDK的解决方案见Map中的hash()解析这里就不再赘述。

HashMap根据用户传入的初始化容量，利用无符号右移和按位或运算等方式计算出第一个大于该数的2的幂。

扩容

除了初始化的时候会指定HashMap的容量，在进行扩容的时候，其容量也可能会改变。

HashMap有扩容机制，就是当达到扩容条件时会进行扩容。HashMap的扩容条件就是当HashMap中的元素个数（size）超过临界值（threshold）时就会自动扩容。

在HashMap中，threshold = loadFactor * capacity。

loadFactor是装载因子，表示HashMap满的程度，默认值为0.75f，设置成0.75有一个好处，那就是0.75正好是3/4，而capacity又是2的幂。所以，两个数的乘积都是整数。

对于一个默认的HashMap来说，默认情况下，当其size大于12(16*0.75)时就会触发扩容。

下面是HashMap中的扩容方法(resize)中的一段

if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

                 oldCap >= DEFAULT_INITIAL_CAPACITY)

    newThr = oldThr << 1; // double threshold

}
1
2
3
4
5
6
7

从上面代码可以看出，扩容后的table大小变为原来的两倍，这一步执行之后，就会进行扩容后table的调整，这部分非本文重点，省略。

可见，当HashMap中的元素个数（size）超过临界值（threshold）时就会自动扩容，扩容成原容量的2倍，即从16扩容到32、64、128 …

所以，通过保证初始化容量均为2的幂，并且扩容时也是扩容到之前容量的2倍，所以，保证了HashMap的容量永远都是2的幂。

思考

根据上面的分析你应该知道了HashMap并不会直接接收用户传入的初始容量，那么为什么《Java开发手册》还是建议开发者在创建HashMap的时候制定一个初始容量呢？这个容量设置成多少合适呢？为什么？口空无凭，来点证据

为什么要设置 HashMap 的初始化容量

我们先来写一段代码在JDK1.7(jdk1.7.0_79)下面来分别测试下，在不指定初始化容量和指定初始化容量的情况下性能情况如何。（jdk 8 结果会有所不同，我会在后面的文章中分析）

public static void main (String[]args){
        int aHundredMillion = 10000000;
        Map<Integer, Integer> map = new HashMap<>(); long s1 = System.currentTimeMillis();
        for (int i = 0; i < aHundredMillion; i++) {
            map.put(i, i);
        }
        long s2 = System.currentTimeMillis();
        System.out.println("未初始化容量，耗时 ：" + (s2 - s1));
        
        Map<Integer, Integer> map1 = new HashMap<>(aHundredMillion / 2);
        long s5 = System.currentTimeMillis();
        for (int i = 0; i < aHundredMillion; i++) {
            map1.put(i, i);
        }
        long s6 = System.currentTimeMillis();
        System.out.println("初始化容量5000000，耗时 ：" + (s6 - s5));
        
        Map<Integer, Integer> map2 = new HashMap<>(aHundredMillion);
        long s3 = System.currentTimeMillis();
        for (int i = 0; i < aHundredMillion; i++) {
            map2.put(i, i);
        }
        long s4 = System.currentTimeMillis();
        System.out.println("初始化容量为10000000，耗时 ：" + (s4 - s3));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

输出结果：

未初始化容量，耗时 ：5437
初始化容量5000000，耗时 ：1661
初始化容量为10000000，耗时 ：1956
1
2
3

从结果中，我们可以知道，在已知 HashMap 中将要存放的 KV 个数的时候，设置一个合理的初始化容量可以有效的提高性能。

当然，以上结论也是有理论支撑的。刚才提到过HashMap 有扩容机制，就是当达到扩容条件时会进行扩容。HashMap 的扩容条件就是当 HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容。在 HashMap 中， threshold = loadFactor * capacity 。

所以，如果我们没有设置初始容量大小，随着元素的不断增加，HashMap 会发生多次扩容，而 HashMap 中的扩容机制决定了每次扩容都需要重建 hash 表，是非常影响性能的。

从上面的代码示例中，我们可以发现，同样是设置初始化容量，设置的数值不同也会影响性能，那么当我们已知 HashMap 中即将存放的 KV 个数的时候，容量设置成多少为好呢？

HashMap 中容量的初始化
默认情况下，当我们设置 HashMap 的初始化容量时，实际上 HashMap 会采用第一个大于该数值的 2 的幂作为初始化容量。

如下代码：

 Map<String, String> map = new HashMap<String, String>(1);
        map.put("hahaha", "hollischuang");
        Class<?> mapType = map.getClass();
        Method capacity = mapType.getDeclaredMethod("capacity");
        capacity.setAccessible(true);
        System.out.println("capacity : " + capacity.invoke(map));
1
2
3
4
5
6

在 jdk1.7 中，初始化容量设置成 1 的时候，输出结果是 2。在 jdk1.8 中，如果我们传入的初始化容量为 1，实际上设置的结果也为 1，上面代码输出结果为 2 的原因是代码中 map.put(“hahaha”, “hollischuang”)；导致了扩容，容量从 1 扩容到 2。

那么，话又说回来，当我们通过 HashMap(int initialCapacity)设置初始容量的时候，HashMap 并不一定会直接采用我们传入的数值，而是经过计算，得到一个新值，目的是提高 hash 的效率。(1->1、3->4、7->8、9->16)

在 Jdk 1.7 和 Jdk 1.8 中，HashMap 初始化这个容量的时机不同。jdk1.8 中，在调用 HashMap
的构造函数定义 HashMap 的时候，就会进行容量的设定。而在 Jdk 1.7 中，要等到第一次 put 操作时才进行这一操作。

不管是 Jdk 1.7 还是 Jdk 1.8，计算初始化容量的算法其实是如出一辙的，主要代码如下(摘抄自源码)：

int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
eturn (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
1
2
3
4
5
6
7

上面的代码挺有意思的，一个简单的容量初始化，Java 的工程师也有很多考虑在里面。

上面的算法目的挺简单，就是：根据用户传入的容量值（代码中的cap），通过计算，得到第一个比他大的 2 的幂并返回。

聪明的读者们，如果让你设计这个算法你准备如何计算？如果你想到二进制的话，那就很简单了。举几个例子看一下：

请关注上面的几个例子中，蓝色字体部分的变化情况，或许你会发现些规律。5->8、9->16、19->32、37->64 都是主要经过了两个阶段。

Step 1，5->7
Step 2，7->8
Step 1，9->15
Step 2，15->16
Step 1，19->31
Step 2，31->32
1
2
3
4
5
6

对应到以上代码中，Step1：

n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
1
2
3
4
5

对应到以上代码中，Step2：

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

Step 2 比较简单，就是做一下极限值的判断，然后把 Step 1 得到的数值 +1。

Step 1 怎么理解呢？其实是对一个二进制数依次向右移位，然后与原值取或。其目的对于一个数字的二进制，从第一个不为 0 的位开始，把后面的所有位都设置成 1。

随便拿一个二进制数，套一遍上面的公式就发现其目的了：

1100 1100 1100 >>>1 = 0110 0110 0110
1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
1110 1110 1110 >>>2 = 0011 1011 1011
1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
1111 1111 1111 >>>4 = 1111 1111 1111
1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
1
2
3
4
5
6

通过几次 无符号右移 和 按位或 运算，我们把 1100 1100 1100 转换成了1111 1111 1111 ，再把 1111 1111 1111 加 1，就得到了 1 0000 0000 0000，这就是大于 1100 1100 1100 的第一个 2 的幂。

好了，我们现在解释清楚了 Step 1 和 Step 2 的代码。就是可以把一个数转化成第一个比他自身大的 2 的幂。

但是还有一种特殊情况套用以上公式不行，这些数字就是 2 的幂自身。如果数字 4 套用公式的话。得到的会是 8 ：

Step 1: 0100 >>>1 = 0010 0100 | 0010 = 0110 0110 >>>1 = 0011 0110 | 0011 = 0111 
Step 2: 0111 + 0001 = 1000
1
2

为了解决这个问题，JDK 的工程师把所有用户传进来的数在进行计算之前先 -1，就是源码中的第一行：

int n = cap - 1;
1

至此，再来回过头看看这个设置初始容量的代码，目的是不是一目了然了：

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;
1
2
3
4
5
6
7

HashMap 中初始容量的合理值
当我们使用 HashMap(int initialCapacity) 来初始化容量的时候，jdk 会默认帮我们计算一个相对合理的值当做初始容量。那么，是不是我们只需要把已知的 HashMap 中即将存放的元素个数直接传给 initialCapacity 就可以了呢？

关于这个值的设置，在《Java 开发手册》有以下建议：

这个值，并不是阿里巴巴的工程师原创的，在 guava（21.0 版本）中也使用的是这个值(源码)。

public static <K, V > HashMap < K, V > newHashMapWithExpectedSize( int expectedSize){
            return new HashMap<K, V>(capacity(expectedSize));
        } /** * Returns a capacity that is sufficient to keep the map from being resized as long as it grows no * larger than expectedSize and the load factor is ≥ its default (0.75). */
        static int capacity ( int expectedSize){
            if (expectedSize < 3) {
                checkNonnegative(expectedSize, "expectedSize");
                return expectedSize + 1;
            }
            if (expectedSize < Ints.MAX_POWER_OF_TWO) { // This is the calculation used in JDK8 to resize when a putAll // happens; it seems to be the most conservative calculation we // can make. 0.75 is the default load factor. return (int) ((float) expectedSize / 0.75F + 1.0F); } return Integer.MAX_VALUE; // any large value }
            }
1
2
3
4
5
6
7
8
9
10

在 return (int) ((float) expectedSize / 0.75F + 1.0F); 上面有一行注释，说明了这个公式也不是 guava 原创，参考的是 JDK8 中 putAll 方法中的实现的。感兴趣的读者可以去看下 putAll 方法的实现，也是以上的这个公式。

虽然，当我们使用 HashMap(int initialCapacity) 来初始化容量的时候，jdk 会默认帮我们计算一个相对合理的值当做初始容量。但是这个值并没有参考 loadFactor 的值。

也就是说，如果我们设置的默认值是 7，经过 JDK 处理之后，会被设置成 8，但是，这个 HashMap 在元素个数达到 8*0.75 = 6 的时候就会进行一次扩容，这明显是我们不希望见到的。

如果我们通过 expectedSize / 0.75F + 1.0F计算，7/0.75 + 1 = 10 ,10 经过 JDK 处理之后，会被设置成 16，这就大大的减少了扩容的几率。

当 HashMap 内部维护的哈希表的容量达到 75% 时（默认情况下），会触发 rehash，而 rehash 的过程是比较耗费时间的。所以初始化容量要设置成 expectedSize/0.75 + 1 的话，可以有效的减少冲突也可以减小误差。

综合上述，我认为，当我们明确知道 HashMap 中元素的个数的时候，把默认容量设置成 expectedSize / 0.75F + 1.0F 是一个在性能上相对好的选择，但是，同时也会牺牲些内存。

小结
当我们想要在代码中创建一个 HashMap 的时候，如果我们已知这个 Map 中即将存放的元素个数，给 HashMap 设置初始容量可以在一定程度上提升效率。

但是，JDK 并不会直接拿用户传进来的数字当做默认容量，而是会进行一番运算，最终得到一个 2 的幂。原因在Map中的hash()解析介绍过，得到这个数字的算法其实是使用了使用无符号右移和按位或运算来提升效率。

但是，为了最大程度的避免扩容带来的性能消耗，建议可以把默认容量的数字设置成 expectedSize / 0.75F + 1.0F 。在日常开发中，可以使用

Map<String, String> map = Maps.newHashMapWithExpectedSize(10);
1

来创建一个 HashMap，计算的过程 guava 会帮我们完成。

但是，以上的操作是一种用内存换性能的做法，真正使用的时候，要考虑到内存的影响。

总结

HashMap作为一种数据结构，元素在put的过程中需要进行hash运算，目的是计算出该元素存放在hashMap中的具体位置。

hash运算的过程其实就是对目标元素的Key进行hashcode，再对Map的容量进行取模，而JDK 的工程师为了提升取模的效率，使用位运算代替了取模运算，这就要求Map的容量一定得是2的幂。

而作为默认容量，太大和太小都不合适，所以16就作为一个比较合适的经验值被采用了。

为了保证任何情况下Map的容量都是2的幂，HashMap在两个地方都做了限制。

首先是，如果用户制定了初始容量，那么HashMap会计算出比该数大的第一个2的幂作为初始容量。

另外，在扩容的时候，也是进行成倍的扩容，即4变成8，8变成16。