映射功能
我有一组 128 位数字，并且集合的大小 < 2^32 ...所以理论上我可以有一个映射函数，将所有128位数字映射到32位数字....我如何构建映射函数???
I have a set of 128bit number and the size of set < 2^32 ...so theoretically I can have a mapping function that maps all the 128bit numbers to 32 bit number ....how can I construct the mapping function ???
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
似乎您正在寻找映射 n 个键的 最小 完美哈希到n个连续的整数。
上面句子中的 wiki 页面链接提到了两个实现此功能的库。
另请参阅此了解更多详细信息： http://burtleburtle.net/bob/hash/perfect.html< /a>
Seems like you are looking for a minimal perfect hash which maps n keys to n consecutive integers.
The wiki page link in the above sentence mentions two libraries which implement this.
Also see this for more detail: http://burtleburtle.net/bob/hash/perfect.html
如果不知道输入数据的性质，就不可能给出最佳的哈希算法。但如果输入均匀分布，那么您可以使用输入的低 32 位。这意味着发生碰撞的可能性，所以你必须处理这个问题。
Without knowing the nature of the input data, it's impossible to give the optimal hashing algorithm. But if the input is evenly distributed then you could use the lower 32 bits of the input. This means the possibility of collisions, so you have to deal with that.
通用结构是将所有 128 位值保存在一个大数组中，并按升序排序。然后，每个值都被“映射”到其在数组中的索引。要“计算”映射，您需要在数组中进行二分搜索，以获取数组中值的精确索引。如果有 232 个值，则数组大小为 64 GB，二分搜索需要在数组中进行 35 次左右的查找。
总的来说，你不可能做得比这更好。但是，如果您的 128 位值具有相当均匀的分布（这取决于它们来自哪里），那么大数组结构可以大幅压缩，特别是如果您可以保证映射的所有输入始终是一部分128 位值的集合；我敢打赌，您可以将其缩减到几 GB，但查找成本会更高。
对于更实用的解决方案，您必须使用 128 位值的结构：它们来自哪里，它们代表什么......
The generic construction is to keep all your 128-bit values in a big array, sorted in ascending order. Then, each value is "mapped" to its index in the array. To "compute" the map, you do a binary search in the array, to get the precise index of the value in the array. With 232 values, the array has size 64 GB, and the binary search entails 35-or-so lookups in the array.
In all generality you cannot do really better than that. However, if your 128-bit values have a reasonably uniform spread (it depends from where they come), then the big array structure can be compressed by a large margin, especially if you can guarantee that all inputs to your map will always be part of the set of 128-bit values; my bet is that you can trim it down to a couple of gigabytes -- but the lookup will be more expensive.
For a more practical solution, you will have to work with the structure of your 128-bit values: where they come from, what they represent...
将数字的位置设置为其值除以 2^32 的值。
Set a position of your number as division of it's value on 2^32.