c - 如何为整数键编写保留最小完美散列的顺序？

Question

我已经搜索了 stackoverflow 和谷歌，但无法准确找到我正在寻找的内容:

我有一组 4 字节无符号整数键，最多一百万个左右，我需要将其用作表的索引。最简单的方法是简单地将键用作数组索引，但我不想使用 4gb 数组，因为我只打算使用几百万个条目!表条目和键是顺序的，因此我需要一个保留顺序的哈希函数。

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

我想将键翻译成{0, 1, 2, 3, 4, 5,....etc}

key 可能是任何整数，但总数不会超过 200 万。随着键(和相应的数组条目)将被删除，数字会有所不同，但新键的编号将始终高于之前编号最高的键。

在上面的例子中，如果键 69 被删除，那么在哈希 3493 上返回的哈希整数应该是 1(而不是 2)，因为它成为第二小的数字。

我希望我的解释是正确的。任何快速高效的哈希解决方案都可以实现上述目标吗？我需要翻译来接受 nS 的低 100 秒，尽管我预计删除需要更长的时间。我查看了 CMPH，但找不到任何不涉及从文件中获取数据的用法示例。需要在linux下运行，使用纯C用gcc编译。

Answer 1

其实，我不知道我是否明白你到底想做什么。

您似乎正在尝试获取存储在某处的按顺序排列的整数“数组”(或“列表”)中的索引号。

如果您将这些整数值存储在一个数组中，那么在最佳时间返回索引整数的算法就是二分查找。

Binary Search Algorithm

由于已知您的列表是有序的，因此二进制搜索在 O(log(N)) 时间内工作，这是非常快的。

如果您删除“键”列表中的一个元素，二分搜索算法仍然可以工作，无需额外的努力或空间(但是，删除列表中一个元素的操作自然会强制您移动所有元素位于被删除元素的右侧)。

当然，您只需向 Ninary Search Algorithm 提供三个数据:数组、数组的大小和所需的键。