HashMapコレクションの性能改善@Java8

Java8標準ライブラリのjava.util.HashMap<K,V>クラスでは、ハッシュ衝突時のパフォーマンス劣化を避けるために キー型K が Comparable インタフェースを実装することが望ましい。ただし、同インタフェースを実装しなくとも正常に動作する*1。

HashMapのインスタンスに多くのマッピングが格納される場合は、この表の作成時に十分な大きさの容量を設定すると、必要に応じてハッシュを自動的にやり直して表を大きくするよりも、マッピングをより効率的に格納できます。同じhashCode()で多数のキーを使用すると、必ずいずれかのハッシュ表のパフォーマンスが低下することに注意してください。影響を軽減するため、キーがComparableである場合は、このクラスでキー間の比較順序を使用してキーの重複を解消できます。

https://docs.oracle.com/javase/jp/8/docs/api/java/util/HashMap.html

HashMapコレクション内部実装ではハッシュ衝突時はチェイン法を採用しており、Java7以前では単純線形リストによる O(n) 探索が行われる。JEP 180 にて赤黒木(Red-Black tree)実装による O(log n) 探索が提案され、Java8から標準ライブラリに採用された。（いずれもハッシュ衝突時の最悪計算量であることに注意）

関連URL

• JEP 180: Handle Frequent HashMap Collisions with Balanced Trees
• Java8からはHashMapの性能のためにComparableを実装しておいた方がいい - interprism's blog
• http://codehiker42.net/how-does-java-hashmap-work/
• How does a HashMap work in JAVA | Coding Geek

*1:当然ながら、キー型 K に Comparable<K> を実装する場合は、同インタフェースの一般契約を満たさないと HashMap コレクションとして正常動作しなくなる。JPCERT MET10-Jも参照。