7

JDK のソース コードを読んだ後、HashMap のhash()機能が楽しいように思えます。このようなソースコード：

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

パラメータhは、そこからに入れられたhashCodeです。この方法はどのように機能し、その理由は何ですか? なぜこのメソッドは貧弱なhashCode関数を防御できるのでしょうか?ObjectsHashMap

4

1 に答える 1

14

Hashtable は、素数の「古典的な」アプローチを使用します。値の「インデックス」を取得するには、キーのハッシュを取得し、サイズに対してモジュラスを実行します。素数をサイズとして取ると、(通常) インデックス全体に適切な広がりが得られます (もちろん、ハッシュにも依存します)。

HashMap は「2 のべき乗」アプローチを使用します。つまり、サイズは 2 のべき乗です。その理由は、素数の計算よりも高速であるはずだからです。ただし、2 の累乗は素数ではないため、特にハッシュ値の下位ビットが同じ場合は、より多くの衝突が発生します。

なんで？(バケット/スロット) インデックスを取得するためにサイズに対して実行されるモジュラスは、次のように単純に計算されます: hash & (size-1) (これはまさにインデックスを取得するために HashMap で使用されるものです!)。これは基本的に「2 の累乗」アプローチの問題です。長さが制限されている場合、たとえば HashMap のデフォルト値である 16 の場合、最後のビットのみが使用されるため、下位ビットが同じハッシュ値は次のようになります。同じ (バケット) インデックス。16 の場合、インデックスの計算には最後の 4 ビットのみが使用されます。

そのため、追加のハッシュが計算され、基本的に上位ビット値がシフトされ、下位ビット値で操作されます。20、12、7、4 という数字の理由はよくわかりません。それらは異なっていました (Java 1.5 かそこらでは、ハッシュ関数はほとんど異なっていませんでした)。もっと高度な文献があると思います。あらゆる種類のアルゴリズム関連の文献で、彼らが使用する数値を使用する理由についての詳細を見つけることができます。

http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming

http://mitpress.mit.edu/books/introduction-algorithms

http://burtleburtle.net/bob/hash/evahash.html#lookupでは、長さに応じて異なるアルゴリズムが使用されます (これには意味があります)。

http://www.javaspecialists.eu/archive/Issue054.htmlもおそらく興味深いものです。記事の下部にある Joshua Bloch の反応を確認してください。 、数値はジョシュ自身によって実行された何らかの分析から得られたものであり、おそらく誰が誰を知っているかによって支援されています.

したがって、2 のべき乗は計算を高速化しますが、スロット/バケット全体に分散させるために追加のハッシュ計算が必要になります。

于 2013-01-23T12:38:24.293 に答える