1. Обзор

В этой статье мы собираемся изучить внутреннюю реализацию класса LinkedHashMap. LinkedHashMap является распространенной реализацией интерфейса Map.

Эта конкретная реализация является подклассом HashMap и поэтому разделяет основные строительные блоки реализации HashMap. В результате его настоятельно рекомендуется освежить в памяти, прежде чем приступить к этой статье.

2. LinkedHashMap против HashMap

Класс LinkedHashMap очень похож на HashMap в большинстве аспектов. Однако связанная хэш-карта основана на хэш-таблице и связанном списке для улучшения функциональности хэш-карты.

Он поддерживает двусвязный список, проходящий через все его записи в дополнение к базовому массиву размера 16 по умолчанию.

Чтобы поддерживать порядок элементов, связанная хэш-карта модифицирует класс Map.Entry HashMap, добавляя указатели на следующую и предыдущую записи.

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 просто добавляет два указателя до и после, что позволяет ему подключаться к связанному списку. Кроме того, он использует реализацию класса Entry HashMap.

Наконец, помните, что этот связанный список определяет порядок итерации, который по умолчанию является порядком вставки элементов (insertion-order).

3. InsertionOrder и 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. AccessOrder LinkedHashMap

LinkedHashMap предоставляет специальный конструктор, который позволяет нам указать, среди пользовательских коэффициентов загрузки (load factor, LF) и начальной емкости, другой механизм/стратегия порядка, называемую access-order:

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

Первый параметр - это начальная емкость, за которой следует коэффициент загрузки, а последним параметром - режим заказа. Таким образом, передав значение true, мы получили access-order, тогда как по умолчанию был insert-order.

Этот механизм гарантирует, что порядок итерации элементов - это порядок, в котором к элементам последний раз обращались, от наименее недавнего доступа до наиболее недавнего доступа.

Итак, создание кеша с наименьшим количеством недавно использовавшихся (Least Recently Used - 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 генерирует один доступ к записи для каждого из отображений в указанной карте.

Естественно, итерации по виду карты не влияют на порядок итерации базовой карты, только порядковые операции доступа к карте будут влиять на порядок.

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;
    }

}

Наша переопределение выше позволит карте увеличиться до максимального размера записей. Когда размер превышает этот, каждая новая запись будет вставлена ​​за счет потери самой старшей записи на карте, то есть записи, время доступа которой предшествует всем другим записям.

@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 по добавлению, удалению и содержанию в постоянном времени, пока хеш-функция имеет хороший размер. Он также принимает нулевой ключ и нулевые значения.

Тем не менее, эта производительность LinkedHashMap в постоянное время, вероятно, будет немного хуже, чем в HashMap с постоянным временем, из-за дополнительных накладных расходов на поддержание двусвязного списка.

Итерация по представлениям коллекции LinkedHashMap также занимает линейное время, аналогичное HashMap. С другой стороны, производительность линейного времени LinkedHashMap во время итерации лучше, чем линейное время HashMap.

Это связано с тем, что для LinkedHashMap значение n в O(n)- это только количество записей на карте независимо от емкости. Принимая во внимание, что для HashMap n - это емкость и сумма, O(Размер + Емкость).

Коэффициент загрузки и начальная емкость определяются точно так же, как и для HashMap. Однако обратите внимание, что штраф за выбор чрезмерно высокого значения для начальной емкости для LinkedHashMap менее суров, чем для HashMap, поскольку время итерации для этого класса не зависит от емкости.

6. Параллелизм

Как и в HashMap, реализация LinkedHashMap не синхронизируется. Таким образом, если вы собираетесь обращаться к нему из нескольких потоков, и хотя бы один из этих потоков может изменить его структурно, то он должен быть внешне синхронизирован.

Лучше всего сделать это при создании

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

Разница с HashMap заключается в том, что влечет за собой структурную модификацию. В связанных хеш-картах с произвольным доступом простой вызов API get приводит к структурной модификации. Наряду с этим, такие операции, как put и remove.

7. Заключение

В этой статье мы рассмотрели класс Java LinkedHashMap как одну из передовых реализаций интерфейса Map с точки зрения использования. Мы также изучили его внутреннюю работу с точки зрения отличия от HashMap, который является его суперклассом.

Надеемся, что после прочтения этого поста вы сможете принимать более обоснованные и эффективные решения относительно того, какую реализацию Map использовать в вашем случае использования.