Рубрики
Без рубрики

Руководство по LinkedHashMap на Java

Краткое и практическое руководство по LinkedHashMap на Java

Автор оригинала: baeldung.

1. Обзор

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

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

2. LinkedHashMap против HashMap

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

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

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

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

Обратите внимание, что класс Entry просто добавляет два указателя; до и после , которые позволяют ему подключаться к связанному списку. Кроме того, он использует реализацию класса Entry для хэш-карты.

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

3. Порядок вставки LinkedHashMap

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

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

    Set 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]);
    }
}

Здесь мы просто проводим элементарный, неубедительный тест на упорядочение записей в linkedhashmap.

Мы можем гарантировать, что этот тест всегда будет проходить, так как порядок вставки всегда будет сохраняться. Мы не можем дать такую же гарантию для хэш-карты.

Этот атрибут может иметь большое преимущество в API, который получает любую карту, делает копию для манипулирования и возвращает ее в вызывающий код. Если клиенту нужно, чтобы возвращенная карта была заказана таким же образом перед вызовом API, то linkedhashmap-это правильный путь.

Порядок вставки не изменяется, если ключ повторно вставлен в карту.

4. Порядок доступа LinkedHashMap

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

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

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

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

Таким образом, создание наименее недавно использованного кэша (LRU) довольно просто и практично с помощью такого рода карт. Успешная операция put или get приводит к доступу к записи:

@Test
public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() {
    LinkedHashMap 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 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 с единственной целью принудительного удаления устаревших отображений путем расширения LinkedHashMap :

public class MyLinkedHashMap extends LinkedHashMap {

    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 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 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 также занимает линейное время O(n) аналогично времени HashMap . С другой стороны, LinkedHashMap производительность линейного времени во время итерации лучше, чем HashMap линейное время .

Это связано с тем, что для LinkedHashMap , n in O(n) – это только количество записей на карте, независимо от емкости. В то время как для HashMap , n – это емкость и суммированный размер, O(размер+емкость).

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

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

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

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

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

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

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

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

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

Полный исходный код для всех примеров, используемых в этой статье, можно найти в проекте GitHub .

Читайте ещё по теме: