Java HashMap・LinkedHashMap・TreeMapの違い

HashMap・LinkedHashMap・TreeMapの違いとは、取り出すときの「順序」の違いです。HashMapは順序を決めず、LinkedHashMapは入れた順、TreeMapはキーの昇順で並びます。 追加・検索・削除といった基本の使い方は3つとも同じで、new するクラスを替えるだけで順序の性質が切り替わります。

この記事では、同じデータを3種類のMapに入れた実行結果を並べたうえで、計算量・null の可否・用途を早見表にまとめます。さらに TreeMap だけが持つ範囲検索（floorKey・headMap など）、LinkedHashMap で作る LRU キャッシュ、Java 21 で加わった SequencedMap まで、すべて動かした結果つきで紹介します。

確認環境：Ubuntu 24.04 / OpenJDK 21.0.10。掲載コードはすべて java ファイル名.java で実行した結果です。

HashMap・LinkedHashMap・TreeMapの早見表

迷ったら HashMap、順番を見せたいなら LinkedHashMap、キーで並べたい・範囲で探したいなら TreeMap が基本の選び方です。

同じデータを入れて出力順を比べる

まず、6件のデータを同じ順番で3種類のMapに入れ、そのまま表示します。

import java.util.*;

public class Order3 {
    public static void main(String[] args) {
        String[] names = {"orange", "apple", "melon", "banana", "kiwi", "grape"};
        int[] stock = {30, 12, 5, 48, 7, 21};

        Map<String, Integer> hash = new HashMap<>();
        Map<String, Integer> linked = new LinkedHashMap<>();
        Map<String, Integer> tree = new TreeMap<>();
        for (int i = 0; i < names.length; i++) {
            hash.put(names[i], stock[i]);
            linked.put(names[i], stock[i]);
            tree.put(names[i], stock[i]);
        }
        System.out.println("入れた順      : " + String.join(", ", names));
        System.out.println("HashMap       : " + hash);
        System.out.println("LinkedHashMap : " + linked);
        System.out.println("TreeMap       : " + tree);

        // 既にあるキーへ上書きしたとき
        hash.put("orange", 99); linked.put("orange", 99); tree.put("orange", 99);
        System.out.println("--- orange を上書き ---");
        System.out.println("HashMap       : " + hash);
        System.out.println("LinkedHashMap : " + linked);
        System.out.println("TreeMap       : " + tree);

        // 消して入れ直したとき
        linked.remove("orange"); linked.put("orange", 99);
        System.out.println("--- LinkedHashMap で remove してから put ---");
        System.out.println("LinkedHashMap : " + linked);
    }
}

実行結果：

入れた順      : orange, apple, melon, banana, kiwi, grape
HashMap       : {orange=30, banana=48, apple=12, kiwi=7, grape=21, melon=5}
LinkedHashMap : {orange=30, apple=12, melon=5, banana=48, kiwi=7, grape=21}
TreeMap       : {apple=12, banana=48, grape=21, kiwi=7, melon=5, orange=30}
--- orange を上書き ---
HashMap       : {orange=99, banana=48, apple=12, kiwi=7, grape=21, melon=5}
LinkedHashMap : {orange=99, apple=12, melon=5, banana=48, kiwi=7, grape=21}
TreeMap       : {apple=12, banana=48, grape=21, kiwi=7, melon=5, orange=99}
--- LinkedHashMap で remove してから put ---
LinkedHashMap : {apple=12, melon=5, banana=48, kiwi=7, grape=21, orange=99}

読み取れることは次の3点です。

• HashMap：入れた順とも辞書順とも違う並びになります。キーのハッシュ値で置き場所が決まるためです。
• LinkedHashMap：入れた順のまま出てきます。既にあるキーに put で上書きしても位置は変わりません。位置を末尾に移したいときは remove してから put します。
• TreeMap：キーの昇順（文字列なら辞書順）で出てきます。入れた順は残りません。

HashMapの順序は件数によって変わる

「HashMap も毎回同じ順で出るから、その順番を当てにしてよいのでは」と感じることがあります。次のコードは、6件入れたあとに20件を追加し、同じ20件を消して中身を元に戻したものです。

import java.util.*;

public class Resize {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        for (String k : List.of("orange", "apple", "melon", "banana", "kiwi", "grape")) {
            map.put(k, 0);
        }
        System.out.println("6件のとき        : " + map.keySet());

        // 20件足してから同じ20件を消す（中身は元の6件に戻る）
        for (int i = 0; i < 20; i++) map.put("tmp" + i, 0);
        for (int i = 0; i < 20; i++) map.remove("tmp" + i);
        System.out.println("増やして戻した後  : " + map.keySet());
    }
}

実行結果：

6件のとき        : [orange, banana, apple, kiwi, grape, melon]
増やして戻した後  : [kiwi, apple, melon, banana, grape, orange]

中身は同じ6件なのに、並びが変わりました。件数が増えると内部の表が広がり、置き場所が計算し直されるためです。公式ドキュメント（HashMap）にも、順序は保証されず、時間がたっても同じとは限らないと書かれています。順序に意味を持たせたい処理では、LinkedHashMap か TreeMap を選ぶのが確実です。

計算量と内部のしくみ

公式ドキュメントでは、HashMap の get・put は「ハッシュ関数が要素をうまく分散させる前提で一定時間」、TreeMap の containsKey・get・put・remove は「log(n) の時間を保証」と説明されています。LinkedHashMap は HashMap に双方向の連結リストを足した作りで、全件ループは容量に関係なく件数に比例します。

O(log n) は件数が100万件でも約20回の比較で済む計算です。通常の業務データの件数では、速度差よりも「どの順序がほしいか」で選ぶほうが、読みやすく直しやすいコードになります。

nullのキーと値を入れたときの挙動

null の扱いは TreeMap だけが異なります。null のキーは、TreeMap では put・get・containsKey のどれでも NullPointerException になります。 null の値は3つとも入ります。

import java.util.*;

public class NullKey {
    public static void main(String[] args) {
        Map<String, Integer> hash = new HashMap<>();
        hash.put(null, 1);
        hash.put("a", null);
        System.out.println("HashMap       : " + hash + " / get(null)=" + hash.get(null));

        Map<String, Integer> linked = new LinkedHashMap<>();
        linked.put("a", null);
        linked.put(null, 1);
        System.out.println("LinkedHashMap : " + linked + " / get(null)=" + linked.get(null));

        Map<String, Integer> tree = new TreeMap<>();
        tree.put("a", null);                       // 値の null は入る
        System.out.println("TreeMap(値null): " + tree);
        try {
            tree.put(null, 1);                     // キーの null
        } catch (NullPointerException e) {
            System.out.println("TreeMap put(null, 1)   : " + e);
        }
        try {
            tree.get(null);
        } catch (NullPointerException e) {
            System.out.println("TreeMap get(null)      : " + e);
        }
        try {
            tree.containsKey(null);
        } catch (NullPointerException e) {
            System.out.println("TreeMap containsKey(null): " + e);
        }

        // Comparator で null の置き場所を決めれば入る
        Map<String, Integer> nullable = new TreeMap<>(Comparator.nullsFirst(Comparator.naturalOrder()));
        nullable.put("b", 2);
        nullable.put(null, 0);
        nullable.put("a", 1);
        System.out.println("nullsFirst の TreeMap : " + nullable);
    }
}

実行結果：

HashMap       : {null=1, a=null} / get(null)=1
LinkedHashMap : {a=null, null=1} / get(null)=1
TreeMap(値null): {a=null}
TreeMap put(null, 1)   : java.lang.NullPointerException
TreeMap get(null)      : java.lang.NullPointerException
TreeMap containsKey(null): java.lang.NullPointerException
nullsFirst の TreeMap : {null=0, a=1, b=2}

TreeMapにnullキーを入れたときのNullPointerException

スタックトレースまで見てみます。

import java.util.*;

public class NullTrace {
    public static void main(String[] args) {
        Map<String, Integer> tree = new TreeMap<>();
        tree.put("a", 1);
        tree.put(null, 2);
    }
}

実行結果：

Exception in thread "main" java.lang.NullPointerException
    at java.base/java.util.Objects.requireNonNull(Objects.java:233)
    at java.base/java.util.TreeMap.put(TreeMap.java:844)
    at java.base/java.util.TreeMap.put(TreeMap.java:569)
    at NullTrace.main(NullTrace.java:7)

TreeMap はキー同士を compareTo で比べて置き場所を決めます。null は比べられないため、put の入り口で Objects.requireNonNull によって止まります。put だけでなく get(null) や containsKey(null) でも同じ例外になる点が、HashMap との違いです。

直し方は2つあります。

上の実行結果の最後の行のとおり、nullsFirst を渡した TreeMap では null のキーが先頭に入ります。

TreeMapの範囲検索：floorKey・ceilingKey・headMap・descendingMap

TreeMap を選ぶ一番の理由は、「このキー以下で最大のもの」「この範囲のキーだけ」をすぐに取り出せることです。購入金額の下限から会員ランクを決める例で確かめます。

import java.util.*;

public class Nav {
    public static void main(String[] args) {
        // 購入金額の下限 → 会員ランク
        NavigableMap<Integer, String> rank = new TreeMap<>();
        rank.put(0, "レギュラー");
        rank.put(10000, "ブロンズ");
        rank.put(30000, "シルバー");
        rank.put(50000, "ゴールド");
        System.out.println("map               : " + rank);

        System.out.println("floorKey(30000)   : " + rank.floorKey(30000));
        System.out.println("floorKey(29999)   : " + rank.floorKey(29999));
        System.out.println("lowerKey(30000)   : " + rank.lowerKey(30000));
        System.out.println("ceilingKey(30000) : " + rank.ceilingKey(30000));
        System.out.println("ceilingKey(30001) : " + rank.ceilingKey(30001));
        System.out.println("higherKey(30000)  : " + rank.higherKey(30000));
        System.out.println("floorKey(-1)      : " + rank.floorKey(-1));
        System.out.println("ceilingKey(50001) : " + rank.ceilingKey(50001));

        System.out.println("floorEntry(42000) : " + rank.floorEntry(42000));
        System.out.println("42000円のランク    : " + rank.floorEntry(42000).getValue());

        System.out.println("firstKey / lastKey: " + rank.firstKey() + " / " + rank.lastKey());
        System.out.println("headMap(30000)        : " + rank.headMap(30000));
        System.out.println("headMap(30000, true)  : " + rank.headMap(30000, true));
        System.out.println("tailMap(30000)        : " + rank.tailMap(30000));
        System.out.println("tailMap(30000, false) : " + rank.tailMap(30000, false));
        System.out.println("subMap(10000, 50000)  : " + rank.subMap(10000, 50000));
        System.out.println("descendingMap()       : " + rank.descendingMap());
        System.out.println("descendingKeySet()    : " + rank.descendingKeySet());

        // headMap はビュー：元の Map の変更が見える
        SortedMap<Integer, String> head = rank.headMap(30000);
        rank.put(5000, "ライト");
        System.out.println("put(5000) 後の head   : " + head);
        try {
            head.put(40000, "範囲外");
        } catch (IllegalArgumentException e) {
            System.out.println("head.put(40000, ...)  : " + e);
        }

        System.out.println("pollFirstEntry()      : " + rank.pollFirstEntry());
        System.out.println("取り出した後           : " + rank);
    }
}

実行結果：

map               : {0=レギュラー, 10000=ブロンズ, 30000=シルバー, 50000=ゴールド}
floorKey(30000)   : 30000
floorKey(29999)   : 10000
lowerKey(30000)   : 10000
ceilingKey(30000) : 30000
ceilingKey(30001) : 50000
higherKey(30000)  : 50000
floorKey(-1)      : null
ceilingKey(50001) : null
floorEntry(42000) : 30000=シルバー
42000円のランク    : シルバー
firstKey / lastKey: 0 / 50000
headMap(30000)        : {0=レギュラー, 10000=ブロンズ}
headMap(30000, true)  : {0=レギュラー, 10000=ブロンズ, 30000=シルバー}
tailMap(30000)        : {30000=シルバー, 50000=ゴールド}
tailMap(30000, false) : {50000=ゴールド}
subMap(10000, 50000)  : {10000=ブロンズ, 30000=シルバー}
descendingMap()       : {50000=ゴールド, 30000=シルバー, 10000=ブロンズ, 0=レギュラー}
descendingKeySet()    : [50000, 30000, 10000, 0]
put(5000) 後の head   : {0=レギュラー, 5000=ライト, 10000=ブロンズ}
head.put(40000, ...)  : java.lang.IllegalArgumentException: key out of range
pollFirstEntry()      : 0=レギュラー
取り出した後           : {5000=ライト, 10000=ブロンズ, 30000=シルバー, 50000=ゴールド}

近いキーを探す4つのメソッド

該当するキーがないときは null が返ります（floorKey(-1) と ceilingKey(50001) の行）。キーと値をまとめてほしいときは floorEntry・ceilingEntry を使います。rank.floorEntry(42000).getValue() の1行で「42000円はシルバー」と判定でき、if 文を並べるより境界値の追加・変更が楽になります。

範囲を切り出すメソッド

headMap・tailMap・subMap・descendingMap が返すのはコピーではなく「ビュー」です。元の TreeMap に put(5000, ...) すると、先に取っておいた head にも 5000 が現れています。ビュー側から範囲外のキーを入れようとすると IllegalArgumentException: key out of range で止まります。切り出した結果を独立して持ちたいときは new TreeMap<>(rank.headMap(30000)) のようにコピーします。

宣言する型で使えるメソッドが決まる

floorKey などは Map インターフェースにはありません。変数を Map 型で宣言すると、次のコンパイルエラーになります。

import java.util.*;

public class DeclErr {
    public static void main(String[] args) {
        Map<Integer, String> rank = new TreeMap<>();
        rank.put(0, "レギュラー");
        System.out.println(rank.floorKey(100));
    }
}

DeclErr.java:7: error: cannot find symbol
        System.out.println(rank.floorKey(100));
                               ^
  symbol:   method floorKey(int)
  location: variable rank of type Map<Integer,String>
1 error
error: compilation failed

宣言の型は、使いたい機能に合わせて選びます。

基本は Map で宣言し、範囲検索を使う変数だけ NavigableMap にすると、あとで実装クラスを差し替えやすくなります。

TreeMapの並び順をComparatorで変える

TreeMap のコンストラクタに Comparator を渡すと、並び順を自由に決められます。降順、大文字小文字を区別しない順、複数条件の順をまとめて確かめます。

import java.math.BigDecimal;
import java.util.*;

public class Comp {
    record Point(int x, int y) {}

    public static void main(String[] args) {
        // 1. 降順
        Map<String, Integer> desc = new TreeMap<>(Comparator.reverseOrder());
        desc.put("orange", 30); desc.put("apple", 12); desc.put("melon", 5);
        System.out.println("降順              : " + desc);

        // 2. 大文字小文字を区別しない（同じとみなされたキーは上書き）
        Map<String, Integer> ci = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
        ci.put("Apple", 1); ci.put("apple", 2); ci.put("APPLE", 3);
        System.out.println("CASE_INSENSITIVE  : " + ci + " / get(\"aPPle\")=" + ci.get("aPPle"));

        // 3. 文字数 → 辞書順 の複合 Comparator
        Map<String, Integer> byLen = new TreeMap<>(
                Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
        byLen.put("orange", 30); byLen.put("apple", 12); byLen.put("melon", 5); byLen.put("kiwi", 7);
        System.out.println("文字数→辞書順      : " + byLen);

        // 3'. thenComparing を付け忘れると、同じ文字数のキーが 1 件にまとまる
        Map<String, Integer> lenOnly = new TreeMap<>(Comparator.comparingInt(String::length));
        lenOnly.put("orange", 30); lenOnly.put("apple", 12); lenOnly.put("melon", 5); lenOnly.put("kiwi", 7);
        System.out.println("文字数だけ         : " + lenOnly);

        // 4. Comparable でないキーを Comparator なしで入れる
        try {
            Map<Point, String> points = new TreeMap<>();
            points.put(new Point(1, 2), "p");
        } catch (ClassCastException e) {
            System.out.println("Comparable でないキー: " + e.getMessage().split(" \\(")[0]);
        }

        // 5. equals と compareTo が食い違うキー（BigDecimal）
        Map<BigDecimal, String> h = new HashMap<>();
        Map<BigDecimal, String> t = new TreeMap<>();
        for (String s : List.of("1.0", "1.00")) {
            h.put(new BigDecimal(s), s);
            t.put(new BigDecimal(s), s);
        }
        System.out.println("BigDecimal HashMap : size=" + h.size() + " " + h);
        System.out.println("BigDecimal TreeMap : size=" + t.size() + " " + t);
    }
}

実行結果：

降順              : {orange=30, melon=5, apple=12}
CASE_INSENSITIVE  : {Apple=3} / get("aPPle")=3
文字数→辞書順      : {kiwi=7, apple=12, melon=5, orange=30}
文字数だけ         : {kiwi=7, apple=5, orange=30}
Comparable でないキー: class Comp$Point cannot be cast to class java.lang.Comparable
BigDecimal HashMap : size=2 {1.0=1.0, 1.00=1.00}
BigDecimal TreeMap : size=1 {1.0=1.00}

押さえておきたい点は3つです。

1. TreeMap は「Comparator が 0 を返す2つのキー」を同じキーとみなします。 String.CASE_INSENSITIVE_ORDER では Apple・apple・APPLE が1件にまとまり、値は最後の 3 に上書きされました（キーは最初に入れた Apple のまま）。
2. 複合 Comparator は thenComparing まで書く。 文字数だけで比べると apple と melon が同じキー扱いになり、4件入れたのに3件になります。thenComparing(Comparator.naturalOrder()) を足すと4件とも残ります。
3. キーのクラスは Comparable を実装するか、Comparator を渡す。 どちらもないと、最初の put で ClassCastException になります。

最後の BigDecimal の例は、equals と compareTo の結果が食い違うクラスをキーにした場合です。HashMap は equals で比べるので 1.0 と 1.00 は別のキー（2件）、TreeMap は compareTo で比べるので同じキー（1件）になります。Mapの種類を替えると件数が変わることがあるので、キーに BigDecimal を使うときは stripTrailingZeros() などで表記をそろえておくと安心です。

LinkedHashMapのアクセス順とLRUキャッシュ

LinkedHashMap には、順序の持ち方が2つあります。

import java.util.*;

public class AccessOrder {
    public static void main(String[] args) {
        Map<String, Integer> insertion = new LinkedHashMap<>();            // 挿入順（既定）
        Map<String, Integer> access = new LinkedHashMap<>(16, 0.75f, true); // アクセス順
        for (String k : List.of("A", "B", "C")) {
            insertion.put(k, 0);
            access.put(k, 0);
        }
        insertion.get("A"); access.get("A");
        insertion.put("B", 1); access.put("B", 1);
        System.out.println("挿入順   : " + insertion);
        System.out.println("アクセス順: " + access);

        // アクセス順の Map を回しながら get するとどうなるか
        try {
            for (String k : access.keySet()) {
                access.get(k);
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("ループ中の get: " + e);
        }
    }
}

実行結果：

挿入順   : {A=0, B=1, C=0}
アクセス順: {C=0, A=0, B=1}
ループ中の get: java.util.ConcurrentModificationException

アクセス順では、get("A") で A が末尾へ、put("B", 1) で B がさらに末尾へ移りました。先頭には「最も長く使われていないもの」が残ります。

最後の行にも注目してください。アクセス順の LinkedHashMap では、get も「構造の変更」にあたるため、keySet を回しながら get すると ConcurrentModificationException になります。ループの中で値がほしいときは、entrySet() を回して getValue() で受け取ります。

removeEldestEntryでLRUキャッシュを作る

LRU（Least Recently Used）キャッシュは、件数の上限を超えたら「最も長く使われていないもの」から消すキャッシュです。アクセス順の LinkedHashMap に removeEldestEntry を組み合わせると、十数行で作れます。

import java.util.*;

public class Lru {
    /** 最大 capacity 件まで保持し、あふれたら最も長く使われていないものを消す */
    static class LruCache<K, V> extends LinkedHashMap<K, V> {
        private final int capacity;

        LruCache(int capacity) {
            super(16, 0.75f, true);   // 第3引数 true = アクセス順
            this.capacity = capacity;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            boolean over = size() > capacity;
            if (over) {
                System.out.println("  (あふれたので削除: " + eldest.getKey() + ")");
            }
            return over;
        }
    }

    public static void main(String[] args) {
        LruCache<String, String> cache = new LruCache<>(3);
        cache.put("A", "ページA");
        cache.put("B", "ページB");
        cache.put("C", "ページC");
        System.out.println("put A,B,C   : " + cache.keySet());

        cache.get("A");                       // A を使う → 末尾（最新）へ
        System.out.println("get(A)      : " + cache.keySet());

        cache.put("D", "ページD");            // 4件目 → 先頭（最古）の B が消える
        System.out.println("put D       : " + cache.keySet());

        cache.getOrDefault("C", "");          // getOrDefault もアクセス扱い
        System.out.println("getOrDefault(C): " + cache.keySet());

        cache.containsKey("A");               // containsKey は順序を変えない
        System.out.println("containsKey(A): " + cache.keySet());

        cache.put("E", "ページE");
        System.out.println("put E       : " + cache.keySet());
    }
}

実行結果：

put A,B,C   : [A, B, C]
get(A)      : [B, C, A]
  (あふれたので削除: B)
put D       : [C, A, D]
getOrDefault(C): [A, D, C]
containsKey(A): [A, D, C]
  (あふれたので削除: A)
put E       : [D, C, E]

get(A) で A が最新になり、4件目の D を入れた時点で最古の B が消えました。getOrDefault もアクセス扱いになり、containsKey では順序が変わらないことも読み取れます。

removeEldestEntry は新しいエントリを入れた直後に呼ばれ、true を返すと先頭（最古）のエントリが消えます。公式ドキュメント（LinkedHashMap）では、アクセス扱いになるメソッドとして put・putIfAbsent・get・getOrDefault・compute・computeIfAbsent・computeIfPresent・merge が挙げられています。

このクラスは複数スレッドからの同時利用には対応していません。 複数スレッドで共有するときは Collections.synchronizedMap(...) で包み、同時に1つのスレッドだけが触れるようにします。

Java 21のSequencedMap：firstEntry・lastEntry・reversed

Java 21 で SequencedMap インターフェースが加わり、LinkedHashMap と TreeMap で「先頭」「末尾」「逆順」を同じメソッド名で扱えるようになりました。

import java.util.*;

public class Seq {
    public static void main(String[] args) {
        SequencedMap<String, Integer> linked = new LinkedHashMap<>();
        linked.put("orange", 30);
        linked.put("apple", 12);
        linked.put("melon", 5);

        System.out.println("linked            : " + linked);
        System.out.println("firstEntry()      : " + linked.firstEntry());
        System.out.println("lastEntry()       : " + linked.lastEntry());
        System.out.println("reversed()        : " + linked.reversed());

        linked.putFirst("kiwi", 7);           // 先頭に入れる
        linked.putLast("orange", 31);         // 既存キーを末尾へ移す
        System.out.println("putFirst/putLast  : " + linked);

        System.out.println("sequencedKeySet().reversed(): " + linked.sequencedKeySet().reversed());
        System.out.println("pollFirstEntry()  : " + linked.pollFirstEntry());
        System.out.println("pollLastEntry()   : " + linked.pollLastEntry());
        System.out.println("残り              : " + linked);

        // reversed() はビュー。元の Map に入れると逆順側にも見える
        SequencedMap<String, Integer> rev = linked.reversed();
        linked.put("grape", 21);
        System.out.println("put 後の rev      : " + rev);

        // TreeMap も SequencedMap
        SequencedMap<String, Integer> tree = new TreeMap<>(linked);
        System.out.println("tree              : " + tree);
        System.out.println("tree.firstEntry() : " + tree.firstEntry());
        System.out.println("tree.reversed()   : " + tree.reversed());
        try {
            tree.putFirst("zzz", 1);
        } catch (UnsupportedOperationException e) {
            System.out.println("tree.putFirst()   : " + e);
        }
        try {
            tree.firstEntry().setValue(100);
        } catch (UnsupportedOperationException e) {
            System.out.println("firstEntry().setValue(): " + e);
        }
        System.out.println("空の Map の firstEntry(): " + new LinkedHashMap<String, Integer>().firstEntry());
    }
}

実行結果：

linked            : {orange=30, apple=12, melon=5}
firstEntry()      : orange=30
lastEntry()       : melon=5
reversed()        : {melon=5, apple=12, orange=30}
putFirst/putLast  : {kiwi=7, apple=12, melon=5, orange=31}
sequencedKeySet().reversed(): [orange, melon, apple, kiwi]
pollFirstEntry()  : kiwi=7
pollLastEntry()   : orange=31
残り              : {apple=12, melon=5}
put 後の rev      : {grape=21, melon=5, apple=12}
tree              : {apple=12, grape=21, melon=5}
tree.firstEntry() : apple=12
tree.reversed()   : {melon=5, grape=21, apple=12}
tree.putFirst()   : java.lang.UnsupportedOperationException
firstEntry().setValue(): java.lang.UnsupportedOperationException
空の Map の firstEntry(): null

注意点は次の3つです。

• TreeMap の putFirst・putLast は使えません。 位置はキーの比較で決まるため、場所を指定して入れる操作は用意されていません。
• firstEntry などが返すエントリは変更できないコピーです。 setValue を呼ぶと UnsupportedOperationException になります。値を変えたいときは put を使います。
• reversed() はビューです。 元の Map に put した grape が、先に取っておいた rev の先頭にも現れています。

HashMap には順序がないため SequencedMap ではなく、SequencedMap 型の変数に new HashMap<>() を代入するとコンパイルエラー（incompatible types）になります。

使い分けの判断表とフロー

flowchart TD
    A[Mapを使いたい] --> B{取り出す順序に意味があるか}
    B -- ない --> H[HashMap]
    B -- ある --> C{どんな順序か}
    C -- 入れた順 --> L[LinkedHashMap]
    C -- 使った順 --> L2[LinkedHashMap アクセス順]
    C -- キーの大小順 --> T[TreeMap]

つまずきやすい点と直し方

よくある質問

Q. LinkedHashMap と TreeMap は HashMap よりどのくらい遅くなりますか？ A. LinkedHashMap は get・put とも HashMap と同じ O(1) が目安で、リンクをつなぐ分のわずかな手間とメモリが加わります。TreeMap は O(log n) で、100万件でも1回の操作あたり約20回の比較です。件数が数万件までの一覧や集計であれば、順序の要件で選んで差し支えありません。

Q. HashMap を後からキー順に並べたいときはどうしますか？ A. new TreeMap<>(hashMap) と書くと、キー昇順に並んだコピーができます。降順なら new TreeMap<>(Comparator.reverseOrder()) を作って putAll します。値の順に並べたいときは、entrySet を Stream で並べ替えて LinkedHashMap に集めます。

Q. Java 20 以前で LinkedHashMap の先頭を取り出すには？ A. SequencedMap は Java 21 で加わったインターフェースなので、それより前では map.entrySet().iterator().next() で先頭を取り出します。末尾は全件を回す必要があります。Java 21 以降なら firstEntry()・lastEntry() で書けます。

Q. 複数スレッドから使うときはどれを選びますか？ A. 3つとも同時更新には対応していません。順序が不要なら ConcurrentHashMap、キー順が必要なら ConcurrentSkipListMap が候補になります。ConcurrentSkipListMap は公式ドキュメントで SequencedMap の実装クラスとして挙げられています。

まとめ

• 3つの違いは取り出す順序：HashMap は順序なし、LinkedHashMap は入れた順、TreeMap はキーの昇順。
• HashMap の並びは件数で変わるため、順序が必要なら LinkedHashMap か TreeMap を選ぶ。
• 計算量は HashMap・LinkedHashMap が O(1) 目安、TreeMap が O(log n)。速度より「ほしい順序」で選ぶ。
• TreeMap は null のキーが入らない（put・get・containsKey とも NullPointerException）。null の値は入る。
• 範囲検索は TreeMap：floorKey・ceilingKey・headMap・tailMap・descendingMap。変数は NavigableMap 型で宣言する。
• LRU キャッシュは LinkedHashMap：new LinkedHashMap<>(16, 0.75f, true) と removeEldestEntry の組み合わせ。
• Java 21 の SequencedMap で、LinkedHashMap と TreeMap の firstEntry・lastEntry・reversed が共通の書き方になった。

参考・出典

• HashMap（Java SE 21 API）
• LinkedHashMap（Java SE 21 API）
• TreeMap（Java SE 21 API）
• SequencedMap（Java SE 21 API）

株式会社RJC ― SI事業・SES事業・AI駆動開発。RJCは一緒に成長を楽しめる会社です。