Eri*_*ikR 2 hash haskell hashmap
我想在Haskell中编写一个生日攻击程序,用于SHA1的变体,它只产生50位散列.为此,我需要一个能够存储大约的哈希表.2 ^ 25个条目.
此映射中的键将是Int64,并且值将是短长度字符串(~16字节).
有关使用哈希实现的任何建议吗？
(无视上次更新 - 我需要一个2 ^ 50个元素的数组.)
对于每个8字节的2 ^ 25个条目,您只需要数据就可以看到768MB的存储空间,最多可能是大约3千兆字节,存储字节串的实际开销 - 每个字节串估计80个字节,然后你有哈希表/ map的内部存储,以及密钥的装箱等.
这意味着您可以将驻留在内存中的所有内容存储在一台体面的计算机上,从而使问题保持相对清晰,但您的收集时间会很糟糕.
我建议使用大量较小的哈希表,通过对键空间进行分区,这样您可以并行运行大量更新,而不管您使用的哈希表.
至于实施:
你可以在IORefs中包装一堆不可变的哈希表,比如来自无序容器的宽扇区哈希表,并使用某种atomicModifyIORef或类似ryan newton的compare和swap原语,或者你可以尝试使用旧的Data.HashTable实现以一种直截了当的方式.
后者将通过无序容器使用的散列数组映射尝试的对数因子来改进渐近因子,但Data.HashTable具有错误的常量.在你的问题的规模,这些因素可能会取消.