Класс LinkedHashMap<K,V>

Реализация интерфейса Map на основе хеш-таблицы и связного списка с определенным порядком обхода. Эта реализация отличается от HashMap тем, что поддерживает двусвязный список, проходящий через все его записи. Этот связный список определяет порядок обхода (порядок итерации), который обычно соответствует порядку вставки ключей в карту (порядку вставки). Первой идет запись, вставленная раньше всех (самая старая), последней — вставленная позже всех (самая новая). Обратите внимание, что повторная вставка ключа в карту с помощью метода put не влияет на порядок обхода. (Ключ k повторно вставляется в карту m, если при вызове m.put(k, v) метод m.containsKey(k) непосредственно перед вызовом возвращает true.) Представление этой карты в обратном порядке имеет противоположный порядок: первой идет самая новая запись, а последней — самая старая. Порядок обхода уже имеющихся в карте записей можно изменить с помощью методов putFirst и putLast.

Эта реализация избавляет клиентский код от неопределенного, обычно хаотичного порядка, предоставляемого HashMap (и Hashtable), не неся при этом дополнительных затрат, связанных с TreeMap. С ее помощью можно создать копию карты с тем же порядком элементов, что и у исходной карты, независимо от реализации исходной карты:

    void foo(Map<String, Integer> m) {
        Map<String, Integer> copy = new LinkedHashMap<>(m);
        ...
    }

Для создания связанной хеш-карты, порядок обхода которой соответствует порядку последнего доступа к ее записям — от наименее недавно использованной до наиболее недавно использованной (порядок доступа), предусмотрен специальный конструктор constructor. Карты такого типа хорошо подходят для создания LRU-кэшей. Вызов методов put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent или merge приводит к обращению к соответствующей записи (если она существует после завершения вызова). Методы replace приводят к обращению к записи только в том случае, если значение заменяется. Метод putAll выполняет по одному обращению к записи для каждого соответствия в указанной карте в порядке, в котором пары ключ-значение предоставляются итератором набора записей этой карты. Никакие другие методы не приводят к обращениям к записям. Вызов этих методов для обратного представления приводит к обращениям к записям базовой карты. Обратите внимание, что в обратном представлении при обращении к записи она перемещается в начало порядка обхода. Методы явного позиционирования, такие как putFirst или lastEntry, независимо от того, вызываются ли они для карты или для ее представления в обратном порядке, выполняют операцию позиционирования и не приводят к обращениям к записям. Операции с представлениями keySet, values и entrySet или с соответствующими им упорядоченными представлениями не влияют на порядок обхода базовой карты.

Метод removeEldestEntry(Map.Entry) можно переопределить, чтобы задать политику автоматического удаления устаревших соответствий при добавлении новых соответствий в карту. Кроме того, поскольку «самая старая» запись является первой в порядке обхода, программы могут проверять и удалять устаревшие соответствия с помощью методов firstEntry и pollFirstEntry.

Этот класс предоставляет все необязательные операции Map и SequencedMap и допускает элементы null. Как и HashMap, он обеспечивает постоянное время выполнения основных операций (add, contains и remove), если хеш-функция правильно распределяет элементы по корзинам. Производительность, вероятно, будет лишь немного ниже, чем у HashMap, из-за дополнительных затрат на поддержку связного списка; исключением является итерация по представлениям-коллекциям LinkedHashMap, для которой требуется время, пропорциональное размеру карты, независимо от ее емкости. Итерация по HashMap, вероятно, будет более затратной и потребует времени, пропорционального ее емкости.

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

Обратите внимание, что эта реализация не синхронизирована. Если несколько потоков одновременно обращаются к связанной хеш-карте и хотя бы один из них структурно изменяет карту, доступ должен синхронизироваться извне. Обычно синхронизацию выполняют на объекте, который естественным образом инкапсулирует карту. Если такого объекта нет, карту следует «обернуть» с помощью метода Collections.synchronizedMap. Лучше всего сделать это при создании карты, чтобы предотвратить случайный доступ к ней без синхронизации:

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

Итераторы, возвращаемые методом iterator коллекций, полученных с помощью методов представлений-коллекций этого класса, являются быстро завершающимися при изменении (fail-fast): если после создания итератора карта структурно изменится каким-либо способом, кроме вызова собственного метода remove итератора, итератор выбросит исключение ConcurrentModificationException. Таким образом, при параллельном изменении итератор быстро и корректно завершает работу, а не рискует в неопределенный момент в будущем привести к произвольному недетерминированному поведению.

Обратите внимание, что гарантировать быстрое завершение итератора при изменении невозможно, поскольку, вообще говоря, нельзя дать строгих гарантий при несинхронизированном параллельном изменении. Итераторы выбрасывают ConcurrentModificationException лишь при первой возможности. Поэтому не следует писать программу, корректность которой зависит от этого исключения: быстрое завершение итераторов при изменении следует использовать только для обнаружения ошибок.

Сплитераторы, возвращаемые методом spliterator коллекций, полученных с помощью методов представлений-коллекций этого класса, имеют отложенное связывание, быстро завершаются при изменении и дополнительно сообщают характеристику Spliterator.ORDERED.

Этот класс входит в состав Java Collections Framework.