JavaのHashMapの衝突の解決

Question

私はstackoverflowと他のウェブサイトで読んだことから。 Javaは、ハッシュ衝突解決のためにリンクされたリストを使用します。

これは、挿入、取得、削除の最悪のシナリオではO（n）の複雑さを保証します。

なぜ、Javaは、挿入、取得、削除の最悪のシナリオでO（ログn）の複雑さを保証するためにセルフ・バランシングBST（AVL、レッド・ブラックなど...）を使用しないのですか？

Answer 1

ほとんどの場合、バケツには非常に少数のアイテムが存在します。しばしば0または1である。これらの場合、単純なハッシュバケット構造はO（1）を保証することができます。 O（log n）BSTは、いくつかの準最適なエッジのケースでは時間をカットするかもしれませんが、パフォーマンスの利得は最高で無視でき、最悪では負です。また、メモリオーバーヘッドが大きくなります。 Java 8は、リンクされたリストが最適ではなくなったときを検出し、BSTに変換するための努力をしています。ただし、この動作が頻繁に発生する場合は、ハッシュとHashMapが間違って使用されているという兆候です。

JDKのソースコードを読むときに、多くの実装の詳細があります。ここでは、Oracleのjava.util.HashMapを上から簡単に抜粋だ：

のHashMap＃getNodeとHashMap.Nodeの実装を見てみると

/* 
* Implementation notes. 
* 
* This map usually acts as a binned (bucketed) hash table, but 
* when bins get too large, they are transformed into bins of 
* TreeNodes, each structured similarly to those in 
* java.util.TreeMap. Most methods try to use normal bins, but 
* relay to TreeNode methods when applicable (simply by checking 
* instanceof a node). Bins of TreeNodes may be traversed and 
* used like any others, but additionally support faster lookup 
* when overpopulated. However, since the vast majority of bins in 
* normal use are not overpopulated, checking for existence of 
* tree bins may be delayed in the course of table methods. 
* [...] 

、私たちは、各バケットは非常に単純なリンクlist--として開始していることがわかります実際には二重リンクされたリストであるjava.util.LinkedListよりも簡単です。

コメントごとに、リストが特定のサイズに拡大すると、ツリーに変換されます。 HashMap.TreeNodeで何が起こっているのかを正確に伝えるのは難しいです。なぜなら、コードはまったく自己記述的ではないからですが、単純な赤黒のBSTのようです。

Answer 2

Java 8 は、リンクチェーンが十分に大きくなる場合。

少数の要素では、メモリとパフォーマンスのオーバーヘッドが大幅に増加します。リンクされたリストは非常に少数の要素に対して非常に効率的です。これはまさに99％の状況でハッシュバケットに期待されるものです。さらに、バイナリツリーのソート方法を明確に定義することは不可解であり、要素がComparableの場合は、使用されていないハッシュコードビットでソートして特殊ケースを作成する必要があります。