0

大量の数値をデータ構造に格納したいので、ハッシュ関数を使用して、挿入、削除、または検索を高速化します。しかし、どのハッシュ関数を使用すればよいか判断できません。

そして一般的に、ハッシュ関数が特定の問題に適していると判断する方法を知りたいですか?

編集：「ランダム」という用語を使用して人々を混乱させたと思います。ここでランダムとは、つまり、[任意の 32 ビット整数] を選択する必要がある特定の範囲の数値はありませんが、約 5000 の数値のようにデータ構造に格納するために与えられる合計数があります。 . では、このシナリオに最適なハッシュ関数を提案してください。

4

3 に答える 3

4

数値が一様にランダムな場合は、下位ビットを選択するハッシュ関数を使用してください。

unsigned hash_number(long long x)
{
    return (unsigned) x;
}
于 2013-03-17T05:44:27.727 に答える
1

入力数値が完全にランダムであっても、h(x) = x を使用するとパフォーマンスの問題が発生する可能性があります。数値は 0、2、4、...、2k からランダムに選択されますが、ランダムではありますが、ハッシュ テーブルの最初のバケット (バケット 0) にはマップされません。したがって、本当に重要なのは、入力数値の情報エントロピーです。

あなたの場合の優れた選択肢は、Thomas Wang の整数ハッシュ関数です。これは可逆で、良好な雪崩効果を維持します ( http://en.wikipedia.org/wiki/Avalanche_effect )。Thomas Wang のハッシュ関数とその逆関数について説明した記事があります: http://naml.us/blog/2012/03。

于 2013-03-22T07:55:25.227 に答える
0

あなたの質問は私には意味がありません。一部の乱数を格納するためにハッシュ アルゴリズムを使用するのはやり過ぎです。問題にさらに何かがある場合、データ構造の選択は、この何かが何であるかによって異なります(あなたは言いません)。

これらの数値が実際に乱数または疑似乱数である場合、必要なのはスタックまたは循環バッファーだけです。新しい乱数をデータ構造に追加 (プッシュ) する機能と、既存の乱数を構造から削除 (ポップ) する機能が必要です。それらを順番に取得する場合は、循環バッファーを使用します。ハッシュ関数は、乱数のリストを保持するための単純なスタック (または循環バッファー) よりもあらゆる点で劣っています。より複雑で、実行速度が遅く、より多くのメモリを使用します。

ほとんどの言語/環境では、「辞書」クラスとして使用できる (または提供されている) ハッシュ関数が提供されており、これらには効率に関するガイダンスが付属しています。一般に、より多くのメモリを割り当てることで辞書クラスを高速化できます。ハッシュ キーが衝突すると速度が低下します。したがって、すべての可能な数の中で実際の数の「密度」が重要です。

したがって、そのような数値を 100 個保持する必要がある場合は、最後の 12 ビットのみを調べるハッシュ関数を使用できます。これにより、2^12 = 4096 の可能なハッシュが得られるため、衝突は 100/2048 の確率でのみ発生し、5% 未満になります。一方で、本来の 20 倍以上のメモリを使用しています。(この関数は、数値のモジュラスを 2^12 を基数にするのと同じであり、Epp が提案したものと似ています。)

ハッシュ衝突を適切に処理し (必要に応じて)、重複データを適切に処理し、悪いデータ (すべての数値が同じなど) をチャックしてもおかしくなりません。些細な仕事。

一方、スタックまたは循環バッファーの実装は非常に単純で効率的であり、完全に予測可能な動作をします。

これを必要以上に複雑にしていませんか?

于 2013-03-17T12:33:45.987 に答える