映射函数

Question

3

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

我有一组128位的数字，集合大小小于2的32次方，理论上我可以有一个映射函数，将所有的128位数字映射到32位数字。请问如何构造这个映射函数？

- Avishek Bhattacharya

你能预测128位数字（或其模式）吗？ - Taha Jahangir

3

你的确切目标是什么？请不要使用“地图”一词进行解释。你使用的语言是什么？ - Dialecticus

@Dia：我猜他想要一个哈希函数，基于[hash]标签。但是对你的评论点个赞 :-) - Aryabhatta

@Moron：这个[哈希]标签不是由原帖作者添加的。 - abeln

4个回答

0

如果不知道输入数据的性质，就无法给出最优的哈希算法。但是如果输入数据是均匀分布的，那么可以使用输入数据的低32位。这意味着可能会发生冲突，因此您需要处理它。

- Fantius

0

通用的构造方法是将所有128位值保存在一个大数组中，按升序排序。然后，每个值都被“映射”到其在数组中的索引位置。为了“计算”映射，您需要在数组中进行二分查找，以获取值在数组中的精确索引。对于2^32个值，数组的大小为64 GB，并且二分查找涉及35次左右的数组查找。

总的来说，你不能真正做得比这更好。但是，如果你的128位值具有合理的均匀分布（这取决于它们来自哪里），那么大数组结构可以被大幅压缩，特别是如果你能保证所有输入到你的映射都将始终是128位值集合的一部分；我打赌你可以将其缩减到几个GB——但查找会更加昂贵。

对于更实际的解决方案，您将不得不处理您的128位值的结构：它们来自哪里，代表什么......

- Thomas Pornin

0

将您的数字位置设置为其值除以2^32的商。

- dhblah

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aryabhatta · Accepted Answer

似乎您正在寻找将n个键映射到n个连续整数的最小完美哈希。

上述句子中的维基页面链接提到了实现此功能的两个库。