最近在看八股之hashMap,分享一些自己对hash索引算法的理解,如果不对处请一定指出

index = HashCode（Key） & （Length - 1)

1.首先为要做按位与运算,按位或,按位异或不行吗?

因为只有在做按位与运算时得到的结果x = a & b,x<=min(a,b)才会小于等于数组的最小值(hash一般是一个很大的int型数),如果是按位或,按位异或得到的值可能会越界

2.为什么做按位与时用length-1,怎么不用length呢?
因为数组长度下标从0开始,做按位与运算最终得到的结果的 x = a & b,x<=min(a,b),
取到等于号时就会数组下标越界,所以要用数组长度-1,保证不会越界

3.为什么容量一定要是2的n次幂?
只有当length=2的n次幂的时候，length-1的二进制表达 全部为1（15的二进制1111，31的二进制位11111），
只有当length-1的全部位都1时，h & (length-1)的结果才能均匀散列在数组中,举个栗子
如果数组长度length不是2的整次幂,是1100101，那么length-1后,n=110100,可以发现在做按位与运算后 1,10,11,1000,1100,1110,1111...这些索引无论怎么样都不可能取到
造成空间浪费,而若是2的整次幂,减一以后,如11111111,那么每个索引处就都可能取到了

4.计算key的索引时index = HashCode（Key） & （Length - 1）为什么是做按位与运算?取模不行吗?
当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n
而且位运算比取模%运算效率高近27倍

5.4.为什么hash运算在原来的hash值基础上与hash值右移16为做按位或运算

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

首先,hashCode()方法得到的的是32位的整型数据,如a为hashCode()得到的值
可以看看下面的解释

int a =  11001110 11001111 11011101 00111110
 
a >>> 16 = 00000000 00000000 11001110 11001111
 
a ^ (a >>> 16)即为
 
11001110 11001111 11011101 00111110
00000000 00000000 11001110 11001111
=
11001110 11001111 00010011 11110001

• 在做按位与运算时,因为数组长度一般而言是小于2的16次方65535的,也就说数组长度的高16位一般全是0,
• 那么hash值的高位相当于全部没有作用,因为x&0=0,无论x是1还是0,这样hash冲突的几率会很大,为什么呢?
• 因为如果有很多hash值,它们的低16位相同,但高16都不相同,那么它们得到的索引值却是一样的,会产生冲突
• 在进行hash()方法之后,可以看出hash值的高16位是没有变化的,
• 而低16位和高16位做了异或运算,这样低16位的值同时拥有了高16位的特征,即使hash值的低16位一样，在做&运算时结果也就不一样,从而减少了冲突的可能

总结:hashMap的源码真的很长,有2000多行,后面还有线程安全问题,链表到红黑树的转换,扩容机制等一系列考点,以上只是我今天看源码,不懂的地方上各大博客上搜索后总结的一小部分,分享给大家啦,欢迎一起讨论~