JavaでのLinkedHashMapのガイド

投稿日: 2019-10-18 2022-10-16
タグ: Java, Java Collections, Java Map

1. 概要

この記事では、LinkedHashMapクラスの内部実装について説明します。LinkedHashMapは、Mapインターフェースの一般的な実装です。

この特定の実装はHashMapのサブクラスであるため、HashMap実装のコアビルディングブロックを共有します。したがって、この記事に進む前に、それをブラッシュアップすることを強くお勧めします。

2. LinkedHashMapとHashMap

LinkedHashMap クラスは、ほとんどの点でHashMapと非常によく似ています。ただし、リンクされたハッシュマップは、ハッシュテーブルとリンクされたリストの両方に基づいており、ハッシュマップの機能を強化しています。

デフォルトサイズ16の基になる配列に加えて、すべてのエントリを実行する二重リンクリストを維持します。

要素の順序を維持するために、リンクされたハッシュマップは、次および前のエントリへのポインタを追加することにより、HashMapのMap.Entryクラスを変更します。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Entryクラスは単に2つのポインターを追加するだけであることに注意してください。 beforeおよびafterは、リンクリストに自分自身をフックできるようにします。それとは別に、HashMapのEntryクラスの実装を使用します。

最後に、このリンクリストは反復の順序を定義することを忘れないでください。これはデフォルトでは要素の挿入順序（挿入順序）です。

3. 挿入-注文LinkedHashMap

マップへの挿入方法に従ってエントリを並べ替えるリンクされたハッシュマップインスタンスを見てみましょう。また、この順序がマップのライフサイクル全体で維持されることも保証されます。

@Test
public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect() {
    LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
    map.put(1, null);
    map.put(2, null);
    map.put(3, null);
    map.put(4, null);
    map.put(5, null);

    Set<Integer> keys = map.keySet();
    Integer[] arr = keys.toArray(new Integer[0]);

    for (int i = 0; i < arr.length; i++) {
        assertEquals(new Integer(i + 1), arr[i]);
    }
}

ここでは、リンクされたハッシュマップ内のエントリの順序について、基本的な非決定的なテストを行っています。

挿入順序は常に維持されるため、このテストが常に合格することを保証できます。 HashMapに対して同じ保証をすることはできません。

この属性は、任意のマップを受け取り、操作するためのコピーを作成して呼び出し元のコードに返すAPIで非常に有利です。クライアントがAPIを呼び出す前に、返されたマップを同じ方法で並べ替える必要がある場合は、リンクされたハッシュマップが最適です。

キーがマップに再挿入されても、挿入順序は影響を受けません。

4. アクセス注文LinkedHashMap

LinkedHashMap は、カスタム負荷率（LF）と初期容量の間で、access-orderと呼ばれる別の順序付けメカニズム/戦略を指定できる特別なコンストラクターを提供します。

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, .75f, true);

最初のパラメーターは初期容量で、その後に負荷率が続き、最後のパラメーターは順序付けモードです。したがって、 true を渡すことにより、アクセス順序をオンにしましたが、デフォルトは挿入順序でした。

このメカニズムにより、要素の反復の順序が、要素が最後にアクセスされた順序（最も最近アクセスされたものから最も最近アクセスされたものへ）になります。

したがって、この種のマップを使用すると、最近使用されていない（LRU）キャッシュを構築するのは非常に簡単で実用的です。 putまたはget操作が成功すると、エントリへのアクセスが発生します。

@Test
public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() {
    LinkedHashMap<Integer, String> map 
      = new LinkedHashMap<>(16, .75f, true);
    map.put(1, null);
    map.put(2, null);
    map.put(3, null);
    map.put(4, null);
    map.put(5, null);

    Set<Integer> keys = map.keySet();
    assertEquals("[1, 2, 3, 4, 5]", keys.toString());
 
    map.get(4);
    assertEquals("[1, 2, 3, 5, 4]", keys.toString());
 
    map.get(1);
    assertEquals("[2, 3, 5, 4, 1]", keys.toString());
 
    map.get(3);
    assertEquals("[2, 5, 4, 1, 3]", keys.toString());
}

マップ上でアクセス操作を実行すると、キーセット内の要素の順序がどのように変換されるかに注意してください。

簡単に言うと、マップ上のアクセス操作は、反復がすぐに実行された場合にアクセスされた要素が最後に表示されるような順序になります。

上記の例の後、 putAll 操作により、指定されたマップ内のマッピングごとに1つのエントリアクセスが生成されることは明らかです。

当然、マップのビューに対する反復は、バッキングマップの反復の順序には影響しません。 マップ上の明示的なアクセス操作のみが順序に影響します。

LinkedHashMap は、固定数のマッピングを維持し、新しいエントリを追加する必要がある場合に最も古いエントリを削除し続けるためのメカニズムも提供します。

removeEldestEntry メソッドをオーバーライドして、古いマッピングを自動的に削除するためのこのポリシーを適用できます。

これを実際に確認するために、 LinkedHashMap を拡張して古いマッピングを強制的に削除することを唯一の目的として、独自のリンクされたハッシュマップクラスを作成しましょう。

public class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V> {

    private static final int MAX_ENTRIES = 5;

    public MyLinkedHashMap(
      int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor, accessOrder);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

}

上記のオーバーライドにより、マップを最大5エントリのサイズに拡大できます。サイズがそれを超えると、マップ内の最も古いエントリを失うという犠牲を払って、新しいエントリが挿入されます。最終アクセス時間が他のすべてのエントリよりも前にあるエントリ：

@Test
public void givenLinkedHashMap_whenRemovesEldestEntry_thenCorrect() {
    LinkedHashMap<Integer, String> map
      = new MyLinkedHashMap<>(16, .75f, true);
    map.put(1, null);
    map.put(2, null);
    map.put(3, null);
    map.put(4, null);
    map.put(5, null);
    Set<Integer> keys = map.keySet();
    assertEquals("[1, 2, 3, 4, 5]", keys.toString());
 
    map.put(6, null);
    assertEquals("[2, 3, 4, 5, 6]", keys.toString());
 
    map.put(7, null);
    assertEquals("[3, 4, 5, 6, 7]", keys.toString());
 
    map.put(8, null);
    assertEquals("[4, 5, 6, 7, 8]", keys.toString());
}

マップに新しいエントリを追加すると、キーセットの先頭にある最も古いエントリがドロップし続けることに注意してください。

5. パフォーマンスに関する考慮事項

HashMap と同様に、 LinkedHashMap は、ハッシュ関数のディメンションが適切である限り、追加、削除、および包含の基本的なMap操作を一定時間で実行します。また、nullキーとnull値を受け入れます。

ただし、LinkedHashMapのこの一定時間のパフォーマンスは、二重リンクリストを維持するための追加のオーバーヘッドのために、HashMapの一定時間よりも少し悪くなる可能性があります。

LinkedHashMap のコレクションビューの反復も、 HashMapと同様の線形時間O（n）を要します。反対に、反復中のLinkedHashMapの線形時間パフォーマンスは、HashMapの線形時間よりも優れています。

これは、 LinkedHashMap の場合、 O（n）の n は、容量に関係なく、マップ内のエントリの数のみであるためです。一方、 HashMap の場合、 n は容量であり、サイズの合計は O（サイズ+容量）です。

負荷率と初期容量は、HashMapと同様に正確に定義されています。ただし、このクラスの反復時間は容量の影響を受けないため、初期容量に過度に高い値を選択した場合のペナルティはHashMapよりもLinkedHashMapの方が厳しくないことに注意してください。

6. 並行性

HashMap と同様に、LinkedHashMapの実装は同期されません。したがって、複数のスレッドからアクセスする予定であり、これらのスレッドの少なくとも1つが構造的に変更する可能性がある場合は、外部で同期する必要があります。

作成時にこれを行うのが最善です：

Map m = Collections.synchronizedMap(new LinkedHashMap());

HashMap との違いは、構造の変更を伴うものにあります。 アクセス順のリンクされたハッシュマップでは、getAPIを呼び出すだけで構造が変更されます。これに加えて、putやremoveのような操作があります。

7. 結論

この記事では、Java LinkedHashMap クラスを、使用法の観点からMapインターフェースの最も重要な実装の1つとして検討しました。また、スーパークラスである HashMap との違いの観点から、その内部動作を調査しました。

うまくいけば、この投稿を読んだ後、ユースケースでどのマップ実装を採用するかについて、より多くの情報に基づいた効果的な決定を下すことができます。

この記事で使用されているすべての例の完全なソースコードは、GitHubプロジェクトにあります。

getdocs

13036