Perl的完美哈希函数(如gperf)？

Question

我将使用key:value存储，并希望在Perl中创建不可冲突的散列。有没有Perl模块或函数可以用来生成不可冲突的散列函数或表(可能类似于gperf)？我已经知道了输入值的范围。

Answer 1

我找不到一个纯Perl的解决方案，最接近的是Reini Urban's examinations of using perfect hashes with a type system。如果使用XS，CMPH (C Minimal Perfect Hashing Library)可能比gperf更合适。CMPH似乎针对重要的密钥大小和运行时生成进行了优化。

在Perl中运行时生成一个完美的散列函数的成本可能会掩盖使用它的价值。为了获得好处，你会希望它被编译和缓存。因此，编写一个在XS编译时从固定键列表生成函数的XS模块可能是最好的方法。

出于好奇，您的数据量有多大，该集合包含多少个密钥？

Answer 2

您可能会对Judy感兴趣。它不是一个哈希表实现，但它被认为是一个非常有效的关联数组实现。

请注意，Perl的散列调整得非常好，当存储桶开始变大时，它们会自动重新散列。