0

私は Java の HashMap hash() 実装を行っていました。以下のようなものです。

final int hash(Object k) {
            // some checks
            h ^= k.hashCode();
            // 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);
                   // >>> is Unsigned right shift
    }

以下のコードが追加された理由がわかりませんが、同じことによってどのような利点が得られるのでしょうか?

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);

または、上記のコードを実装から削除した場合、質問を再構成させてください。欠点は何ですか? 衝突の可能性を回避する方法をいくつか理解していますが、「正確に」どのように回避しているのかわかりませんか?

例を挙げて理解を助け、上記のコードの有無にかかわらずどのように機能するかを説明できますか?

4

1 に答える 1

5

Javaハッシュテーブルの実装では、テーブルのサイズがプライムサイズではなく、2の累乗になります。これにより、高価な剰余演算の代わりに高速ビットマスキングを使用できます。これは一般的には良いことですが、特に悪いハッシュ関数では通常よりも多くの衝突が発生する可能性があるという欠点があります。引用するコードは、余分な衝突を最小限に抑える方法でハッシュのビットを混合します。

于 2013-03-19T03:09:31.930 に答える