无意中看到 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]，
假如数据分布均匀，
碰撞率应该是一定的呀？
 |
1
morethansean Jul 25, 2019
你不是说你看了源码？ index 是 hash 值和长度做与操作出来的啊...长度一般比较小基本就是低位掩码了，所以把高位信息混进来鸭。
|
 |
2
quickma Jul 25, 2019
你两种都跑一下不就知道了
|
 |
3
qwerthhusn Jul 25, 2019
当然了，当桶数为 16 的时候，
决定落到那个桶是由初始 hash 值的最后 4 位决定的 扰一下，决定落到哪个桶是由初始 hash 值的最后 4 位和第 13-16 位总共 8 位决定的 |
|
4
qwerthhusn Jul 25, 2019  1
虽然，全集合[-2147483648,2147483647]缩到了[0,15]是均匀的。
但是随机少量数据，通过 4 位和通过 8 位的分散概率肯定不一样。 |
 |
5
jie170601 OP @qwerthhusn 是的随机少量的影响还是挺大的，可能数学专业惯性思维了，概率算的整个区间的🙃
|
Select Language