わりと多種類で使い方に迷うJavaの連想配列（Map）について、各実装の紹介と周辺知識をまとめました。Javaに触れる際の参考になれば。
鉄則その1「とりあえずHashMap」
Mapインタフェースの実装はたくさんありますが、まずはHashMapから使うことを勧めます。HashMapはハッシュテーブルというシンプルなアルゴリズムにもとづく実装であり、理論上はデータ量に関係なく一定の時間で挿入・参照・削除を行えることになっています*1。ヒープの消費が特にひどいということもありません。
鉄則その2「hashCode,equals,compareToを正しく実装」
キーとして使用するインスタンスはhashCodeメソッドやequalsメソッドを正しく実装しなければならないことに注意してください。正しく実装されないと「データ量に関わらず少ない時間で操作できる」という優位性を損なったり、そもそも期待する動作をしなかったりと危険です。またSortedMapの実装を使用する場合は、キーのcompareToメソッドを正しく実装するか、Comparatorを正しく実装する必要があります。
何が「正しい実装」かよくわからない場合は、IDEの自動コード生成を頼りつつ詳しい人に聞くといいでしょう。
キー順にソートされた状態を保つSortedMap
MapのサブインタフェースであるSortedMapを使うことで、最大/最小のキーを持つ要素の取得や範囲検索が可能になります。用意されている実装クラスには、赤黒木を基にしたTreeMapがあります。
「順番」を保持できるLinkedHashMap
LinkedHashMapはすべてのエントリが双方向リンクリストとして繋がっているのが特徴です。リンクの順番はコンストラクタによって「追加順」「アクセス順」の2パターンを利用できます。
単に「追加順・アクセス順に要素を並べたい」だけならばLinkedListでも可能ですが、LinkedHashMapならキーで要素を特定できるので、キャッシュとしての利用に特に向いています。
その他細かいこと
- Hashtable（とVector）は昔から存在するクラスにコレクションインタフェースを実装させた「レガシー実装」です。今採用するならば、コレクションインタフェースを前提として用意された他のクラスにすべきです。機能上のデメリットとしては、多くのメソッドがsynchronizedで修飾されている＝低速であることが挙げられます。
- Collectionsクラスに用意されているユーティリティメソッドをおさえておきましょう。特にunmodifiableMapメソッドはMapを返すgetterで重宝します。synchronizedMapは一見便利ですが、Mapの外で同期処理する方が好ましい場合が多いでしょう。
- HashMapやLinkedHashMapでは、性能を決定づける値として「初期容量」と「負荷係数」が存在します。が、エントリ数が極端に大きい場合を除き、デフォルトで問題ないでしょう。エントリが極端に増えるということがあらかじめ分かっている場合は、初期容量を増やすことで高速化を実現できるかもしれません。
*1:実際hashCodeメソッドの実装が理想的であれば、ほぼ一定の時間で動作します
