Gperf在我的环境中始终不如Judy数组好,我想知道是否还有另一个专门为整数键构建的完美哈希库。我事先知道密钥集,我想将其用于性能/大小优势。
有大约1000个键,并且检索不是按顺序进行的。密钥对都是整数。密钥为32位,而检索到的值为8位。大小是最重要的因素。
如果有一种方法可以调整Gperf的整数键,或者通常只是另一种方法,那么我也很高兴。:)
(旁注:…在输入此问题时,我意识到二进制搜索可能会很麻烦,但我只是对此问题进行了过度思考。我仍然想听听您为学习而可能有的想法,虽然!)
编辑:密钥不均匀分布。大多数随机分布在整个可能范围内。
编辑2:最坏情况的二进制搜索对于我的口味来说太慢了,因此我最终使用了这些键,直到发现每个键都可以使用8位来制作256个分布均匀的存储桶。我保存每个存储桶的最小值和最大值(每个存储桶条目为24位),并为键对制作了一个大结构数组。与我针对特定案例测试的所有内容相比,同等/更快,更小,因此我想现在就可以使用。:)
保持键排序,并使用M树检索任何键。
一个M树的每个节点有M个条目,而不是2个。这将极大地提高性能。使用高速缓存行大小作为节点大小的基础,因此为64字节。您可以以此大小存储16个32位值。
因为您有1000个值,所以3个级别将足以检索正确的键(而二叉树则为10个级别)。
另一个想法是将您的密钥哈希到一个小的哈希表中,例如12位的哈希表(4K条目),并通过一条简单的链解决潜在的冲突。您很可能会在一次搜索中获得大部分密钥。