64位无符号哈希函数

Question

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

数据遵循均匀分布。有人能建议一个哈希函数，该函数将为该分布提供较低数量的冲突(可能有一定的冲突发生概率)吗？

Answer 1

如果的分布真的是均匀的，那么只取较低的n位(哈希值的宽度)。这意味着，在最坏的情况下，一个bucket中可以有2个^N-N元素。(此处N表示原始编号的宽度)

注意：刚刚看到@JanDvorak已经提出了这一点(在我回答之前)，使用模2ⁿ相当于取较低的n位。。。

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

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

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());