文字列を一様にハッシュしようとするハッシュテーブル？

Question

私は現在、セメスターの終わりに近づいているData Structuresコースに在籍しており、キーを格納および取得するためのLinked Hash Tableを実装するプロジェクトが割り当てられています。私たちは、ハッシュテーブルの実装をどのように設計するかについてかなり大きな自由を与えられましたが、私たちは、キー（一意の文字列）を一様かつ無作為に近く分布させるハッシュ関数テーブル。

私はここで見て、ELFハッシュを使用することを選択したhttp://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

次のように私の質問は：整数が返され、このハッシュ関数を使用すると、私はトラブルこの指定を支援するために使用することができる方法を見を持っています私のキーをハッシュテーブルに入れるための特定のインデックスです。私は単純に行うことができます：インデックス= ELFhash（文字列キー）％tableSize、これは最初の場所でELFハッシュを使用する目的を敗北か？

また、私は衝突解消戦略をダブルハッシュにすることを選択しました。あなたのジャンプを見つけるのに適切なセカンダリハッシュ関数を決定する良い方法はありますか？私のハッシュテーブルは一定のサイズではありません（文字列のセットがハッシュされているデータのセットから追加され、削除されます。追加と削除の繰返しのたびにリハッシュされます。 ）ので、私はk％nのような何かをするのは難しいです。ここで、nはテーブルの大きさに比例する数字です。

私の質問を読んでくれてありがとう、ありがとう、ありがとうと思うことを教えてください！

Answer 1

"折り返しバイアス"について考えるのは間違いありませんが、実際の目的では問題にはなりません。

ハッシュテーブルのサイズがNで、ハッシュ値が[0..M]の範囲にある場合は、k = floor(M/N)とします。 [0..k*N)の範囲のハッシュ値は、mod Nをマップとして使用して、各ハッシュバケットが正確にkのハッシュ値でマッピングされるという点で「良い」ものです。 [k*N..M)のハッシュ値は、それらを使用する場合、対応するM-K*n最低ハッシュバケットが1つの追加ハッシュ値からマップされるという点で「不良」です。ハッシュ関数が完全であっても、これらのバケットは与えられた値を受け取る可能性が高くなります。

質問は「どれくらい？それはMとNに依存します。ハッシュ値が[0..2^32)のunsigned intであり、Knuthなどを読んでいる場合は、何千ものバケット、たとえば1009を選ぶことになります。

floor(2^32/1009) = 4256657 

「悪い」の値の数が

2^32 - 4256657 * 1009 = 383 

その結果、すべてのバケットが4256657「良い」の値からマッピングされている、と383は、このように4256658.のための1つの追加の不要な「悪い」の値を取得"バイアス"は1/4,256,657です。

バケット間で400万の確率差が目立つようなハッシュ関数を見つけることはほとんどありません。

ここで、1,000の代わりに100万個のバケットを使用して計算をやり直すと、状況は少し違って見えます。そのような場合には、ちょっとOCならば、64ビットのハッシュに切り替えることができます。

追加事項：Elfハッシュは絶対に恐ろしい結果を与えることはほとんどなく、非常に高速ですが、はるかに優れたハッシュ関数があります。あなたが試してみたいかもしれない、合理的に評価されているものは、Murmur 32です。（Wikiの記事では、オリジナルのalgにはDoS攻撃のために悪用できる弱点があると述べていますが、あなたのアプリケーションでは問題ありません）あなたの教授がコードをコピーしたくないと確信していますが、Wikipediaページにはそれは完了する。 Elfを自分で実装し、Murmurに対してそれらを比較してみると面白いでしょう。