③.HashMap算法

• ①. HashMap是如何存数、找数、寻找下标的——此算法必须领悟并记住,这就是资本

1. 如果key为null,则默认对应的数组下标为0

2. key的hashCode值记为hashCode

3. 记h = hashCode ^ (hashCode >>> 16)

4. 记数组长度len也就是HashMap容量cap

5. index = h & (cap-1)

①. h = hashCode ^ (hashCode >>> 16)的理解

①. hashCode >>> 16:对hashCode值向右移16位,hashCode的值是一个32位的int,如果hashCode值比较小,那么高位就是0,相当于没有高位；如果hashCode的值比较大的话,高16就有数据

②. hashCode ^ (hashCode >>> 16):这个时候,hashCode与高16位进行^运算。高16位参与运算,可以大大提高离散的程度。

②. 为何不直接使用hashCode值来跟数组长度取模？

①. 如果直接使用hashCode和数组长度-1 进行运与运算,数组长度比较小的时候,这里我们使用数组长度为16。当hashCode很大的时候,高16位一直变动,而底16位处于不变的时候。因为数组长度16对应的后4位是1111。而我们hashCode低16位固定。固定的低16位和数组的后4位1111是一个固定的值,就是说元素储存的索引是固定的。元素都储存在同一个位置上,那产生的冲突将是非常恐怖的。意味着我们通过get( )去获取值,查询性能非常低,效率就也低

②. 所以,这个算法,在进行后面取模求index之前,先获取了一个更具有代表这个数据整体的数值h(h = hashCode ^ (hashCode >>> 16))。这样操作之后就将hashCode值的高低16位都运用了起来,这样h & (cap - 1)取模的离散算法就更优了,产生的冲突的几率更小,访问效率更高

③. 为什么index = h & (length-1) 要减去1？

①. 假如不减去1,length长度=16,这个时候和hashCode进行运与运算。16的后5位是10000,这个时候hashCode的后四位无论是什么结果都是4个0,而倒数第五位只有两个值,一个是0一个是1。如果是0那么对应储存的位置就是0；如果是1,对应储存的元素位置就是16。这个时候如果是0,那么所有的元素都储存在0位置,导致hash冲突,通过get()去查询元素时,效率极其低下。如果是1,对应储存的元素位置就是16,而索引最多只有15,所以会导致下标越界。

②. 如果index = h & (length-1) ,假如这个时候length=16,我们的后4位就是1111,这个时候hashCode的后四位无论怎么变化,h & (length-1) 运算的结果都是在[0-15]之间的。