首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  Java

HashMap 中的扰动函数有没有必要

  •  
  •   jie170601 · 137 天前 · 1421 次点击
    这是一个创建于 137 天前的主题,其中的信息可能已经有所发展或是发生改变。

    无意中看到 HashMap 的源码,
    有个函数理解不了用途,
    搜索引擎搜索了一下,
    发现叫扰动函数:

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

    代码比较好看懂,
    就是把高 16 位的信息加到低 16 位上来,
    但是这样真的能降低 hash 的碰撞率吗?
    按理说把[-2147483648,2147483647]缩到了[0,15],
    假如数据分布均匀,
    碰撞率应该是一定的呀?

    7 回复  |  直到 2019-07-26 11:30:45 +08:00
        1
    morethansean   137 天前
    你不是说你看了源码? index 是 hash 值和长度做与操作出来的啊...长度一般比较小基本就是低位掩码了,所以把高位信息混进来鸭。
        2
    x7395759   137 天前
    你两种都跑一下不就知道了
        3
    qwerthhusn   137 天前
    当然了,当桶数为 16 的时候,
    决定落到那个桶是由初始 hash 值的最后 4 位决定的
    扰一下,决定落到哪个桶是由初始 hash 值的最后 4 位和第 13-16 位总共 8 位决定的
        4
    qwerthhusn   137 天前   ♥ 1
    虽然,全集合[-2147483648,2147483647]缩到了[0,15]是均匀的。
    但是随机少量数据,通过 4 位和通过 8 位的分散概率肯定不一样。
        5
    jie170601   136 天前 via Android
    @qwerthhusn 是的随机少量的影响还是挺大的,可能数学专业惯性思维了,概率算的整个区间的🙃
        6
    jie170601   136 天前 via Android
    @x7395759 有人跑过了说能减少 10%的碰撞,但是这个和用的啥样本数据关系很大,不是很值得参考
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1008 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 27ms · UTC 22:48 · PVG 06:48 · LAX 14:48 · JFK 17:48
    ♥ Do have faith in what you're doing.