大量の値のセットを生成して値の分布を確認する以外に、ハッシュ関数の効率を評価する方法を知っていますか? 効率とは、ハッシュ関数によって生成されたキーが均等に分散されることを意味します。実際の値を実際にテストせずにこれを証明する方法はありますか?
質問する
1544 次
1 に答える
4
ハッシュ関数は、ハッシュされるデータのコンテキストでのみ偶数です
次の 2 つのデータセットを検討してください。
セット 1
1, 3, 6, 2, 7, 9, 5, 8, 4
セット 2
65355, 96424664, 86463624, 133, 643564, 24232, 88677, 865747, 2224
1 つのセットの適切なハッシュ関数 (つまり、セット 1 の mod 10) は衝突を起こさず、そのデータ セットの完全なハッシュと見なすことができます。
ただし、それを 2 番目のセットに適用すると、いたるところで衝突が発生します
Hash = (x * 37) mod 256
2番目のセットにははるかに適していますが、最初のセットにはあまり適していない可能性があります...特に、少数のバケットのハッシュを分割する場合.
あなたができることは、関数が処理しなければならないことが「期待される」ランダムなデータに対してハッシュを評価することです...しかし、それは仮定をしています...
時期尚早の最適化は、評価の基礎となる実際のデータが十分に得られる前に、完全なハッシュ関数を探します。
ハッシュ関数を変更するには、再ハッシュのコストが法外に高くなる前に、十分なデータを取得する必要があります
アップデート
入力データの 8 ビット ハッシュを生成するハッシュ関数を探しているとします。さらに、ハッシュ関数がさまざまな長さのバイトストリームを受け取ると想定しているとします。
バイトストリーム内のバイトが均一に分散されていると仮定すると、さまざまなハッシュ関数を評価できます。
int hash = 0;
for (byte b in datastream) hash = hash xor b;
この関数は、指定されたデータ セットに対して一様に分散されたハッシュ値を生成するため、このコンテキストでは適切なハッシュ関数になります。この理由がわからない場合は、他の問題が発生している可能性があります。
int hash = 37;
for (byte b in datastream hash = (31 * hash + b) mod 256;
この関数は、指定されたデータ セットに対して一様に分散されたハッシュ値を生成するため、このコンテキストでは適切なハッシュ関数になります。
ここで、データ セットを 0 ～ 255 の範囲の乱数の可変長文字列から、US-ASCII としてエンコードされた英語の文を含む可変長文字列に変更します。
入力データには 8 番目のビットが設定されず、結果として 0 ～ 127 の範囲のハッシュしか生成されないため、XOR は不十分なハッシュです。また、英語の文字頻度のために、いくつかの「ホット」な値の可能性が高くなります。言葉と XOR のキャンセル効果。
素数のペアは、出力範囲全体を使用し、素数の初期オフセットが異なる素数の乗数と組み合わされて値が分散する傾向があるため、ハッシュ関数として妥当なままです。しかし、英語がどのように構造化されているかにより、衝突にはまだ弱いです... 実際のデータでテストするだけで何かを示すことができます.
于 2012-09-30T15:33:30.700 に答える