ハスケルで50ビットのハッシュのみを生成するSHA1の亜種のバースデー攻撃プログラムを作成したいと思います。これを行うには、私は約保存可能なハッシュテーブルが必要です。 2^25エントリ。大きなハッシュテーブル（2^25要素）の提案
このマップのキーはInt64になり、値は短い文字列（〜16バイト）になります。
どのハッシュ実装を使用するべきですか？
（その最後の更新を無視してください - 。私は2^50の要素のビット配列を必要とする）
私はまた質問の同じ種類を掲載。そしていくつかの提案から、私はKyoto Cabinetを使用しています。それはかなりクールであり、素晴らしいパフォーマンスも与えます。同様の問題があるので、私の投稿をチェックすることもできます。 EX。 one,twoおよびthree。多分これは役に立つかもしれません。
8バイトの2^25エントリの場合、データだけのために768MBの記憶域がありますが、実際にはテイクリングを格納するための実際のオーバーヘッドとともに約3ギガバイトあります。バイトごとに80バイトを推測します
これは、まともなマシンに常駐しているものをメモリに格納することができるということです。これは、問題が比較的まれであるが、収集時間が長くなることを意味します。これは、ハッシュテーブル/マップの内部格納とキーのボクシングです。一種の吸うだろう。
あなたのキースペースを分割することによって、多くの小さなハッシュテーブルを使用することをお勧めします。これは、使用するハッシュテーブルに関係なく、多くの更新を並行して実行することができます。実装用として
：あなたは、比較とスワッププリミティブIORefsに順不同コンテナから幅広いファンアウトもののような不変のハッシュテーブルの束をラップし、ライアン・ニュートンのようatomicModifyIORefか何かのいくつかの種類を使用することができますいずれか
、古いData.HashTable実装を簡単な方法で使用することもできます。
後者は、順序付けられていないコンテナで使用されているハッシュ配列のマップされた試行よりもログファクタであなたの漸近線を改善しますが、Data.HashTableは不正な定数を持ちます。あなたの問題のスケールでは、これらの要因はおそらくキャンセルされます。
Data.HashTableよりも優れた定数を持つ変更可能なハッシュテーブルについては、Gregory Collinsのハッシュテーブルパッケージ（http://hackage.haskell.org/package/hashtables）を参照してください。 – reinerp
さて、SQLは最もシンプルでしょう。しかし、それらは、ストレージ内や「ストレージ内のソート」というハッシュテーブルのバリエーションがたくさんあります。多くは、使用環境とデータの特性のいくつか（分散されているかなど）によって異なります。 –