这是一个创建于 1953 天前的主题，其中的信息可能已经有所发展或是发生改变。
无意中看到 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 2019-07-25 16:54:30 +08:00
你不是说你看了源码？ index 是 hash 值和长度做与操作出来的啊...长度一般比较小基本就是低位掩码了，所以把高位信息混进来鸭。
|
 |
2
x7395759 2019-07-25 17:30:24 +08:00
你两种都跑一下不就知道了
|
 |
3
qwerthhusn 2019-07-25 17:35:16 +08:00
当然了，当桶数为 16 的时候，
决定落到那个桶是由初始 hash 值的最后 4 位决定的 扰一下，决定落到哪个桶是由初始 hash 值的最后 4 位和第 13-16 位总共 8 位决定的 |
|
4
qwerthhusn 2019-07-25 17:38:20 +08:00  1
虽然，全集合[-2147483648,2147483647]缩到了[0,15]是均匀的。
但是随机少量数据，通过 4 位和通过 8 位的分散概率肯定不一样。 |
 |
5
jie170601 OP @qwerthhusn 是的随机少量的影响还是挺大的，可能数学专业惯性思维了，概率算的整个区间的🙃
|
|
6
jie170601 OP @x7395759 有人跑过了说能减少 10%的碰撞，但是这个和用的啥样本数据关系很大，不是很值得参考
|
 |
7
deadlyn 2019-07-26 11:30:45 +08:00 1
|
Select Language