キーのハッシュ コードからハッシュ テーブルのバケット インデックスを計算するときに、バケットの配列のサイズが 2 のべき乗である場合に、除算後の剰余 (モジュロ) を使用しないのはなぜですか?
1384 次
2 に答える
5
ハッシュを計算するときは、ビット範囲全体に適切に分散して、安価に変更できる限り多くの情報が必要です。たとえば、32 ビットの符号なし整数は、大量 (>30 億) のアイテムがない限り、通常は適切です。ハッシュテーブルに格納します。
ハッシュ コードを、本当に興味のあるバケット インデックスに変換します。バケットの数 n が 2 の累乗の場合、ハッシュ コード h と (n-1) の間で AND 演算を実行するだけで済みます。結果は h mod n に等しくなります。
これが良くない理由は、AND 演算が単純にビット (高レベルのビット) をハッシュ コードから破棄しているためです。これは、他のものに応じて、良い場合も悪い場合もあります。AND は除算よりもはるかに高速であるため (これが、2 の累乗のバケット数を使用することを選択する通常の理由です)、一方では非常に高速になりますが、他方では、貧弱なハッシュ関数は下位ビットの貧弱なエントロピー: つまり、ハッシュされるデータが変更されても、下位ビットはあまり変化しません。
于 2008-11-10T11:21:24.887 に答える
0
テーブルのサイズが m = 2^p だとしましょう。k をキーとします。次に、k mod m を実行するたびに、k のバイナリ表現の最後の p ビットのみを取得します。したがって、同じ最後の p ビットを持つ複数のキーを入力すると、すべてのキーがテーブル内の同じスロットにハッシュされるため、ハッシュ関数のパフォーマンスが非常に悪くなります。したがって、2 の累乗を避ける
于 2010-12-12T14:54:43.260 に答える