14

HashMap が Java でどのように実装されているかを理解しようとしています。そのクラスの (コードとコメントの) すべての行を理解しようと決心しましたが、すぐに抵抗に直面したことは明らかです。次のスニペットは HashMap クラスからのもので、ポアソン分布について説明しています。

 Ideally, under random hashCodes, the frequency of
 nodes in bins follows a Poisson distribution
 (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 parameter of about 0.5 on average for the default resizing
 threshold of 0.75, although with a large variance because of
 resizing granularity. Ignoring variance, the expected
 occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 factorial(k)). The first values are:
 0:    0.60653066
 1:    0.30326533
 2:    0.07581633
 3:    0.01263606
 4:    0.00157952
 5:    0.00015795
 6:    0.00001316
 7:    0.00000094
 8:    0.00000006
 more: less than 1 in ten million

私は数学の平均的な人で、最初にポアソン分布が何であるかを理解しなければなりませんでした。私にそれを説明した簡単なビデオに感謝します。

ポアソンを使用して確率を計算する方法を理解した後でも、上記の内容を理解できません。

誰かがこれをより簡単な言葉で、可能であれば例を挙げて説明できますか? それは私の仕事をもっと面白くするでしょう。

4

2 に答える 2

13

HashMap は、挿入される要素の hashCode に基づいて「バケット」の配列として編成されます。各バケットは (デフォルトでは) 要素のリンクされたリストです。各バケットには非常に少数の要素 (理想的には最大でも 1 つ) が含まれるため、特定の要素を見つけるためにリンクされたリストを下方向に検索する必要はほとんどありません。

簡単な例として、容量 4 の HashMap と 0.75 (デフォルト) の負荷係数があるとします。これは、サイズ変更前に最大 3 つの要素を保持できることを意味します。バケットへの要素の理想的な分散は、次のようになります。

bucket | elements
-------+---------
     0 | Z
     1 | X
     2 |
     3 | Y

そのため、バケット内を検索することなく、あらゆる要素をすぐに見つけることができます。一方、要素の分布が非常に悪い場合は、次のようになります。

bucket | elements
-------+---------
     0 | 
     1 | Z -> X -> Y
     2 |
     3 |

これは、すべての要素がたまたま同じバケットにハッシュされた場合に発生するため、要素 Y を検索するには、リンクされたリストをたどる必要があります。

これは大したことではないように思えるかもしれませんが、10,000 要素の容量を持つ HashMap があり、リンクされたリストの 1 つのバケットに 7,500 要素がある場合、特定の要素の検索は線形検索時間に低下します。 HashMap を使用して回避しようとしているもの。

1 つの問題は、要素をバケットに分散するための hashCode がオブジェクト自体によって決定され、オブジェクトの hashCode 実装が常に適切であるとは限らないことです。hashCode があまり良くない場合、要素が特定のバケットに集まり、HashMap のパフォーマンスが低下し始めます。

コードからのコメントは、各バケットに異なる長さのリンクされたリストが表示される可能性について語っています。まず、hashCode がランダムに分散されていることを前提としていますが、常にそうであるとは限りません。-- また、HashMap の要素数がバケット数の 50% であることも想定していると思います。これらの仮定の下では、そのポアソン分布に従って、バケットの 60.6% が空になり、30.3% が 1 つの要素を持ち、7.5% が 2 つの要素を持ち、1.2% が 3 つの要素を持つ、というようになります。

言い換えれば、これらの (理想的な) 仮定が与えられた場合、通常、各バケット内のリンクされたリストは非常に短くなります。

JDK 8 には、リンクされたリストを特定のしきい値サイズを超えるツリーに変換する最適化があり、最悪の場合、少なくともパフォーマンスが O(n) ではなく O(log n) に低下します。問題は、しきい値としてどの値を選択する必要があるかです。それがこの議論のすべてです。現在のしきい値 TREEIFY_THRESHOLD は 8 です。繰り返しますが、これらの理想的な仮定の下では、長さ 8 のリンク リストを持つバケットは 0.000006% の時間しか発生しません。したがって、リンクされたリストが長くなると、明らかに理想的ではありません!! たとえば、格納されているオブジェクトの hashCode が非常に悪いことを意味する場合があるため、過度のパフォーマンスの低下を避けるために、HashMap をリンク リストからツリーに切り替える必要があります。

問題のコメントを含むソース ファイルへのリンクは次のとおりです。

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/jdk8-b119/src/share/classes/java/util/HashMap.java

于 2013-12-10T03:18:59.780 に答える
2

受け入れられた答えは素晴らしいですが、そのコードを読んだときにまったく同じ質問があったため、特にポアソン分布を使用することが合理的である理由を記入したかっただけです。

固定数のバケットに固定数のアイテムkを挿入する場合、固定バケット内のアイテム数は、試行と成功確率を伴う 二項分布nに従う必要があります。これは非常に簡単に確認できます。ハッシュがランダムな場合、各アイテムは確率でバケットに入れられ、アイテムがあります。k1 / n1 / nk

がk大きく、二項分布の平均が小さい場合、適切な近似は同じ平均のポアソン分布です。この場合、平均値はk / n、ハッシュ テーブルの負荷係数です。テーブルはサイズ変更前に最大 0.75 の負荷係数を許容し、約 0.5 の負荷係数でテーブルが大量に使用されるため、平均に 0.5 を使用することは合理的です。

于 2016-09-29T16:55:58.247 に答える