3

ハッシュテーブルの現在の実装は線形プロービングを使用しており、今度は2次プロービングに移行したいと思います（後でチェーン化とおそらくダブルハッシュにも移行します）。いくつかの記事、チュートリアル、ウィキペディアなどを読みましたが、まだ正確に何をすべきかわかりません。

線形プロービングは、基本的に1のステップがあり、それは簡単に実行できます。ハッシュテーブルから要素を検索、挿入、または削除するときは、ハッシュを計算する必要があり、そのために次のことを行います。

index = hash_function(key) % table_size;

次に、検索、挿入、または削除中に、次のように空きバケットが見つかるまでテーブルをループします。

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + 1) % table_size;
    }
while(/* LOOP UNTIL IT'S NECESSARY */);

Quadratic Probingに関しては、「インデックス」ステップサイズの計算方法を変更する必要があると思いますが、それをどのように行うべきかわかりません。私はさまざまなコードを見てきましたが、それらはすべて多少異なります。

また、ハッシュ関数がそれに対応するように変更されたQuadratic Probingのいくつかの実装を見てきました（すべてではありません）。その変更は本当に必要ですか、それともハッシュ関数の変更を避けてQuadratic Probingを使用できますか？

編集： 以下のEli Benderskyによって指摘されたすべてを読んだ後、私は一般的な考えを得たと思います。http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspxのコードの一部は次のとおりです。 

15   for ( step = 1; table->table[h] != EMPTY; step++ ) {
16     if ( compare ( key, table->table[h] ) == 0 )
17       return 1;
18 
19     /* Move forward by quadratically, wrap if necessary */
20     h = ( h + ( step * step - step ) / 2 ) % table->size;
21   }

私が得られないことが2つあります...彼らは、二次プロービングは通常、を使用して行われると言いますc(i)=i^2。ただし、上記のコードでは、次のようなことを行っていますc(i)=(i^2-i)/2

私はこれを自分のコードに実装する準備ができていましたが、単純に次のようにします。

index = (index + (index^index)) % table_size;

...ではなく：

index = (index + (index^index - index)/2) % table_size;

どちらかといえば、私はします：

index = (index + (index^index)/2) % table_size;

...他のコード例が2つに分かれているのを見たからです。理由はわかりませんが...

1）なぜステップを引くのですか？
2）なぜ2でダイビングするのですか？

4

2 に答える 2

11

テーブルサイズが2の累乗である場合、2次プロービングを実装するための特にシンプルでエレガントな方法があります。

step = 1;

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + step) % table_size;
        step++;
    }
} while(/* LOOP UNTIL IT'S NECESSARY */);

元のインデックスからのオフセット0、1、2、3、4 ...を調べる代わりに、オフセット0、1、3、6、10 ...を調べます（i番目のプローブはオフセット（i * （i + 1））/ 2、つまり2次式）。

これは、テーブルサイズが2の累乗である場合、ハッシュテーブル内のすべての位置にヒットすることが保証されます（したがって、空のバケットがある場合はそれを見つけることが保証されます） 。

これが証明のスケッチです：

  1. テーブルサイズがnの場合、i = 0 ... n-1で（i *（i + 1））/ 2（mod n）のn個の異なる値を取得することを示したいと思います。
  2. これは矛盾によって証明できます。n個未満の個別の値があると想定します。その場合、（i *（i + 1））/ 2（mod n ） 同じです。これらをpおよびqと呼びます。ここで、p<qです。
  3. すなわち（p *（p + 1））/ 2 =（q *（q + 1））/ 2（mod n）
  4. =>（p 2 + p）/ 2 =（q 2 + q）/ 2（mod n）
  5. => p 2 + p = q 2 + q（mod 2n）
  6. => q 2 -p 2 + q --p = 0（mod 2n）
  7. 因数分解=>（q --p）（p + q + 1）= 0（mod 2n）
  8. （q --p）= 0は、自明なケースp=qです。
  9. （p + q + 1）= 0（mod 2n）は不可能です。pとqの値は[0、n-1]の範囲にあり、q> pであるため、（p + q + 1）は次のようになります。範囲[2、2n-2]。
  10. 2nを法として作業しているので、両方の因子がゼロ以外であるが、0（mod 2n）を与えるために乗算するというトリッキーなケースにも対処する必要があります。
    • 2つの因子（q --p）と（p + q + 1）の差が（2p + 1）であり、これは奇数であることに注意してください。したがって、因子の1つは偶数で、もう1つは奇数である必要があります。
    • （q --p）（p + q + 1）= 0（mod 2n）=>（q --p）（p + q + 1）は2nで割り切れます。 n（したがって2n）が2の累乗である場合、偶数の因数は2nの倍数である必要があります（2nの素因数はすべて2であるのに対し、奇数の因数の素因数はいずれも2ではないため）。
    • ただし、（q --p）の最大値はn-1であり、（p + q + 1）の最大値は2n-2であるため（手順9を参照）、どちらも2nの倍数にすることはできません。
    • したがって、この場合も不可能です。
  11. したがって、（ステップ2で）n個未満の個別の値があるという仮定は誤りである必要があります。

（テーブルサイズが2の累乗でない場合、これはステップ10でバラバラになります。）

于 2010-02-28T02:05:00.840 に答える
4

二次プロービングのためにハッシュ関数を変更する必要はありません。二次プロービングの最も単純な形式は、実際には、線形1、2、3ではなく、計算された位置に結果の正方形を追加することです。

ここに良いリソースがあります。そこから以下を取り上げます。これは、単純な多項式c(i) = i^2を使用する場合の2次プロービングの最も単純な形式です。

代替テキスト

より一般的なケースでは、式は次のとおりです。

代替テキスト

そして、あなたはあなたの定数を選ぶことができます。

ただし、2次プロービングは特定の場合にのみ役立つことに注意してください。ウィキペディアのエントリが述べているように：

二次プロービングは、参照の局所性をある程度保持するため、優れたメモリキャッシュを提供します。ただし、線形プロービングの方が局所性が高いため、キャッシュのパフォーマンスが向上します。二次プロービングは、免疫ではありませんが、線形プロービングで発生する可能性のあるクラスタリングの問題をより適切に回避します。

編集：コンピュータサイエンスの多くのものと同様に、二次プロービングの正確な定数と多項式はヒューリスティックです。はい、最も単純な形式はi^2ですが、他の多項式を選択することもできます。ウィキペディアはの例を示していh(k,i) = (h(k) + i + i^2)(mod m)ます。

したがって、「なぜ」の質問に答えるのは困難です。ここでの唯一の「理由」は、なぜ2次プロービングが必要なのかということです。他の形式のプローブとクラスター化されたテーブルの取得に問題がありますか？それとも、宿題だけですか、それとも独学ですか？

ハッシュテーブルの最も一般的な衝突解決手法は、チェーンまたは線形プロービングのいずれかであることに注意してください。二次プロービングは、特殊なケースで利用できるヒューリスティックオプションであり、自分が何をうまく行っているかを理解していない限り、これを使用することはお勧めしません。

于 2010-02-27T17:10:09.543 に答える