1

重複の可能性:
HashMap#hash(int) メソッドの説明 

   /**
    * Applies a supplemental hash function to a given hashCode, which
    * defends against poor quality hash functions.  This is critical
    * because HashMap uses power-of-two length hash tables, that
    * otherwise encounter collisions for hashCodes that do not differ
    * in lower bits. Note: Null keys always map to hash 0, thus index 0.
    */
   static int hash(int h) {
       // This function ensures that hashCodes that differ only by
       // constant multiples at each bit position have a bounded
       // number of collisions (approximately 8 at default load factor).
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
   }

誰でもこの方法を詳しく説明できますか、ありがとう。

4

2 に答える 2

1

汎用ハッシュコードを設計する際の問題の1つは、ビットの適切な拡散を確保するためにこのすべての努力を注ぐと、誰かがやって来て、それを完全に元に戻すような方法で使用することです。

XとYが両方とも整数である座標クラスの典型的な例を見てみましょう。

これは古典的な例です。これX ^ Yは、X == Y（すべてハッシュが0）であるオブジェクト、またはXとYがYとXであるオブジェクトが複数存在するのが一般的であるため、これは適切なハッシュコードではないことを示すために使用されるためです。他の（同じハッシュになります）および同じハッシュコードになってしまう他の場合。

整数には40億の値をカバーする可能性のある範囲がありますが、99％の使用では、整数はせいぜい数十万または数万未満になる傾向があるという事実に帰着します。40億の可能な結果の中に18quadrillionの可能な値を広めようとすることから逃れることはできませんが、実際に見られる可能性が高く、衝突する可能性が低いものにするために取り組むことができます。

さて、(X << 16 | X >> 16) ^ Yこの場合、Xからのビットをより多くの周りに広げて、より良い仕事をします。

残念ながら、このハッシュを使用% someBinaryRoundNumerしてテーブルにインデックスを付ける場合（または% someOtherNumber、少し程度は少ないですが）、Xの値が以下の場合（someBinaryRoundNumber最も一般的であると予想されます）、このハッシュは効果的になりreturn Yます。

私たちのすべてのハードワークは無駄になりました！

使用される再ハッシュは、そのようなロジックを使用してハッシュを作成することです。

(X << 16 | X >> 16) ^ Yハッシュの別の使用法は、特定の代替案よりも優れた形式になる可能性があるため、このアプローチに批判的すぎることは公平ではないことに注意してください。

于 2012-08-29T10:53:27.307 に答える
0

細かいところまでは入りませんが、次のようにします。

  • hascode（）およびequals（）コントラクトが原因で、ハッシュコード関数の実装が不十分な場合、同じハッシュコードを持つ異なるインスタンスが発生する可能性があります。これは、クラスのequals（）メソッドがAインスタンスとBインスタンスに対してfalseを返すように、安っぽいhashcode（）メソッドを実装したクラスがある可能性があることを意味します（つまり、ビジネスロジックの観点からは異なります）ただし、hashcode（）メソッドはインスタンスAとBに対して同じ値を返します。これも、hashcode（）およびequals（）コントラクトに従って技術的に有効ですが、あまり適切ではありません。

  • ハッシュテーブルのような構造（HashMapなど）では、「バケット」を使用して、ハッシュコードに従ってマップ内にインスタンスを配置します。2つのインスタンスが同じhashcode（）を持っている場合（ただし、equas（）メソッドによって異なります）、両方とも同じバケットに配置されます。このような状況がたくさんあると、ハッシュテーブルのような構造に固有の取得速度の一部が失われるため、これはパフォーマンスの観点からは良くありません。これは衝突と呼ばれます。後で誰かが「検索」インスタンスを使用してハッシュマップから何かを取得し、対応するハッシュバケットに複数の占有者がいる場合、そのバケット内の各要素をequals（）メソッドでチェックして、どれを見つける必要があります。取得する必要があるものです。

  • そのhash（int n）メソッドは、そのような状況から身を守るために、既存のhashcode（）値にいくつかの余分なものを追加します。

于 2012-08-29T10:54:08.937 に答える