如何编写针对整数键的保序最小完美哈希函数？

Question

5

我在stackoverflow和谷歌上搜索，但没找到我要的内容，具体是这样的：

我有一组4字节无符号整数键，最多有100万个左右，我需要将它们用作索引到表中。最简单的方法是将键直接用作数组索引，但我不想在只使用几百万条记录时就拥有一个4GB的数组！表条目和键是连续的，因此我需要一个保留顺序的哈希函数。

例如。 keys = {56, 69, 3493, 49956, 345678, 345679,....etc}

我想将这些键转换为{0, 1, 2, 3, 4, 5,....等}。

这些键可能是任何整数，但总数不会超过200万。数字会因为删除键（及相应的数组条目）而发生变化，但新键始终比以前的最高编号更高。

在上面的例子中，如果删除了键69，则哈希3493返回的哈希整数应为1（而不是2），因为它成为第二低的数字。

我希望我解释得清楚。是否有任何快速高效的哈希解决方案可以实现上述功能？我需要翻译在低100毫微秒内完成，但我预计删除需要更长时间。我查看了CMPH，但找不到任何不涉及从文件获取数据的用法示例。它需要在Linux下运行，并使用纯C编译。

- poby

4个回答

1

这里有一个完整的Python实现链接在此。同时，也可以参考这里提供的资料。如果你只需要解码字典，最简单的方法是修改Python代码，使其输出定义所需数组的C文件，并重新实现查找函数。

- michaelmeyer

0

可以通过使用两个动态分配的数组来解决问题：一个用于“键”，另一个用于键的数据。

要获取特定键的数据，首先在键数组中找到它，其在键数组中的索引是数据数组的索引。

当您删除键-数据对或想要插入新项时，重新分配数组，并将键/数据复制到正确的位置。

我不声称这是最好或最有效的解决方案，但它是解决您问题的一种方法。

- Some programmer dude

0

你不需要一个保序的最小完美哈希，因为任何老旧的哈希都可以。你不想使用一个4GB的数组，但是对于2MB的项目，你不介意使用3MB的查找条目。

标准的哈希映射实现就可以胜任这项工作。它将允许您删除和添加条目，并在添加它们时分配任何值给条目。

这让你面临一个问题：“我应该在整数上使用什么哈希函数？”通常的答案是取质数除法余数。所选的质数应比您预期的数据稍大一些。例如，如果您预计有2M个项目，则选择一个约为3M的质数。

- johnstosh

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

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

- pablo1977 · Accepted Answer

实际上，我不知道我是否理解了您想要做的确切内容。

看起来您正在尝试获取您存储在某处的顺序整数的“数组”（或“列表”）中的索引号。

如果您已将这些整数值存储在数组中，则返回索引整数的算法是二分查找。

由于您的列表已知为有序的，因此二分查找在O(log(N))时间内运行非常快。

如果您删除了“键”列表中的一个元素，则二分查找算法仍然可以工作，而无需额外的工作或空间（但是，自然地，删除列表中一个元素的操作会强制您移动所有位于删除元素右侧的元素）。

您只需要向Ninary Search算法提供三个数据：数组，数组大小和所需的键。