如何为整数键编写保留最小完美哈希的顺序？

Question

我已经搜索了 stackoverflow 和 google，但无法准确找到我正在寻找的内容，这是：

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

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

我想把钥匙翻译成{0, 1, 2, 3, 4, 5,....etc}

键可以是任何整数，但总数不会超过 200 万个。由于键（和相应的数组条目）将被删除，因此该数字会有所不同，但新键的编号将始终高于先前编号最高的键。

在上面的示例中，如果密钥 69 被删除，则哈希 3493 返回的哈希整数应该为 1（而不是 2），因为它随后成为第二小的数字。

我希望我能正确解释这一点。以上是否可以通过任何快速有效的哈希解决方案实现？我需要翻译在 100 纳秒以下，但删除我预计需要更长的时间。我查看了 CMPH，但找不到任何不涉及从文件获取数据的使用示例。它需要在linux下运行，并使用纯C语言通过gcc编译。

Answer 1

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

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

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

二分查找算法

由于已知您的列表是有序的，因此二分搜索的工作时间为 O(log(N))，速度非常快。

如果您删除“键”列表中的一个元素，二分搜索算法无论如何都会起作用，无需额外的努力或空间（但是，删除列表中的一个元素的操作自然会强制您移动位于该位置的所有元素）被删除元素的右侧）。

您只需向九进制搜索算法提供三个数据：数组、数组的大小，当然还有所需的键。