以下代码叫做 “扰动函数”,理论上 hash 散列是一个 int 值,如果直接拿出来作为下标访问 hashmap 的话,考虑到二进制 32 位,取值范围在-2147483648 ~ 2147483647。大概有 40 亿个 key , 只要哈希函数映射比较均匀松散,一般很难出现碰撞。,一个客观的问题:要存下 40 亿长度的数组,服务器内存是不能放下的。通常咱们 HashMap 的默认长度为 16 。所以这个 hashCode , (key.hashCode ) 是不能直接来使用的。使用之前先做对数组长度的与运算,得到的值才能用来访问数组下标。,代码如下:,这里为什么要使用 n -1 ,来进行与运算,这里详单与是一个”低位掩码”, 以默认长度 16 为例子。和某个数进行与运算,结果的大小是 < 16 的。如下所示:,这个时候会有一个问题,如果本身的散列值分布松散,只要是取后面几位的话,碰撞也会非常严重。还有如果散列本身做得不好的话,分布上成等差数列的漏洞,可能出现最后几位出现规律性的重复。,这个时候“扰动函数”的价值就体现出来了。如下所示:,


文章版权声明
1 原创文章作者:cmcc,如若转载,请注明出处: https://www.52hwl.com/20775.html
2 温馨提示:软件侵权请联系469472785#qq.com(三天内删除相关链接)资源失效请留言反馈
3 下载提示:如遇蓝奏云无法访问,请修改lanzous(把s修改成x)
4 免责声明:本站为个人博客,所有软件信息均来自网络 修改版软件,加群广告提示为修改者自留,非本站信息,注意鉴别
微信扫一扫
支付宝扫一扫