Java 8のハッシュマップでリンクリストの代わりにバイナリツリーを使用するのはなぜですか？

Question

私は最近、Java 8のハッシュマップでは、リンクされたリストの代わりにバイナリツリーを使用し、ハッシュコードが分岐ファクタとして使用されていることがわかりました。高い衝突の場合、参照はO（ログn） （n）のバイナリツリーを使用しています。私の質問は、償却された時間の複雑さが依然としてO（1）であることと、同じバケットにすべてのエントリを格納するように強制すると、私たちは大きな時間差を見ることができますが、正しい心の誰もそれをすることはありません。

バイナリツリーは、左右のノードを両方とも格納するため、単一リンクリストより多くの領域も使用します。何らかの偽のテストケースを除いて、時間の複雑さが全く改善されていない場合は、

Answer 1

これはほとんどのセキュリティ関連の変更です。通常の状況では、ハッシュキーが信頼できない送信元（クライアントから受信したHTTPヘッダー名など）から到着した場合、多くのコリジョンが発生することはほとんどありませんが、入力を特別に細工することは難しくありません。同じハッシュコード。多くのルックアップを実行すると、サービス拒否が発生する可能性があります。野生にはこの種の攻撃に対して脆弱なコードがたくさんあるようだから、これをJava側で修正することに決めました。

詳細については、JEP-180を参照してください。

Answer 2

ご質問に間違った施設が含まれています。

1. バケット衝突は必ずしもハッシュ衝突ではありません。 2つのオブジェクトが同じバケットに終わるために同じハッシュコードを持つ必要はありません。バケットは配列の要素であり、ハッシュコードは特定のインデックスにマップされなければなりません。配列のサイズはMapのサイズに対して妥当でなければならないので、バケットの衝突を避けるために配列のサイズを任意に大きくすることはできません。理論的な制限として、配列のサイズは最大2 1であり、可能なハッシュコードは2 32です。
2. ハッシュコリジョンを持つことは、不正なプログラミングの兆候ではありません。値のスペースが232より大きいすべてのオブジェクトでは、同じハッシュコードを持つ別個のオブジェクトの可能性は避けられません。 Stringは明白な例ですが、2つのint値を持つPointでも、またはLongの平文キーでも、やむを得ないハッシュコリジョンが発生します。だからあなたが思うよりももっと一般的かもしれませんし、ユースケースに大きく依存しています。
3. 実装は、バケット内の衝突の数が特定のしきい値を超えた場合にのみ、バイナリツリーに切り替えるので、より高いメモリコストは支払う際にのみ適用されます。彼らがどのように働いているかについての共通の誤解があるようです。バケットの衝突は必ずしもハッシュの衝突ではないので、バイナリ検索はまずハッシュコードを検索します。ハッシュコードが同一で、キーが適切に実装されている場合にのみ、その自然順序が使用されます。 Web上で見つかった例では、オブジェクトに同じハッシュコードを使用して、別の方法では表示されないComparable実装の使用方法をデモンストレーションします。彼らが引き起こすのは、実装の最後の手段です。
4. Tagir pointed outとして、この問題は、遅いフォールバックがDoS攻撃の可能性を開く可能性があるため、ソフトウェアのセキュリティに影響する可能性があります。以前のJREバージョンでは、バイナリツリーのメモリ消費よりも多くの欠点を持つこの問題に対処するいくつかの試みがありました。たとえば、Java 7の配列エントリにハッシュコードのマッピングをランダム化して、this bug reportに記載されているような初期化オーバーヘッドを発生させる試みがありました。この新しい実装では、これは当てはまりません。