13

ここ数時間、ハッシュコード関数について読んでいて、カスタム ハッシュコードの実装での乗数としての素数の使用に関するいくつかの質問を蓄積しました。以下の質問について、少しでも理解を深めていただければ幸いです。

  • ここでの @mattb の回答へのコメントで、@hstoerrは一般的な素数 31 の代わりに、より大きな素数 (524287 など) の使用を提唱しています。私の質問は、ペアまたは要素のハッシュコード関数の次の実装を考えると、

    @Override
public int hashCode() {
    final int prime = 31;
    int hash1 = (pg1 == null) ? 0 : pg1.hashCode();
    int hash2 = (pg2 == null) ? 0 : pg2.hashCode();
    return prime * (hash1 ^ hash2);
}

intこれは、返されたifprimeが大きな数である場合にオーバーフローを引き起こしませんか?

  • オーバーフローが問題ではないと仮定すると (JVM は自動キャストを実行します)、キャストの代わりにビットシフトを実行する方がよいでしょうか?

  • ハッシュコード関数のパフォーマンスは、ハッシュコードの複雑さによって大きく異なると思います。素数乗数のサイズはパフォーマンスに影響しませんか?

  • 単一の乗数ではなく、カスタム ハッシュコード関数で複数の素数を使用する方が良い/スマート/高速ですか? そうでない場合、他の利点はありますか？関連する質問に対する @jinguy の回答から以下の例を参照してください。

    public int hashCode() {
    return a * 13 + b.hashCode() * 23 + (c? 31: 7);
}

はa、はint、はです。bStringcboolean

  • のようなものlong lhash = prime * (hash1 ^ hash2);はどう(int)((lhash >> 32) ^ lhash)ですか？それは私が別の質問で見たものですSOですが、なぜそのようにするのが良い考えなのかは実際には説明されていませんでした.
4

2 に答える 2

9

小説の前に謝罪。自由に提案したり、直接編集したりしてください。--チェット

オーバーフローがありますが、例外ではありません。

危険は精度を失うことではなく、射程距離を失うことから来ます。「素数」が 2 の大きなべき乗であり、簡潔にするために 8 ビットの符号なし数値である、ばかげた例を使用してみましょう。(hash1 ^ hash2)そして、それが 255であると仮定します。

        "prime": 1000 0000
(hash1 ^ hash2): 1111 1111

角かっこで切り捨てられた数字を示すと、結果は次のようになります。

        product: [0111 1111] 1000 0000

ただし、128 を掛けることは、左に 7 桁シフトすることと同じです。(hash1 ^ hash2)したがって、 の値が何であれ、積の最下位の場所には 7 つのゼロがあることがわかります。したがって、(hash1 ^ hash2)が奇数 (最下位ビット = 1) の場合、128 を掛けた結果は常に 128 になります (上位桁を切り捨てた後)。が偶数の場合(hash1 ^ hash2)(LSB が 0 の場合、積は常にゼロになります。

これは、より大きなビットサイズに拡張されます。一般的なポイントは、「prime」の下位ビットがゼロの場合、下位ビットにゼロを与えるシフト（または複数シフト+合計）操作を行っているということです。そして、乗算の積の範囲が損なわれます。

primeしかし、最下位ビットが常に 1 になるように" " を奇数にしてみましょう。これをシフト / 加算操作に分解することを考えてください。のシフトされていない値は、(hash1 ^ hash2)常に被加数の 1 つになります。偶数 " prime" 乗数によって保証された無用にシフトされた最下位ビットは、少なくとも元の値のビットに基づいて設定され(hash1 ^ hash2)ます。

primeさて、実際に素数である値を考えてみましょう。2 より大きい場合は、奇数であることがわかります。したがって、下位ビットは無駄にシフトされていません。また、十分に大きな素数を選択することで、小さい素数を使用する場合よりも、出力値の範囲全体でより適切な分布が得られます。

0010 0000 1111 10118443 ( ) と 59 ( )を使用した 16 ビット乗算の演習を試してください0000 0000 0011 1011。それらは両方とも素数であり、59 の下位ビットは 65531 の下位ビットと一致します。たとえば、hash1 と hash2 が両方とも ASCII 文字値 (0 .. 255) の場合、(hash1 ^ hash2) * のすべての結果59 は <= 15045 になります。これは、16 ビットの数値のハッシュ値の範囲 (0..65535) の約 1/4 が使用されないことを意味します。

しかし(hash1 ^ hash2) * 8443、マップ全体にあります。が 8 のように小さい場合はオーバーフロー(hash1 ^ hash2)します。非常に小さい入力数値でも 16 ビットすべてを使用します。入力数値が比較的小さい範囲にある場合でも、範囲全体でハッシュ値のクラスター化ははるかに少なくなります。

オーバーフローが問題ではないと仮定すると (JVM は自動キャストを実行します)、キャストの代わりにビットシフトを実行する方がよいでしょうか?

ほとんどの場合、そうではありません。とにかく、JVM はホスト プロセッサ上で効率的な実装に変換する必要があります。整数乗算はハードウェアに実装する必要があります。そうでない場合、JVM は操作を CPU にとって妥当なものに変換する責任があります。整数乗算の場合は、すでに高度に最適化されている可能性が非常に高いです。特定の CPU で整数乗算がシフトアンド加算としてより高速に実行される場合、JVM はそれをそのように実装する必要があります。しかし、JVM を作成している人々が、複数のシフトと加算の操作が 1 つの整数乗算に結合された可能性があるケースに気を配る可能性は低いでしょう。

ハッシュコード関数のパフォーマンスは、ハッシュコードの複雑さによって大きく異なると思います。素数乗数のサイズはパフォーマンスに影響しませんか?

いいえ。ハードウェアで実行する場合、サイズや設定されたビット数などに関係なく、操作は同じです。おそらく数クロック サイクルです。特定の CPU によって異なりますが、入力値に関係なく一定時間の操作になるはずです。

単一の乗数ではなく、カスタム ハッシュコード関数で複数の素数を使用する方が良い/スマート/高速ですか? そうでない場合、他の利点はありますか？

衝突の可能性を減らす場合にのみ、これは使用している数値によって異なります。ハッシュ コードが と に依存してAおりB、それらが同じ範囲にある場合は、異なる素数を使用するか、入力値の 1 つをシフトして、ビット間のオーバーラップを減らすことを検討してください。値に直接依存するのではなく、個々のハッシュ コードに依存しているため、ハッシュ コードが適切な分散などを提供すると想定するのが合理的です。

のハッシュコード(x, y)を(y, x). ハッシュ関数がAとBを同じように扱う場合、 hash(x, y) = hash(y, x). それが必要な場合は、必ず同じ乗数を使用してください。そうではありません。別の乗数を使用することは理にかなっています。

のようなものlong lhash = prime * (hash1 ^ hash2);はどう(int)((lhash >> 32) ^ lhash)ですか？それは私が別の質問で見たものですSOですが、なぜそのようにするのが良い考えなのかは実際には説明されていませんでした.

興味深い質問です。Java では、long は 64 ビットで、int は 32 ビットです。したがって、これは必要なビット数の 2 倍を使用してハッシュを生成し、上位ビットと下位ビットを組み合わせて結果を導き出します。

n数値を素数で乗算しp、 の最下位kビットnがすべてゼロの場合k、積の最下位ビットn * pもすべてゼロになります。これは非常に簡単にわかります。たとえば、n = 0011 0000と を乗算している場合p = 0011 1011、積は 2 つのシフト操作の和として表すことができます。または、

00110000 * p = 00100000 * p + 00010000 * p
             = p << 5 + p << 4

p = 59unsigned 8 ビット int と 16 ビット long を取得して使用する例を次に示します。

 64: 0011 1011 * 0100 0000 = [ 0000 1110 ] 1100 0000 (192)
128: 0011 1011 * 1000 0000 = [ 0001 1101 ] 1000 0000 (128)
192: 0011 1011 * 1100 0000 = [ 0010 1100 ] 0100 0000 (64)

結果の上位ビットを削除するだけで、非素数被乗数の下位ビットがすべてゼロの場合、結果のハッシュ値の範囲が制限されます。それが特定のコンテキストの問題であるかどうかは、コンテキスト固有です。ただし、一般的なハッシュ関数の場合、入力数値にパターンがある場合でも、出力値の範囲を制限しないようにすることをお勧めします。また、セキュリティ アプリケーションでは、出力のパターンに基づいて元の値を推測できるようなものを避けることがさらに重要です。下位ビットを取得するだけで、元のビットの一部の正確な値が明らかになります。入力数値に大きな素数を乗算する操作が含まれていると仮定すると、元の数値にはハッシュ出力と同じ数のゼロが右側にあることがわかります (素数'

上位ビットと下位ビットを XOR することにより、出力の一貫性が低下します。さらに重要なことに、この情報に基づいて入力値を推測することははるかに困難です。XOR の仕組みに基づいて、元の下位ビットが 0 で上位ビットが 1 であったか、元の下位ビットが 1 で上位ビットが 0 であったことを意味する可能性があります。

 64: 0011 1011 * 0100 0000 = 0000 1110 1100 0000 => 1100 1110 (206)
128: 0011 1011 * 1000 0000 = 0001 1101 1000 0000 => 1001 1101 (157)
192: 0011 1011 * 1100 0000 = 0010 1100 0100 0000 => 0110 1100 (204)
于 2012-08-22T18:44:18.100 に答える
4

  • オーバーフローは問題ではありません。とにかく、ハッシュは狭い値セットに制限されます。

  • あなたが投稿した最初のハッシュ関数はあまり良くありません。代わりreturn (prime * hash1) ^ hash2; に`を実行すると、ほとんどの場合、衝突の数が減ります。

  • 単一の単語intによる乗算は一般に非常に高速であり、異なる数値による乗算の違いはごくわずかです。さらに、実行時間は、関数内の他のすべてのものによって小さくなります。

  • パーツごとに異なるプライムマルチプライヤを使用すると、衝突のリスクを減らすことができます。

于 2012-08-22T15:55:46.383 に答える