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

[jie170601]

无意中看到 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]，
假如数据分布均匀，
碰撞率应该是一定的呀？

[morethansean]

你不是说你看了源码？ index 是 hash 值和长度做与操作出来的啊...长度一般比较小基本就是低位掩码了，所以把高位信息混进来鸭。

[x7395759]

你两种都跑一下不就知道了

[qwerthhusn]

当然了，当桶数为 16 的时候，
决定落到那个桶是由初始 hash 值的最后 4 位决定的
扰一下，决定落到哪个桶是由初始 hash 值的最后 4 位和第 13-16 位总共 8 位决定的

[qwerthhusn]

虽然，全集合[-2147483648,2147483647]缩到了[0,15]是均匀的。
但是随机少量数据，通过 4 位和通过 8 位的分散概率肯定不一样。

[jie170601]

@qwerthhusn 是的随机少量的影响还是挺大的，可能数学专业惯性思维了，概率算的整个区间的🙃

[jie170601]

@x7395759 有人跑过了说能减少 10%的碰撞，但是这个和用的啥样本数据关系很大，不是很值得参考

[deadlyn]

https://www.javacodegeeks.com/2015/09/an-introduction-to-optimising-a-hashing-strategy.html