首页 > 其他 > 详细

hashCode

时间:2019-03-16 10:27:28      阅读:65      评论:0      收藏:0      [点我收藏+]

标签:简单   个数   差异   包括   情况   哈希冲突   www   总结   ati   

1.背景

某天不经意间调用到String 的hashcode,随即点进去看下源码。发现里面是如下实现的

源码:

 
  1. public int hashCode() {
  2. int h = hash;
  3. if (h == 0 && value.length > 0) {
  4. char val[] = value;
  5. for (int i = 0; i < value.length; i++) {
  6. h = 31 * h + val[i];
  7. }
  8. hash = h;
  9. }
  10. return h;
  11. }

看到有个数字31引起我的注意,为什么要用数字31呢,不能是其他吗,这里面是有什么规则吗?于是就有了后续的问题与答案了。当然这里看的是string重写的hashCode方法,object对象的hashCode方法是本地方法native方法,该方法返回哈希码确定该对象在哈希表中的索引位置。

 

2.查找答案的历程

我先百度直接搜索问题,发现有很多类似一样的科普文章长篇解释了,但是每个点都没有详细说明。百度科普链接如下:https://www.cnblogs.com/nullllun/p/8350178.html

等我看完上面那篇文章后,我自己总结了几个答案:

 

1. 31是奇数,那为什么不能用偶数

首先因为偶数乘任何一个数,都是偶数,会造成偶数区域压力大,奇数区域基本为空,冲突比较大。其次因为偶数会导致乘法溢出,信息丢失。

2. 31是质数,那为什么不能用非质数呢

因为31质数,且只能被它本身和1整除。31是个不大不小的质数。而且还要选择与16,32,64,128相差一的质数,这样才能替换为移位与加减法。

3. 31可以被JVM优化

31*i = (i < <5)-i => i*(2^5-1) = i*2^5 - i,就这样被编译器优化为左移五位后减 i

当时说到这里的时候,我展开了说了下两个比较像的问题,分别如下:

 
  • 为什么hashmap容量建议是2的幂次方,当然是为了解决冲突,原因是这样的,hashmap有个方法indexFor 源码如下

 
  1. /**
  2. * 返回数组下标
  3. */
  4. static int indexFor(int h, int length) {
  5. return h & (length-1);
  6. }

因为 2? =》1和n个0,减一之后就是0和n个1,例如2? =》10000 ,而2?-1 = 01111,这样与运算都在低位,让低位都参与运算。这样会保证低位全为1,而扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)。还有,数组长度保持2的次幂,length-1的低位都为1,会使得获得的数组索引index更加均匀,上面的&运算,高位是不会对结果产生影响的(hash函数采用各种位运算可能也是为了使得低位更加散列),我们只关注低位bit,如果低位全部为1,那么对于h低位部分来说,任何一位的变化都会对结果产生影响,如果不是2的次幂,也就是低位不是全为1此时,h的低位部分不再具有唯一性了,哈希冲突的几率会变的更大,同时,index对应的这个bit位无论如何不会等于1了,而对应的那些数组位置也就被白白浪费了。

 
 
 
  • 为什么hashmap的hash()采用右移16位,然后异或(就是高16位异或低16位)

 

key的hash值高16位不变,低16位与高16位异或作为key的最终hash值。(h >>> 16,表示无符号右移16位,高位补0,任何数跟0异或都是其本身,因此key的hash值高16位不变。设计者考虑到现在的hashCode分布的已经很不错了,而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下,既减少了系统的开销,也不会造成的因为高位没有参与下标的计算(table长度比较小时),从而引起的碰撞。

 

技术分享图片

 

4. 31的哈希值正太分布均匀

按照前辈们实验得出的结论,31的哈希分布的确均匀。就如一开始给的链接那里有证明,考虑到大家可能不会去点击那个链接,所以我转载一部分出来,如下。

接下来,让我们对照上面的分区表,对数字2、3、17、31、101的散点曲线图进行简单的分析。先从数字2开始,数字2对于的散点曲线图如下:

 

技术分享图片

 
 
 

上面的图还是很一幕了然的,乘子2算出的哈希值几乎全部落在第32分区,也就是 [0, 67108864)数值区间内,落在其他区间内的哈希值数量几乎可以忽略不计。这也就不难解释为什么数字2作为乘子时,算出哈希值的冲突率如此之高的原因了。所以这样的哈希算法要它有何用啊,拖出去斩了吧。接下来看看数字3作为乘子时的表现:

 

技术分享图片

 
 
 

3作为乘子时,算出的哈希值分布情况和2很像,只不过稍微好了那么一点点。从图中可以看出绝大部分的哈希值最终都落在了第32分区里,哈希值的分布性很差。这个也没啥用,拖出去枪毙5分钟吧。在看看数字17的情况怎么样:

 

技术分享图片

 

数字17作为乘子时的表现,明显比上面两个数字好点了。虽然哈希值在第32分区和第34分区有一定的聚集,但是相比较上面2和3,情况明显好好了很多。除此之外,17作为乘子算出的哈希值在其他区也均有分布,且较为均匀,还算是一个不错的乘子吧。

 
 
 

技术分享图片

 

接下来来看看我们本文的主角31了,31作为乘子算出的哈希值在第33分区有一定的小聚集。不过相比于数字17,主角31的表现又好了一些。首先是哈希值的聚集程度没有17那么严重,其次哈希值在其他区分布的情况也要好于17。总之,选31,准没错啊。

 

技术分享图片

 

最后再来看看大质数101的表现,不难看出,质数101作为乘子时,算出的哈希值分布情况要好于主角31,有点喧宾夺主的意思。不过不可否认的是,质数101的作为乘子时,哈希值的分布性确实更加均匀。所以如果不在意质数101容易导致数据信息丢失问题,或许其是一个更好的选择。

 

当我看完上面全部内容后,我还是带着疑问去追寻那为什么不能是33,或者37,因为没有对33,37实验。

找到两个链接,有很多人给出了反对31的声音,大家有空可以看看。

https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier#

https://stackoverflow.com/questions/1835976/what-is-a-sensible-prime-for-hashcode-calculation#

包括php有个算法Time33哈希算法用的是33

 
  1. int Time33(String str) {
  2. int len = str.length();
  3. int hash = 0;
  4. for (int i = 0; i < len; i++)
  5. // (hash << 5) + hash 相当于 hash * 33
  6. hash = (hash << 5) + hash + (int) str.charAt(i);
  7. return hash;
  8. }

包括有些开源工具源码用的37

 

技术分享图片

 

所以最后个人得出结论是并不一定是要31,但是一定要符合上述4个标准即可

hashCode

标签:简单   个数   差异   包括   情况   哈希冲突   www   总结   ati   

原文:https://www.cnblogs.com/Javabc/p/10540456.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号