V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
This topic created in 2476 days ago, the information mentioned may be changed or developed.
无意中看到 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