2

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

此映射中的键Int64和值将是短长度字符串（~ 16 字节）。

关于使用哪个哈希实现的任何建议？

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

4

2 回答 2

6

对于每块 8 个字节的 2^25 个条目，您正在查看仅用于数据的 768MB 存储空间，最多可能大约 3 GB 存储字节串的实际开销——猜测每个字节串 80 个字节，那么您就有了哈希表/map 要存储的内部结构，以及密钥的装箱等。

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

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

至于实施：

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

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

于 2012-04-04T01:46:02.613 回答
2

我也发布了同样的问题。根据一些建议，我正在使用京都内阁。它非常酷，而且性能也很好。你也可以查看我的帖子，因为我也有类似的问题。前任。一、二、三。也许这可能会有所帮助。

于 2012-04-04T01:06:20.647 回答