JavaにおけるHashMapとTreeMapの違いを徹底解説

Javaのコレクションフレームワークにおいて、Mapインターフェースを実装する代表的なクラスとして「HashMap」と「TreeMap」があります。どちらもキーと値のペアを管理するためのクラスですが、内部構造やパフォーマンス、機能面で大きな違いがあります。本記事では、それぞれの特徴を詳しく解説し、適切な使い分けのポイントを紹介します。

HashMapとは

HashMapは、ハッシュテーブルを基盤としたMap実装です。高速なデータアクセスが特徴で、要素の順序を保持しないシンプルなマップです。

主な特徴

• 内部構造: ハッシュテーブルを使用し、Mapインターフェースに基づいて実装されています。
• 実装インターフェース: Map、Cloneable、Serializableを実装しています。
• nullの扱い: nullキーを1つだけ許容し、null値は複数持つことができます。
• パフォーマンス: TreeMapと比較して高速です。get()やput()などの基本操作が平均定数時間O(1)で実行できます。
• ソート: キーの並び替えは行われません。そのため、異なる型の要素をキーとして格納できます。
• 順序の保持: 要素の挿入順序やソート順は保持されません。
• キーの比較: Objectクラスのequals()メソッドを使用してキーの同一性を判定します。
• 提供メソッド: keySet()、get()、put()など、基本的なメソッドが中心です。

適した用途

キーと値のペアをソート順で管理する必要がない場合に最適です。検索速度を重視する場面で広く利用されます。

TreeMapとは

TreeMapは、木構造(赤黒木)を基盤としたMap実装です。キーが常にソートされた状態で保持される点が最大の特徴です。

主な特徴

• 内部構造: ツリー構造を使用し、Mapインターフェースに基づいて実装されています。
• 実装インターフェース: NavigableMap、Cloneable、Serializableを実装しています。
• nullの扱い: nullキーは許容されません(nullキーを追加するとNullPointerExceptionが発生します)。一方、null値は複数持つことができます。
• キーの型: ソートを行うため、キーは同種の型(相互に比較可能な型)である必要があります。
• パフォーマンス: HashMapより低速です。add()、remove()、contains()などのほとんどの操作がO(log n)の計算量となります。
• 内部実装: 赤黒木(Red-Black Tree)を使用しています。赤黒木は自己平衡型二分探索木の一種で、木のバランスが自動的に保たれます。
• キーの比較: compareTo()メソッドを使用してキーを比較します。
• 豊富なナビゲーション機能: tailMap()、firstKey()、lastKey()、pollFirstEntry()、pollLastEntry()など、順序に関連した便利なメソッドが多数用意されています。
• ソート: 要素は昇順(自然順序)で自動的にソートされます。

適した用途

キーと値のペアをソートされた順序で管理したい場合に最適です。範囲検索や最小値・最大値の取得を頻繁に行う场景で活躍します。

HashMapとTreeMapの比較表

両者の違いを一覧表にまとめると以下のようになります。

使い分けのポイント

選択の基準はシンプルです。「速度重視ならHashMap」「順序が必要ならTreeMap」です。

• 要素の順序が不要で、最高の検索・挿入性能を求める場合はHashMapを選びましょう。
• キーを常にソートされた状態で保持したい、範囲検索や順序付き走査を行いたい場合はTreeMapを選びましょう。
• 挿入順序を保持したいだけであれば、LinkedHashMapという第三の選択肢もあります。

それぞれの特性を正しく理解し、用途に応じて最適なMap実装を選択することが、効率的で保守性の高いJavaプログラムを作成する鍵となります。