关于HashMap的详解文章请移步：
链接: HashMap源码研究——源码一行一行的注释
文章目录
- 为什么初始容量是 2次幂？
- 如果指定了不是2的次幂的容量会发生什么？
- 有一个初始容量参数的构造方法HashMap(int initialCapacity)
- 有两个参数的构造方法HashMap(int initialCapacity, float loadFactor)
- 扰动函数
为什么初始容量是 2次幂？
代码语言：javascript复制final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果没有hash碰撞则直接插入元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
......
}
}通过看源码，我们发现，判断桶的索引的实现是 i = ( n - 1 ) & hash，其中 n 是 map 的容量。
任何 2 的整数幂 - 1 得到的二进制都是 1，如：16 - 1 = 15（1111）；32 - 1 = 31（11111）
而 n-1 与 hash 做的是与运算(&)，与运算是 两个都为1，才为1
既然我们的 n-1 永远都是 1，那 ( n - 1 ) & hash 的计算结果就是 低位的hash 值。如：
代码语言：javascript复制 00100100 10100101 11000100 00100101 // Hash 值
& 00000000 00000000 00000000 00001111 // 16 - 1 = 15
----------------------------------
00000000 00000000 00000000 00000101 // 高位全部归零，只保留末四位。那容量不是 2次幂会怎么样？我们来做个试验。
2次幂的情况：
非2次幂的情况，假设 n = 10:
对比来看，哪种发生哈希碰撞的概率更低一目了然，如果 n 为 2次幂，可以保证数据的均匀插入，降低哈希冲突的概率，毕竟冲突越大，代表数组中的链表/红黑树越大，从而降低Hashmap 的性能。
如果指定了不是2的次幂的容量会发生什么？
答案：会获得最接近的一个2的次幂作为容量
有一个初始容量参数的构造方法HashMap(int initialCapacity)
参数：initialCapacity 初始容量
public HashMap(int initialCapacity) {
//此处通过把第二个参数负载因子使用默认值0.75f，然后调用有两个参数的构造方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}这个一个参数的构造方法，使用HashMap的默认负载因子，把该初始容量和默认负载因子作为入参，调用HashMap的两个参数的构造方法
有两个参数的构造方法HashMap(int initialCapacity, float loadFactor)
参数：initialCapacity 初始容量
参数：loadFactor 负载因子
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
* 通过指定的初始容量和负载因子初始化一个空的HashMap
*
* @param initialCapacity the initial capacity 初始化容量
* @param loadFactor the load factor 负载因子
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
* 如果初始容量或者负载因子为负数，则会抛出非法数据异常
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) //如果初始容量小于0，抛出异常
throw new IllegalArgumentException("Illegal initial capacity: "
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) //如果初始容量超过最大容量（1<<32）
initialCapacity = MAXIMUM_CAPACITY; //则使用最大容量作为初始容量
if (loadFactor <= 0 || Float.isNaN(loadFactor)) //如果负载因子小于等于0或者不是数字，则抛出异常
throw new IllegalArgumentException("Illegal load factor: "
loadFactor);
this.loadFactor = loadFactor; //把负载因子赋值给成员变量loadFactor
//调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果，并赋给成员变量threshold
this.threshold = tableSizeFor(initialCapacity);
}我们下面看看tableSizeFor()这个方法是如何计算的，这个方法的实现原理很巧妙，源码如下：
代码语言：javascript复制/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1; //容量减1，为了防止初始化容量已经是2的幂的情况，最后有 1运算。
n |= n >>> 1; //将n无符号右移一位再与n做或操作
n |= n >>> 2; //将n无符号右移两位再与n做或操作
n |= n >>> 4; //将n无符号右移四位再与n做或操作
n |= n >>> 8; //将n无符号右移八位再与n做或操作
n |= n >>> 16; //将n无符号右移十六位再与n做或操作
//如果入参cap为小于或等于0的数，那么经过cap-1之后n为负数，n经过无符号右移和或操作后仍未负
//数,所以如果n<0,则返回1;如果n大于或等于最大容量，则返回最大容量;否则返回n 1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}首先，为什么要对cap做减1操作。int n = cap - 1; 这是为了防止，cap已经是2的幂。如果cap已经是2的幂， 又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。如果不懂，要看完后面的几个无符号右移之后再回来看看。 下面看看这几个无符号右移操作： 如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是1（最后有个n 1的操作）。 这里只讨论n不等于0的情况。 第一次右移
n |= n >> 1;
由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如000011xxxxxx。 第二次右移
n |= n >>> 2;
注意，这个n已经经过了n |= n >>> 1; 操作。假设此时n为000011xxxxxx ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如00001111xxxxxx 。 第三次右移
n |= n >>> 4;
这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中会有8个连续的1。如00001111 1111xxxxxx 。 以此类推 注意，容量最大也就是32bit的正数，因此最后n |= n >>> 16; ，最多也就32个1，但是这时已经大于了MAXIMUM_CAPACITY ，所以取值到MAXIMUM_CAPACITY 。
但是，请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。
扰动函数
HashMap 中的扰动函数是一个通过对 key 值类型自带的哈希函数生成的散列值进行位移计算来扰乱散列值，以达到降低哈希碰撞的概率的方法。源码中对应的是 hash()，但具体是如何进行移位和降低碰撞概率的？？
代码语言：javascript复制// jdk 8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}我们分析一下hash()，key.hash() 调用的是key类型自带的哈希函数，返回的是 int 类型的散列值。
如果没有扰动函数的情况下，我们拿着散列值作为下标找到 hashmap 中对应的桶位存下即可（不发送哈希冲突的情况下），但 int 类型是 32 位，很少有Hashmap的数组有40亿这么大，所以， key 类型自带的哈希函数返回的散列值不能拿来直接用。如果我们取低几位的 hash 值来做数组映射行不行，但是如果低位相同，高位不同的 hash 值就碰撞了，如：
代码语言：javascript复制// Hash 碰撞示例：
00000000 00000000 00000000 00000101 & 1111 = 0101 // H1
00000000 11111111 00000000 00000101 & 1111 = 0101 // H2为了解决这个问题，HashMap 想了个办法，用扰动函数降低碰撞的概率。将 hash 值右移16位（hash值的高16位）与 原 hash 值做异或运算（^），从而得到一个新的散列值。如：
代码语言：javascript复制00000000 00000000 00000000 00000101 // H1
00000000 00000000 00000000 00000000 // H1 >>> 16
00000000 00000000 00000000 00000101 // hash = H1 ^ (H1 >>> 16) = 5
00000000 11111111 00000000 00000101 // H2
00000000 00000000 00000000 11111111 // H2 >>> 16
00000000 00000000 00000000 11111010 // hash = H2 ^ (H2 >>> 16) = 250H1,H2 两个 hash 值经过扰动后，很明显不会发生碰撞。
总结 总的来说，不管是规定 Hashmap 的 n 为 2次幂，还是扰动函数，都是为了一个目标，降低哈希冲突的概率，从而使 HashMap 性能得到优化。而规定 n 为 2次幂，是在新建 Hashmap对象初始化时，规定其容量大小的角度来优化。而扰动函数是插入 key 值时改变 key 的散列值来达到优化效果。
