从数据结构谈HashMap的实现

预设HashMap的初始容量的情况，主要是你对所要存储的数据的数量可预知或者可预测的情况。

HashMap 包含如下几个构造器：

   HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。

   HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。

   HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。

因此，当你在构造HashMap时，如果预知存储数据的数量，可使用稍大于存储数量/loadFactor转成int后的值来设置初始容量。以避免数量过多时，造成不必要的多次扩容。

HashMap的实现中，是通过threshold字段来判断HashMap的最大容量：

threshold = (int)(capacity * loadFactor); 

if (size++ >= threshold)     
    resize(2 * table.length);

 当你的初始容量不是2的n次幂时，HaspMap会主动帮你进行优化，你不必要去保证自己构造时传入的初始容量一定为2的n次幂，只要大于存储数量/loadFactor即可。这样做的原因我在上面已经分析的很清楚了，当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。HashMap保证底层数组的大小总是2的n次幂的代码如下：

int capacity = 1;  
     while (capacity < initialCapacity)  
          capacity <<= 1;