Класс 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 в режиме наилучшего усилия. Поэтому неправильно писать программу, зависящую от этого исключения для правильности: поведение быстропроверяемых итераторов должно использоваться только для обнаружения ошибок.

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

Этот класс является членом Java Collections Framework.