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

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

  •  
  •   jie170601 · 2019-07-25 16:36:36 +08:00 · 4118 次点击
    这是一个创建于 1709 天前的主题,其中的信息可能已经有所发展或是发生改变。

    无意中看到 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
    morethansean
        1
    morethansean  
       2019-07-25 16:54:30 +08:00
    你不是说你看了源码? index 是 hash 值和长度做与操作出来的啊...长度一般比较小基本就是低位掩码了,所以把高位信息混进来鸭。
    x7395759
        2
    x7395759  
       2019-07-25 17:30:24 +08:00
    你两种都跑一下不就知道了
    qwerthhusn
        3
    qwerthhusn  
       2019-07-25 17:35:16 +08:00
    当然了,当桶数为 16 的时候,
    决定落到那个桶是由初始 hash 值的最后 4 位决定的
    扰一下,决定落到哪个桶是由初始 hash 值的最后 4 位和第 13-16 位总共 8 位决定的
    qwerthhusn
        4
    qwerthhusn  
       2019-07-25 17:38:20 +08:00   ❤️ 1
    虽然,全集合[-2147483648,2147483647]缩到了[0,15]是均匀的。
    但是随机少量数据,通过 4 位和通过 8 位的分散概率肯定不一样。
    jie170601
        5
    jie170601  
    OP
       2019-07-26 07:51:14 +08:00 via Android
    @qwerthhusn 是的随机少量的影响还是挺大的,可能数学专业惯性思维了,概率算的整个区间的🙃
    jie170601
        6
    jie170601  
    OP
       2019-07-26 07:52:55 +08:00 via Android
    @x7395759 有人跑过了说能减少 10%的碰撞,但是这个和用的啥样本数据关系很大,不是很值得参考
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2803 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 14:46 · PVG 22:46 · LAX 07:46 · JFK 10:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.