为什么要先高16位异或低16位再取模运算 - 起点终站

我们应该感谢相遇,无论结局是喜是悲....
为什么要先高16位异或低16位再取模运算
  • 首页 > IT技术
  • 作者:起点终站
  • 2020年12月3日 19:31 星期四
  • 浏览:16632
  • 字号:
  • 评论:7
  • 我们知道,n代表的是table的长度length,之前一再强调,表table的长度需要取2的整数次幂,就是为了这里等价这里进行取模运算时的方便——取模运算转化成位运算公式:a%(2^n) 等价于 a&(2^n-1),而&操作比%操作具有更高的效率。
    当length=2n时,(length - 1)正好相当于一个"低位掩码","与"操作的结果就是散列值的高位全部归零,只保留低位,用来做数组下标访问:

    可以看到,当我们的length为16的时候,哈希码(字符串“abcabcabcabcabc”的key对应的哈希码)对(16-1)与操作,对于多个key生成的hashCode,只要哈希码的后4位为0,不论不论高位怎么变化,最终的结果均为0。也就是说,如果支取后四位(低位)的话,这个时候产生"碰撞"的几率就非常大(当然&运算中产生碰撞的原因很多,这里只是举个例子)。为了解决低位与操作碰撞的问题,于是便有了第二步中高16位异或低16位的“扰动函数”。
    右移16位,自己的高半区和低半区异或,就是为了混合原始哈希码的高位和低位,以此来加大低位随机性。

    可以看到: 扰动函数优化前:1954974080 % 16 = 1954974080 & (16 - 1) = 0 扰动函数优化后:1955003654 % 16 = 1955003654 & (16 - 1) = 6 很显然,减少了碰撞的几率。

      您阅读这篇文章共花了:  
    本文作者:起点终站      文章标题: 为什么要先高16位异或低16位再取模运算
    本文地址:https://blog.hellozwh.com/?post=445
    版权声明:若无注明,本文皆为“起点终站”原创,转载请保留文章出处。
    • blogger
    海安人才网2021-11-19 15:20
    什么样的脑回路能看懂
    海阔天空2021-06-18 21:48
    是这样吗
    海阔天空2021-06-18 21:48
    是这样吗
    头条2021-04-21 14:48
    文章不错交个朋友
    今日热搜2021-03-21 20:22
    文章不错支持一下
    跨境电商卖家2021-04-09 15:58
    @今日热搜:这个不错顶一下
    今日新鲜事2021-02-25 00:02
    文章不错非常喜欢
    返回顶部| 首页| 手气不错| 网站地图| sitemap| 装逼生成器| 站长介绍|

    Copyright © 2016-2019 起点终站 闽ICP备16011094号-1