java - 64 位无符号哈希函数

Question

我有 64 位无符号整数(范围从 0 到 2^63 - 1)，我想将它们散列为 32 位无符号整数(范围 0 到 2^31 - 1)。

数据如下Uniform Distribution .任何人都可以建议一个散列函数，该函数将为该分布提供较少的冲突(可能有一定的冲突发生概率)吗？

Answer 1

如果真的分布均匀，那么就取低n位(哈希值的宽度)。这意味着，在最坏的情况下，一个桶中可以有 2^N-n 个元素。 (这里N表示原数的宽度)

注意:刚刚看到@JanDvorak 已经建议了这个(在我回答之前)，使用模 2ⁿ 相当于取较低的 n位...

如果这真的是关于64 位无符号整数 被散列为32 位无符号整数，那么正确的范围将是[0;2 ⁶⁴-1]和[0;2³²-1]，至多2³² 单个散列上的冲突。然而，在Java中，没有无符号整数...

如果这是关于分别使用带符号的 64 位和 32 位整数值的正半部分，那么您的范围值是正确的，您仍然会遇到 2³² 冲突最坏的情况。