2

約 6,400 万個の 64 ビットの一意の符号なし整数を 1 億 2,800 万個のバケット (27 ビット幅のアドレス) にハッシュしようとしていました。Bob Jenkin のHashLittleとMurmurハッシュを試しました (これらのハッシュ関数はどちらも 32 ビット ハッシュを提供し、それをマスクして 27 ビット アドレスを取得しました)。どちらの場合も、約 22% の衝突が発生し、最終的にバケットの 37% しか占有しませんでした。これは予期されていることですか、それとも何か間違っていますか? 衝突がはるかに少なく、バケツの占有が改善されることを期待していました。

4

2 に答える 2

6

http://en.wikipedia.org/wiki/Poisson_distributionに基づく近似を使用すると、ランダムに予想するよりもわずかに悪いように見えます。バケット内の予想エントリ数が 1/2 の場合、0 エントリの確率は exp(-0.5) = 0.607 であり、バケット内の 1 エントリの確率はこの約半分、つまり 0.303 であると予想します。これにより、バケットに 2 つ以上のエントリがある確率は 0.09 になります。

整数はすべて一意ですか? そうでない場合、重複した値をハッシュ衝突の原因としてカウントしていますか?

好都合な状況では、ハッシュ関数を選択して、ランダムに予想される衝突を少なくすることができます。p が素数の場合、hash(x) = x % p がこれを達成することがあります。

于 2014-08-09T18:53:58.747 に答える
1

「ランダムだが再現可能な」結果を取得したい場合 - 意図的に難しい入力*でも最悪の場合の衝突率が最も高い結果を得るには、次のようなテーブルを簡単に作成できます。

uint32_t r[8][256];

8kb のランダム データを使用して入力します。ランダム データを含む Web サイトをグーグル検索してダウンロードし、再フォーマットして、ソースに含めたり、実行時にファイルからロードしたりできます。

(*) - 入力がランダム データも知っている悪意のある人物によって作成されていない限り。

次に、次のようにハッシュします。

uint32_t hash(uint64_t n)
{
    unsigned char* p = (unsigned char*)&n;
    return r[0][p[0]] ^ r[1][p[1]] ^ r[2][p[2]] ^ r[3][p[3]] ^
           r[4][p[4]] ^ r[5][p[5]] ^ r[6][p[6]] ^ r[7][p[7]];
}

もちろん、最悪の場合の衝突が改善されることは、多くの場合、実際のパフォーマンスが改善されることとは大きく異なります。多くの場合、データ セットとハードウェアに依存します。そのため、本当に気にする場合は、ベンチマークにすぎません。ベンチマークの単純なパススルーも行います。素数のバケットを使用することは非常に良い方法ですが、ハッシュ テーブルによっては注意が必要な場合があります。たとえば、一部の実装ではサイズ変更リクエストが 2 の累乗に丸められる場合があります。

于 2014-08-09T19:47:59.190 に答える