HashMap的构造函数，hash, tableSizeFor的源码分析
一，静态默认参数
//默认的初始容量16,且实际容量是2的整数幂，0000 0001 =>向左移动4位 => 0001 0000
staticfinalintDEFAULT_INITIAL_CAPACITY =1<<4;
//最大容量(传入容量过大将被这个值替换)
//00000000 0000000 00000000 00000001 =>向左移动30位 => 01000000 00000000 00000000 00000000
staticfinalintMAXIMUM_CAPACITY =1<<30;
// 默认加载因子为0.75(当表达到3/4满时,才会再散列),这个因子在时间和空间代价之间达到了平衡.更高的因子可以降低表所需的空间,但是会增加查找代价,而查找是最频繁操作
staticfinalfloatDEFAULT_LOAD_FACTOR =0.75f;
//桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 >= 8时，则将链表转换成红黑树
staticfinalintTREEIFY_THRESHOLD =8;
// 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 <= 6时，则将 红黑树转换成链表
//最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
staticfinalintUNTREEIFY_THRESHOLD =6;
二，构造函数
1. 无参构造函数
2. 传入初始容量，调用this
初始化capacity和扩容的阈值
tableSizeFor()的主要功能是返回一个比给定整数大且最接近的2的幂次方整数，如给定16，返回2的4次方16.
逐行分析
int n = cap - 1
给定的cap 减 1,为了避免参数cap本来就是2的幂次方,这样一来,经过后续操作，cap将会变成2 * cap,是不符合我们预期的n |= n >>> 1
n >>> 1 : n无符号右移1位,即n二进制最高位的1右移一位
n | (n >>> 1) 导致 n二进制的高2位值为1
目前n的高1~2位均为1n |= n >>> 2
n继续无符号右移2位
n | (n >>> 2) 导致n二进制表示的高34位经过运算值均为1
目前n的高14位均为1n |= n >>> 4
n继续无符号右移4位
n | (n >>> 4) 导致n二进制表示的高58位经过运算值均为1
目前n的高18位均为1n |= n >>> 8
n继续无符号右移8位
n | (n >>> 8) 导致n二进制表示的高916位经过运算值均为1
目前n的高116位均为1可以看出,无论给定cap(cap < MAXIMUM_CAPACITY )的值是多少,经过以上运算,其值的二进制所有位都会是1.再将其加1,这时候这个值一定是2的幂次方.
当然如果经过运算值大于MAXIMUM_CAPACITY,直接选用MAXIMUM_CAPACITY.
所以最终tableSizeFor(20)的结果是 32（2的5次方）
三，hash算法
在Java8中,HashMap中key的Hash值由Hash(key)方法计得，HashMap中存储数据table的index是由key的Hash值决定的. 在HashMap存储数据时,我们期望数据能均匀分布,以防止哈希冲突.
为什么cap要保持为2的幂次方？
自然而然我们就会想到去用%取余操作来实现我们这一构想
取余(%)操作 : 如果除数是2的幂次则等价于与其除数减一的与(&)操作.
这也就解释了为什么一定要求cap要为2的幂次方.再来看看table的index的计算规则：
等价于:
|
1 |
|
采用二进制位操作&,相对于%,能够提高运算效率,这就是cap的值被要求为2幂次的原因。
（数组长度-1）正好相当于一个“低位掩码”
“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问
以初始长度16为例，16-1=15
2进制表示是00000000 00000000 00001111
和某散列值做“与”操作如下，结果就是截取了最低的四位值
但这时候问题就来了,这样就算我的散列值分布再松散,要是只取最后几位的话,碰撞也会很严重
这时候“扰动函数”的价值就体现出来了
右位移16位，正好是32位一半，自己的高半区和低半区做异或，就是为了混合原始hashCode的高位和低位，以此来加大低位的随机性
而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
index的运算规则是
|
1 |
|
newCap是2的幂,所以newCap - 1的高位全0
若e.hash值只用自身的hashcode,index只会和e.hash的低位做&操作.这样一来,index的值就只有低位参与运算,高位毫无存在感,从而会带来哈希冲突的风险
所以在计算key的hashCode时,用其自身hashCode与其低16位做异或操作
这也就让高位参与到index的计算中来了,即降低了哈希冲突的风险又不会带来太大的性能问题
参考自：