本文已同步至GitHub。有GitHub账号的朋友,看完记得给二哥安排一波star哦!麻烦大家刷一波GitHub的热搜榜。github地址:https://github.com/itwanger/toBeBetterJavaer在线阅读地址:https://itwanger.gitee.io/tobebetterjavaer看看hash方法的源码(JDK8中的HashMap):staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}这段代码是做什么用的?我们都知道key.hashCode()是用来获取key的hash值的。理论上hash值是int类型,取值范围为-2147483648到2147483648,总映射空间约40亿。只要哈希值均匀松散的映射,一般不会出现哈希冲突。但是问题是一个长度为40亿的数组内存是放不下的。HashMap展开前的数组初始大小只有16,所以这个hash值不能直接使用。需要用它对之前的数组长度进行取模运算,用得到的余数访问数组下标。模运算有两个地方。模运算(“ModuloOperation”)和余数运算(“RemainderOperation”)这两个概念有重叠但并不完全一致。主要区别在于除负整数时的运算不同。模数主要用于计算机术语,而余数更多是一个数学概念。一种是在放入HashMap时(在putVal方法中):intn,i;if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);}一个是从HashMap获取时(在getNode方法中):finalNodegetNode(inthash,Objectkey){Node[]tab;Nodefirst,e;intn;Kk;if((tab=table)!=null&&(n=tab.length)>0&&(first=tab[(n-1)&hash])!=null){}}其中(n-1)&hash只是取模运算,也就是在hash值和(arraylength-1)之间做一个“与”运算.你可能会疑惑:%不应该用于取模运算吗?为什么要用&?这是因为&运算比%效率更高,而当b为2的n次方时,有如下公式a%b=a&(b-1)replacebwith:验证一下,如果a=14,b=8,即n=3,这也正好解释了为什么HashMap的数组长度应该是2的整数次方.因为(arraylength-1)正好等同于一个“低位掩码”——这个掩码的低位最好全为1,这样&操作就是有意义,否则结果一定为0,则&运算无意义。a&b运算的结果为:如果a和b中对应的位同时为1,则对应的结果位为1,否则02的整数次方正好是偶数,偶数-1是一个奇数,奇数的二进制最后一位为1,保证hash的最后一位&(length-1)可能为0也可能为1(取决于h的值),即&运算后的结果可以是偶数也可以是奇数,这样可以保证哈希值的一致性。&操作的结果是将hash值的高位全部清零,只保留低位供数组下标访问。假设某个hash值为101001011100010000100101,用它来取模,我们来看看结果。HashMap初始长度为16(内部数组),16-1=15,二进制为000000000000000000001111(高位补0):101001011100010000100101&000000000000000000001111---------------------------------00000000000000000000000101因为15的高位全为0,&运算后高位的结果一定为0,只剩下4个低位0101,即十进制为5,即把hash值为101001011100010000100101的key放在数组的第5位。了解了取模运算之后,我们再来看put方法的源码:publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}和get方法的源码:publicVget(Objectkey){HashMap.Nodee;return(e=getNode(hash(key),key))==null?null:e.value;}它们会在调用putVal和getNode之前调用hash方法:staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}那为什么要在取模之前调用hash方法呢?看下面的图片。某hash值为11111111111111111111000011101010,右移16位(h>>>16),正好是00000000000000001111111111111111,再进行异或运算(h^(h>>>16)),结果是11111111111111110000111100010101XOR(^)运算是一种基于二进制的位运算,用符号XOR或^表示。运算规则是:如果相同的值为0,不同的值为1,因为原哈希值的高位和低位混合,所以增加了低位的随机性(一些高位特征混合,并且高位信息也被保留)。然后对数组长度-1(00000000000000000000000000001111)取模,得到下标为00000000000000000000000000000101,即5。还记得之前假设的哈希值1010010111000100001we1001吗?在调用hash方法之前,与15取模的结果也是5,我们来看看调用hash之后的取模结果。某hash值为00000000101001011100010000100101(32位补齐),右移16位(h>>>16),正好是00000000000000000000000010100101,再进行异或运算(h^(h>>>16)),结果为00000000101001010011101110000000将结果与数组长度-1(00000000000000000000000000001111)进行取模运算,得到下标为00000000,00000000,00000000综上所述,hash方法就是用来优化hash值的。将哈希值右移16位,刚好是自身长度的一半,然后与原哈希值进行异或运算,这样混合了原哈希值中的高位和低位,增加了随机性。hash方法说白了就是增加随机性,让数据元素的分布更加均衡,减少碰撞。参考链接:https://blog.csdn.net/lonyw/article/details/80519652>https://zhuanlan.zhihu.com/p/91636401>https://www.zhihu.com/question/20733617