1

私は私を悩ませているこの独特のコードを持っています、

   // exbPtr points to 128-bit unsigned integer
   // lgID is a "short" with 0xFFFF being the max value

   int hash = (*exbPtr + (int)lgID * 9) & tlpLengthMask;

最初に、実際には配列であるこの「ハッシュテーブル」は256要素に初期化され、tlpLengthMaskは255に設定されます。

次に、この不思議なコードがあります。そのすぐ上に、「ここに到達した場合、衝突が発生しました」というコメントがあります。そして、再びループバックを開始するので、これはハッシュの衝突であり、再ハッシュしているように見えますか？

   hash = (hash + (int)lgID * 2 + 1) & tlpLengthMask;

さらに、モジュラスとしてマスクを使用しているため、この配列の長さは2の累乗である必要があることを示す大量のデバッグコードがあります。

誰かが著者の意図が何であったかを説明できますか？この背後にある理由は何ですか？

編集-私が識別しようとしているのは、なぜ彼が9を掛けたのか、そしてなぜ2を掛けて再ハッシュするのかということです。

4

1 に答える 1

1

3つの可能性があります：

1）元の作者は、ハッシュ関数を多かれ少なかれランダムに構築し、それらが十分に機能することを確認し、そのままにしました。

2）元の作成者は、実際のデータを適切に表すテストデータを持っており、これらの関数が彼の正確なアプリケーションに対して非常にうまく機能することを確認しました。

3）このコードのパフォーマンスは非常に低く、彼のハッシュテーブルはまったく効率的に動作していません。

唯一の実際の要件は、出力が実際に遭遇する入力についてハッシュテーブル全体に均等に分散されているように見え、同じ入力に対して常に同じ出力を生成することです。これらの種類の機能は一般にパフォーマンスが低くなりますが、この特定のアプリケーションには十分な場合があります。

ちなみに、このタイプのオープンハッシュは削除に直面しても機能しません。たとえば、テーブルに1つのレコードを追加するとします。次に、2番目を追加しますが、最初の1つと衝突するため、先にスキップして2番目を追加します。これですべてが正常になりました。最初のレコード（直接）と2番目のレコードの両方を見つけることができます（2番目のレコードのハッシュ位置で最初のレコードを見つけたらスキップします）。

しかし、最初のレコードを削除した場合、どのようにして2番目のレコードを見つけますか？2番目のレコードのハッシュ位置を見ると、何も見つかりません。スキップしてみますか？もしそうなら、何回ですか？

これらの問題には回避策がありますが、誤って実行するのは非常に簡単です。

于 2012-05-29T08:49:14.400 に答える