haskell - 关于大型哈希表(2^25 个元素)的建议

Question

我想用 Haskell 为 SHA1 的变体编写一个生日攻击程序，它只产生 50 位哈希值。为此，我需要一个能够存储大约的哈希表。 2^25 个条目。

此映射中的键将为 Int64，值将为短长度字符串(约 16 字节)。

对于使用哪种哈希实现有什么建议吗？

(忽略上次更新 - 我需要一个 2^50 个元素的位数组。)

Answer 1

对于每条 8 字节的 2^25 个条目，您正在查看大约 768MB 的存储空间来存储数据，最多可能大约 3 GB，以及存储字节串的实际开销 - 估计每个字节串 80 字节，然后您有要存储的哈希表/映射的内部结构以及 key 的装箱等。

这意味着您可以将驻留在内存中的整个内容存储在一台像样的机器上，这使问题相对理智，但您的收集时间会有点糟糕。

我建议通过对键空间进行分区来使用许多较小的哈希表，这样无论您使用什么哈希表，都可以并行运行大量更新。

至于实现:

您可以包装一堆不可变的哈希表，例如 IORef 中无序容器中的宽扇出哈希表，并使用某种atomicModifyIORef 或类似 ryan newton 的比较和交换原语之类的东西，或者您可以尝试使用旧的 Data .HashTable 以简单的命令方式实现。

后者将通过无序容器使用的哈希数组映射尝试的对数因子来改进渐近，但 Data.HashTable 有错误的常量。不过，就您问题的规模而言，这些因素可能会相互抵消。