1.      HashMap数组大小

无论是哪个版本的jdk，在扩容时数组大小必须是n=power(2,k)，初始大小为16，原因是效率：我们需要对一个对象的hash值判断其所在数组的下标时，直观上需要进行求余操作，而这里就可以简化为位运算hash & (n-1)，即求hash值的低位。

例如下面第一个数是某hashCode，而第二个数就是默认数组大小16-1.

http://s13/mw690/002i2qf8zy7ojxs0Ibicc&690

2.      hashCode方法的素数选择

官方native方法中，String对象的hashCode计算如下：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

这里选择了31作为基底，为什么呢？

正如1中所述，HashMap的数组大小是2的k次方，如果我们选择一个整数16作为基底，而此时Bucket数组的大小是16，那么此时哈希（求余）的结果就会很糟糕：

(x*16 + y) % 16 = (x*16) % 16 + y % 16 = 0 + y % 16 = y % 16

也就是说只有最不重要的低位决定了bucket的下标。所以基底的选择应当是素数，同时31又是一个特殊的素数，它是2的5次方减1，可以利用位运算得到，在计算hashCode时，31可以通过移位运算来提高计算效率：31 * i == (i << 5) – I 。

3.      扰动函数

在jdk1.8 HashMap在获取hash值时会作如下处理，而不是直接对bucket数量n求余找到对应的数组下标：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在jdk1.7的HashMap在获取hash值时的处理更为复杂：

static int hash(int h) {

    // This function ensures that hashCodes that differ only by

    // constant multiples at each bit position have a bounded

    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);

    return h ^ (h >>> 7) ^ (h >>> 4);

}

这种对hashCode的运算函数我们称为扰动函数。

虽然hashCode本身的int类型，数据范围在[-2^32, 2^32-1]内，但内存中不可能存在这么大的数组来表示Bucket，所以才会有1中的解释，默认数组大小仅为16。

         根据1中的解释，我们发现通过位运算hash & (n-1)的方式判断bucket下标，要是只取hashCode的最低几位（由数组大小n-1决定）的话，很容易出现碰撞，所以我们希望能够利用高位的信息避免哈希碰撞。这时扰动函数的价值就体现出来了，它可以结合高位和低位的信息。

http://s8/mw690/002i2qf8zy7ojxszcrl17&690

         右移16位正好获取int类型数字的高位，然后通过异或运算将高位信息传入最终的hash值的低位中，以此来加大低位的随机性。

         当然java8只通过一次扰动就认为可以了，虽然可能随机性比java7的4次要差，但谁让java8用了红黑树，不怕哈希碰撞了呢？

4.      关于数组大小的讨论

在上古版本中，HashTable的初始size是质数：11，通过模运算寻找数组下标，Since JDK 1.3, integer division and remainder calculation has become really slow，而移位运算速度比模运算快5倍以上；

HashMap的数组大小是2的次方，从而可以通过位运算来替代模运算提高效率，但这就对hash本身提出了要求，需要随机性更强的hashCode，通过扰动函数来增加随机性，从而解决非质数引起的分布不随机，这就可能从一定程度上抵消了位运算带来的高效，真是个trade off选择。

参考：

[1] https://www.zhihu.com/question/20733617

[2] /questions/3613102/why-use-a-prime-number-in-hashcode

[3] /questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier/299748#299748

[4] /questions/9413966/why-initialcapacity-of-hashtable-is-11-while-the-default-initial-capacity-in-has