java - 64 位无符号散列函数

Question

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

数据遵循均匀分布。任何人都可以建议一个散列函数来为这个分布提供少量的冲突（可能有一定的冲突发生概率）？

Answer 1

如果 的分布真的很均匀，那么只取低位n（散列值的宽度）。这意味着，在最坏的情况下，您可以在一个桶中有 2 ^{N-n 个元素。}（这里N表示原数字的宽度）

注意：刚刚看到@JanDvorak 已经提出了这个建议（在我回答之前），使用模 2 ⁿ相当于取低位n......

如果这真的是大约64 位无符号整数被散列成32 位无符号整数，那么正确的范围将是[0;2 ⁶⁴ -1]和[0;2 ³² -1]，一次最多有2 ^{32 次}冲突哈希。然而，在Java中，没有无符号整数......

如果这是关于分别使用带符号的 64 位和 32 位整数值的正半部分，那么您的范围值是正确的，在最坏的情况下您仍然会有2 ^{32 次}冲突。

Answer 2

对于这样一个简单的分布，任何合理的散列函数都适合。为了确保，只需尝试(int)(longvalue+(longvalue>>32))计算碰撞次数。如果您只想要 31 位，请制作res&0x7fffffff（为什么强调值是无符号的？31 位 int 和 63 位 long 适合有符号和无符号范围）。

Answer 3

如果您已经拥有正确的长度和均匀分布的位，为什么还要散列？我假设您有一些安全要求？请分享。

如果它是您正在寻找的标准哈希，请考虑 SHA-1：

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
//Some more imports

MessageDigest md = MessageDigest.getInstance("SHA-1");
md.update(data);
byte[] hash = md.digest());