Perl的完美哈希函数（类似于gperf）？

Question

我将使用键值存储，并希望在Perl中创建不可碰撞的哈希。是否有可以用于生成不可碰撞哈希函数或表的Perl模块或函数（也许类似于gperf的东西）？我已经知道我的输入值范围。

- EhevuTov

---

啊，阅读理解失败。对此感到抱歉... - Amadan

哦，非常棒。谢谢你让我更好地理解了Perl中快速构建哈希的方法 :-) 我可能最终会使用gperf和XS。 - EhevuTov

Answer 1

我找不到一个纯Perl的解决方案，最接近的是Reini Urban对使用完美哈希和类型系统的研究。如果你想用XS来实现，CMPH（C Minimal Perfect Hashing Library）可能比gperf更适合。CMPH似乎针对非平凡的键大小和运行时生成进行了优化。

在Perl中运行时生成完美哈希函数的成本可能会超过使用它的价值。为了获得好处，您需要将其编译并缓存。因此，编写一个XS模块，在XS编译时从固定的键列表生成该函数可能是最好的方法。

出于好奇，你的数据有多大，集合包含多少个键？

- Schwern

---

我刚开始了解哈希的工作原理，所以目前看起来这似乎是可行的方法。我将把它用作键值存储中的键，可能是LevelDB。基本上，我需要一个键值或多键值存储，仅在高写入率实时系统上对一个键进行简单的去重计数（聚合）。该键将在24小时内进行计数，然后将该聚合转储到CSV文件中，并且该存储将被删除一整天。 - EhevuTov

我想要存储的数据每个记录大约有1k长，每天总共超过2G。密钥相当长，大约30个字符和一些整数。我不知道这是否可行。 - EhevuTov

@EhevuTov 我强烈建议您在尝试完美哈希算法之前，先使用您的原始数据库对系统性能进行分析。除非您的数据是病态的，而我认为LevelDB的原始哈希算法已经相当不错了，哈希冲突不太可能成为您的瓶颈。 - Schwern

@EhevuTov 阅读关于LevelDB的资料，从性能角度来看，最明显的问题是“只有一个进程（可能是多线程）可以同时访问特定的数据库”，这极大地限制了您对数据的访问、并行工作的能力或者通过增加硬件来解决问题的能力。您可能希望从一个不那么基础的数据库开始。 - Schwern

这是一个大量写入I/O的系统，因此如果我向I/O投入更多线程，我认为性能会降低而不是提高。我会使用某种类型的哈希池来线程化哈希。我正在研究SQLite和MongoDB作为替代方案，但我怀疑它们的速度不会那么快。 - EhevuTov

Answer 2

你可能会对 Judy感兴趣。它不是哈希表实现，但据说是非常高效的关联数组实现。

请注意，Perl的哈希表已经非常优化，并且在桶开始变得很大时会自动重新散列。

- ikegami

---

谢谢你提醒我。也许我会在另一个项目中使用Judy。我正在开发实时系统，因此重新哈希对我来说不是很好。看起来我可能还需要为哈希制作工作进程。还不确定如何做。 - EhevuTov