6

これは一種の学術的なポイントですが、Effective Javaや多くのSOの質問などの本でハッシュコードが推奨されている理由がわからないと、ハッシュコードを完全に理解できないと感じます。

仮定する：

public sealed class Point
{
    private readonly int x;
    private readonly int y;

    //constructor ommited

    //equals ommited
    
    public override int GetHashcode()
    {
       int hash = 17; //why should the initial value be non-zero?
       unchecked
       {
         hash = hash * 31 + x; //do not tell me why I should use primes - that is not the question
         hash = hash * 31 + y;
         return hash;
       }
    }
}

さて、おそらく、初期値の理由は、コンポーネントの1つがゼロである場合の衝突を減らすためです。

これが役立つ例を見つけるのに苦労しています。

これは衝突の一例ですが、初期値を持っていてもオッズはありません。

x   y   Hash Without initial value     Hash With initial value  
0   31  31                             16368                
1   0   31                             16368

理想的には、初期値が衝突を防ぐ具体的な例を探しています。

初期値が決して違いを生まない理由についての私の理論

//Given a prime p, initial value i, fields a,b,c, calculate hash h
h = i;
h = h*p + a;
h = h*p + b;
h = h*p + c;

したがって：

h = ((i*p + a)*p + b)*p + c
  = (ipp + ap + b   )*p + c
  = ippp + app + bp + c

したがって、初期値iは、定数値（この場合はi*p3 ）を生成することにより、すべてのハッシュコードに同じように影響します。

4

4 に答える 4

2

初期値は素数でなければなりません。なんで？長さ=20の配列のインデックスを取得するためにハッシュしているとすると、[object.getHash（）％20]は、オブジェクトを格納する配列のインデックスです。偶数を使用した場合：データ構造のアドレスの半分は使用されません...これが初期値を使用する必要がある理由です：衝突を最小限に抑え、データ構造の使用を最大化する

于 2012-11-19T15:31:00.427 に答える
1

素数の使用は、ハッシュ関数に適した特性を持つ実験とテストによって示されています。また、既存のライブラリなどに
見られるハードコードされた番号は、テスト中に適切なオプションであることがわかりました。私の知る限り、これらの「魔法の」数字の選択の背後にある証拠はありません。それらはフィールドテストの後にのみ選択されました。 31Java

更新：
初期値としてゼロを使用すると、ハッシュはメンバー変数の影響も受けます。
たとえばhash = hash * 31 + x;、の0場合xは0であり、初期値も0です。
次に、アプリケーションドメインで非常に一般的であるy可能0性のある数値、または衝突が発生する可能性のある数値になります。

于 2012-11-19T15:45:06.447 に答える
0

初期値は、異なるクラスのオブジェクトを区別するのに役立ちます。

上に示したハッシュ関数はあまり良くないため、プロパティ値が異なるオブジェクトの衝突が非常に簡単に発生します。ハッシュ関数の考え方は、パブリックプロパティに応じて、一意の、またはほぼ一意の値になるということです。

したがって、可能な限り一意の値を取得するには、次のようにします。

  • 優れた分布をもたらす優れたハッシュ関数を使用する
  • PointaとLine同じハッシュを返す可能性が低くなるように、さらに区別する適切な初期値を使用します。
于 2012-11-19T15:31:36.100 に答える
0

初期値の選択がハッシュに違いをもたらすことは決してありません。

例：

//Given a prime p, initial value i, fields a,b,c, calculate hash h
h = i;
h = h*p + a;
h = h*p + b;
h = h*p + c;
h = h % 2^32;

したがって：

h = (((ip  + a) * p + b) * p + c) % 2^32
  = (( ip² + ap     + b) * p + c) % 2^32
  = (  ip³ + ap²    + bp     + c) % 2^32
  = ip³ % 2^32 + (ap² + bp + c) % 2^32

したがって、初期値iは、この場合はハッシュに定数値を追加することにより、すべてのハッシュコードに同じように影響しますi*p³ % 2^32。

于 2020-12-18T15:26:20.083 に答える