1概要

この記事では、

LinkedHashMap

クラスの内部実装を探ります。

LinkedHashMap

は、

Map

インターフェースの一般的な実装です。

この特定の実装は

HashMap

のサブクラスであるため、リンクの中心的な構成要素を共有します。/java-hashmap[

HashMap

implementation]。結果として、この記事を読む前にそれについてブラッシュアップすることを強くお勧めします。


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

クラス実装を使用します。

最後に、このリンクリストは繰り返しの順序を定義していることを覚えておいてください。これはデフォルトで要素の挿入の順序(insert-order)です。


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(Least Recently Used)キャッシュを作成するのは、一種のマップでは非常に簡単で実用的です。

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

は、ハッシュ関数が適切な次元である限り、add、remove、およびcontainsの基本的な

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

との違いは、構造上の変更が必要な点です。

アクセス順リンクハッシュマップでは、

get

APIを呼び出すだけで構造上の変更が発生します

。これと並んで、

put



remove

のような操作があります。


7. 結論

この記事では、使用法の観点から、

Map

インターフェースの最も重要な実装の1つとして、Java

LinkedHashMap

クラスを検討しました。また、そのスーパークラスである

HashMap

との違いについても、内部の仕組みを調べました。

この記事を読んだ後で、ユースケースでどのMap実装を採用するかについて、より情報に基づいた効果的な決定を下すことができれば幸いです。

この記事で使用されているすべての例の完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/java-collections-maps[GitHubプロジェクト]にあります。