查找已知的整数键集

Question

在我的环境中，Gperf 的性能始终低于 Judy 数组，我想知道是否有另一个专门为整数键构建的完美哈希库。我事先知道一组键，并且我想利用它来获得性能/尺寸优势。

有大约 1000 个键，并且检索不按顺序排列。密钥对都是整数。密钥是 32 位，检索的值是 8 位。尺寸是最重要的因素。

如果有一种方法可以针对整数键调整 Gperf，或者只是另一种方法，我也会洗耳恭听。:)

（旁注：...在输入这个问题时，我意识到二分搜索可能会更有效，而且我只是过度思考了这个问题。为了学习，我仍然想听听您的任何想法，尽管！）

编辑：键分布不均匀。大多数是在整个可能的范围内随机聚集的。

编辑 2：最坏情况的二进制搜索对我来说太慢了，所以我最终使用了这些键，直到我找到每个键可以使用 8 位来创建 256 个均匀分布的存储桶。我保存了每个桶的最小值和最大值（每个桶条目 24 位），并为密钥对创建了一个大的结构数组。与我在特定情况下测试的其他所有产品相比/更快且更小，所以我想我现在就采用它。:)

Answer 1

保持密钥排序，并使用 M 树来检索任何密钥。

M 树的每个节点有 M 个条目，而不是二进制文件的 2 个条目。这将对性能有很大帮助。使用缓存行大小作为节点大小的基础，因此为 64 字节。您可以在此大小中存储 16 个 32 位值。

由于您有 1000 个值，因此 3 个级别足以检索正确的键（而不是二叉树的 10 个级别）。

另一个想法是将密钥散列到一个小型散列表中，例如 12 位散列表（4K 条目），并使用简单的链解决潜在的冲突。您很可能在一次搜索中获得大部分密钥。