一尘不染

在已知的整数键集上查找

algorithm

Gperf在我的环境中始终不如Judy数组好,我想知道是否还有另一个专门为整数键构建的完美哈希库。我事先知道密钥集,我想将其用于性能/大小优势。

有大约1000个键,并且检索不是按顺序进行的。密钥对都是整数。密钥为32位,而检索到的值为8位。大小是最重要的因素。

如果有一种方法可以调整Gperf的整数键,或者通常只是另一种方法,那么我也很高兴。:)

(旁注:…在输入此问题时,我意识到二进制搜索可能会很麻烦,但我只是对此问题进行了过度思考。我仍然想听听您为学习而可能有的想法,虽然!)

编辑:密钥不均匀分布。大多数随机分布在整个可能范围内。

编辑2:最坏情况的二进制搜索对于我的口味来说太慢了,因此我最终使用了这些键,直到发现每个键都可以使用8位来制作256个分布均匀的存储桶。我保存每个存储桶的最小值和最大值(每个存储桶条目为24位),并为键对制作了一个大结构数组。与我针对特定案例测试的所有内容相比,同等/更快,更小,因此我想现在就可以使用。:)


阅读 155

收藏
2020-07-28

共1个答案

一尘不染

保持键排序,并使用M树检索任何键。

一个M树的每个节点有M个条目,而不是2个。这将极大地提高性能。使用高速缓存行大小作为节点大小的基础,因此为64字节。您可以以此大小存储16个32位值。

因为您有1000个值,所以3个级别将足以检索正确的键(而二叉树则为10个级别)。

另一个想法是将您的密钥哈希到一个小的哈希表中,例如12位的哈希表(4K条目),并通过一条简单的链解决潜在的冲突。您很可能会在一次搜索中获得大部分密钥。

2020-07-28