我有 64 位正整数（范围从 0 到 2 63 - 1），我想将它们散列成 32 位正整数（0 到 2 31 - 1 范围）。
我的数据具有高斯分布。任何人都可以建议一个散列函数来为这个分布提供少量的冲突吗？
（原始问题在这里，我已经改进了。）
问问题
1820 次
2 回答
3
您可以首先通过（预期的）累积分布函数映射您的输入数据，然后输出（预期）均匀分布的结果。然后，您可以将该数据放入常规的 64 到 32 位散列函数中。
于 2012-11-09T10:01:17.747 回答
2
基于 Long 的哈希值，它是一个 64 位整数。
int hash = (int) ((l >>> 32) ^ l);
顺便说一句：高斯分布是有符号的，我认为它不适合无符号值。
如果你有一些遵循高斯分布的东西已经被缩放和移动，那么低 32 位可能仍然是完全随机的。（取决于比例）如果低 32 位是随机的，那么高位是什么（它们都可以是 0）并不重要，并且散列仍然是伪随机的。
顺便说一句：即使您的哈希在转换为 32 位值时是唯一的，您也必须进一步减少它以节省内存（除非您有自己的 2^32 大小的哈希表）这意味着在进一步减少值之后对于一些合理的东西，例如样本数量的两倍，你会遇到一些冲突（除非你的 64 位值比你需要的多得多）
于 2012-11-09T09:44:36.147 回答