18

重複の可能性:
奇妙な Java ハッシュ関数を理解する 

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);   
}

この実装のアルゴリズム原理がよくわかりません。参照できる説明やリソースはありますか？ありがとう ！

アップデート

回答とリソースをありがとう。a bounded number of collisions実際、私はハッシュがどのように機能するかを理解していますが、コメントにあるように、このコードが保証する理由はわかりません。理論的な検証はありますか？

4

3 に答える 3

5

この関数は、での衝突を回避するのに役立ちますHashMap。

適切な実装があれば、オブジェクトのバケットを検出するhashCodeためだけに衝突が発生する可能性があります。hashCode % size

例：

HashMapあなたのサイズがであると仮定します20。

  1. hashCode()forを計算しobject1て取得し401ます。バケットは401 % 20 = 1です。
  2. hashCode()forを計算しobject2て取得し3601ます。バケットは3601 % 20 = 1
  3. hashCode()forを計算しobject3て取得し1601ます。バケットは1601 % 20 = 1です。

したがって、3つの異なるhashCodeがある場合でも、3つのオブジェクトすべてに対して1つのバケットを取得します。これは、O(n)の代わりにHashMapが複雑になることを意味しますO(1)。

hash取得したすべてのハッシュコードに関数を適用すると、次のようになります。

  1. hash = 395、bucket = 395 % 20 = 15
  2. hash = 3820、bucket = 3820 % 20 = 0
  3. hash = 1577、bucket = 1577 % 20 = 17

追加のステップとして適用するhashと、オブジェクトへの一定時間のアクセスを維持する3つの異なるバケットが得られることは明らかです。

于 2012-11-19T10:51:34.593 に答える
5

主な目標は、同様の入力パラメーターに対して非常に異なる値を生成し、衝突の数を最小限に抑えることです。 http://en.wikipedia.org/wiki/Hash_function

この実装は、多くの可能な機能の 1 つの満足できるオプションにすぎません。

于 2012-11-19T10:07:52.347 に答える
3

>>> 演算子はビットシフトですが、符号なしとして扱われます。

^ は XOR (排他的論理和)

だからライン

h ^= (h >>> 20) ^ (h >>> 12);

h をビットシフトした 20 ビットで元の xor、h をシフトした 12 ビットで XOR を意味します。

それから

h ^ (h >>> 7) ^ (h >>> 4);

上記の h、xor h は 7 ビット シフト、xor h は 4 ビット シフト。なぜそのように設定されているのかは100％わかりませんが

于 2012-11-19T10:18:00.407 に答える