# 为什么建议初始化 HashMap 的容量大小？
在《[HashMap中傻傻分不清楚的那些概念](http://www.javashuo.com/link?url=http://www.hollischuang.com/archives/2416)》文章中，咱们介绍了HashMap中和容量相关的几个概念，简单介绍了一下HashMap的扩容机制。html
文中咱们提到，默认状况下HashMap的容量是16，可是，若是用户经过构造函数指定了一个数字做为容量，那么Hash会选择**大于该数字的第一个2的幂**做为容量。(3->四、7->八、9->16)程序员
本文，延续上一篇文章，咱们再来深刻学习下，到底应不该该设置HashMap的默认容量？若是真的要设置HashMap的初始容量，咱们应该设置多少？算法
### 为何要设置HashMap的初始化容量
咱们以前提到过，《阿里巴巴Java开发手册》中建议咱们设置HashMap的初始化容量。app
函数
那么，为何要这么建议？你有想过没有。性能
咱们先来写一段代码在JDK 1.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));
}
~~~
以上代码不难理解，咱们建立了3个HashMap，分别使用默认的容量（16）、使用元素个数的一半（5千万）做为初始容量、使用元素个数（一亿）做为初始容量进行初始化。而后分别向其中put一亿个KV。测试
输出结果：字体
~~~
未初始化容量，耗时 ： 14419
初始化容量5000000，耗时 ： 11916
初始化容量为10000000，耗时 ： 7984
~~~
**从结果中，咱们能够知道，在已知HashMap中将要存放的KV个数的时候，设置一个合理的初始化容量能够有效的提升性能。**spa
固然，以上结论也是有理论支撑的。咱们[上一篇](http://www.javashuo.com/link?url=http://www.hollischuang.com/archives/2416)文章介绍过，HashMap有扩容机制，就是当达到扩容条件时会进行扩容。HashMap的扩容条件就是当HashMap中的元素个数（size）超过临界值（threshold）时就会自动扩容。在HashMap中，`threshold = loadFactor * capacity`。
因此，若是咱们没有设置初始容量大小，随着元素的不断增长，HashMap会发生屡次扩容，而HashMap中的扩容机制决定了每次扩容都须要重建hash表，是很是影响性能的。（关于resize，后面我会有文章单独介绍）
从上面的代码示例中，咱们还发现，一样是设置初始化容量，设置的数值不一样也会影响性能，那么当咱们已知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。在jdk1.8中，若是咱们传入的初始化容量为1，实际上设置的结果也为1，上面代码输出结果为2的缘由是代码中map.put("hahaha", "hollischuang");致使了扩容，容量从1扩容到2。
那么，话题再说回来，当咱们经过HashMap(int initialCapacity)设置初始容量的时候，HashMap并不必定会直接采用咱们传入的数值，而是通过计算，获得一个新值，目的是提升hash的效率。(1->一、3->四、7->八、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;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
~~~
上面的代码挺有意思的，一个简单的容量初始化，Java的工程师也有不少考虑在里面。
上面的算法目的挺简单，就是：根据用户传入的容量值（代码中的cap），经过计算，获得第一个比他大的2的幂并返回。
聪明的读者们，若是让你设计这个算法你准备如何计算？若是你想到二进制的话，那就很简单了。举几个例子看一下：
请关注上面的几个例子中，蓝色字体部分的变化状况，或许你会发现些规律。5->八、9->1六、19->3二、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
对应到以上代码中，Step1：
~~~
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
~~~
对应到以上代码中，Step2：
~~~
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 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
~~~
经过几回`无符号右移`和`按位或`运算，咱们把1100 1100 1100转换成了1111 1111 1111 ，再把1111 1111 1111加1，就获得了1 0000 0000 0000，这就是大于1100 1100 1100的第一个2的幂。
好了，咱们如今解释清楚了Step 1和Step 2的代码。就是能够把一个数转化成第一个比他自身大的2的幂。（能够开始佩服Java的工程师们了，使用`无符号右移`和`按位或`运算大大提高了效率。）
可是还有一种特殊状况套用以上公式不行，这些数字就是2的幂自身。若是数字4 套用公式的话。获得的会是 8 ：
~~~
Step 1:
0100 >>>1 = 0010
0100 | 0010 = 0110
0110 >>>1 = 0011
0110 | 0011 = 0111
Step 2:
0111 + 0001 = 1000
~~~
为了解决这个问题，JDK的工程师把全部用户传进来的数在进行计算以前先-1，就是源码中的第一行：
~~~
int n = cap - 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;
~~~
### 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
}
~~~
在`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()分析的最透彻的文章，别无二家。](http://www.javashuo.com/link?url=http://www.hollischuang.com/archives/2091)）介绍过，获得这个数字的算法实际上是使用了使用无符号右移和按位或运算来提高效率。
- java开发手册
- 嵩山版手册
- 为什么禁止使用 Apache Beanutils 进行属性的 copy ？
- 为什么阿里巴巴要求日期格式化时必须有使用y表示年，而不能用Y？
- 《Java 开发手册 - 泰山版》提到的三目运算符 的空指针问题到底是个怎么回事？
- 为什么建议初始化 HashMap 的容量大小？
- Java 开发手册建议创建 HashMap 时设置初始 化容量，但是多少合适呢？
- 为什么禁止使用 Executors 创建线程池？
- 为什么要求谨慎使用 ArrayList 中的 subList 方法？
- 为什么不建议在 for 循环中使用“+”进行字符 串拼接？
- 为什么禁止在 foreach 循环里进行元素的 remove/add 操作？
- 为什么禁止工程师直接使用日志系统 (Log4j、 Logback) 中的 API ？
- 为什么禁止把 SimpleDateFormat 定义成 static 变量？
- 为什么禁止开发人员使用 isSuccess 作为变量名？
- 为什么禁止开发人员修改 serialVersionUID 字段的值？
- 为什么建议开发者谨慎使用继承？
- 为什么禁止使用 count( 列名 ) 或 count( 常量 ) 来替代 count(*) ？