HashMap的构造函数，hash,tableSizeFor的源码分析

一，静态默认参数

//默认的初始容量16,且实际容量是2的整数幂，0000 0001 =>向左移动4位 => 0001 0000

static final int DEFAULT_INITIAL_CAPACITY = 1 <<4;

//最大容量(传入容量过大将被这个值替换) 

//00000000 0000000 00000000 00000001 =>向左移动30位 => 01000000 00000000 00000000 00000000

static final int MAXIMUM_CAPACITY = 1 <<30;

// 默认加载因子为0.75(当表达到3/4满时,才会再散列),这个因子在时间和空间代价之间达到了平衡.更高的因子可以降低表所需的空间,但是会增加查找代价,而查找是最频繁操作

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 >= 8时，则将链表转换成红黑树

static final int TREEIFY_THRESHOLD = 8;

// 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 <= 6时，则将 红黑树转换成链表

//最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）

static final int UNTREEIFY_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位均为1

  
  



• n |= n >>> 2
  
  n继续无符号右移2位
  
  n | (n >>> 2) 导致n二进制表示的高34位经过运算值均为1
  
  目前n的高14位均为1

  
  



• n |= n >>> 4
  
  n继续无符号右移4位
  
  n | (n >>> 4) 导致n二进制表示的高58位经过运算值均为1
  
  目前n的高18位均为1

  
  



• n |= n >>> 8
  
  n继续无符号右移8位
  
  n | (n >>> 8) 导致n二进制表示的高916位经过运算值均为1
  
  目前n的高116位均为1

  
  

可以看出,无论给定cap(cap
当然如果经过运算值大于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的计算规则：

等价于:

采用二进制位操作&,相对于%,能够提高运算效率,这就是cap的值被要求为2幂次的原因。

（数组长度-1）正好相当于一个“低位掩码”

“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问

以初始长度16为例，16-1=15

2进制表示是00000000 00000000 00001111

和某散列值做“与”操作如下，结果就是截取了最低的四位值

但这时候问题就来了,这样就算我的散列值分布再松散,要是只取最后几位的话,碰撞也会很严重

这时候“扰动函数”的价值就体现出来了

右位移16位，正好是32位一半，自己的高半区和低半区做异或，就是为了混合原始hashCode的高位和低位，以此来加大低位的随机性

而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

index的运算规则是

newCap是2的幂,所以newCap - 1的高位全0

若e.hash值只用自身的hashcode,index只会和e.hash的低位做&操作.这样一来,index的值就只有低位参与运算,高位毫无存在感,从而会带来哈希冲突的风险

所以在计算key的hashCode时,用其自身hashCode与其低16位做异或操作

这也就让高位参与到index的计算中来了,即降低了哈希冲突的风险又不会带来太大的性能问题

参考自：

https://www.nowcoder.com/discuss/151172

https://www.jianshu.com/p/ee0de4c99f87