映射函数

Question

我有一组128位数和集合的大小< 2^32 ...所以理论上我可以有一个映射函数，将所有的128位数映射到32位数....我怎么构造映射函数

Answer 1

好像你正在寻找一个最小perfect hash它将n个键映射到n个连续的整数。

上述句子中的wiki页面链接提到了两个实现它的库。

也看到更多的细节：http://burtleburtle.net/bob/hash/perfect.html

Answer 2

如果不知道输入数据的性质，它不可能给最优的哈希算法。但是如果输入是均匀分布的，那么你可以使用输入的低32位。这意味着碰撞的可能性，所以你必须处理。

Answer 3

通用结构是将所有128位值保存在一个大数组中，按升序排列。然后，每个值被“映射”到数组中的索引。要“计算”地图，您需要在数组中进行二分搜索，以获取数组中值的精确索引。使用2 值，数组的大小为64 GB，二进制搜索需要在数组中进行35次左右的查找。

在所有的普遍性，你不能做的比这更好。然而，如果你的128位数值具有相当均匀的分布（取决于它们来自何处），那么大型数组结构可以被大量压缩，特别是如果你能保证所有地图输入总是成分128位值的集合;我敢打赌，你可以将其削减到几千兆字节 - 但查找会更加昂贵。

对于更实用的解决方案，你将与结构中的128位值的工作：他们来自哪里，他们代表着什么......

Answer 4

设置你的电话号码为师的位置它的价值在2^32。