Класс 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 и допускает нулевые элементы. Как и HashMap, он обеспечивает постоянное время выполнения основных операций (add, contains и remove) при условии, что хеш-функция равномерно распределяет элементы по корзинам. Производительность, вероятно, будет лишь немного ниже, чем у HashMap, из-за дополнительных затрат на поддержку связного списка. Исключение составляет итерация по представлениям-коллекциям LinkedHashMap: она занимает время, пропорциональное размеру карты, независимо от ее емкости. Итерация по HashMap, вероятно, будет дороже и займет время, пропорциональное ее емкости.

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

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

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

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

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

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

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