Класс 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. Таким образом, при одновременном изменении итератор быстро и чисто завершается, а не рискует произвольным непредсказуемым поведением в неопределённый момент времени в будущем.

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

Разделители, возвращаемые методом spliterator коллекций, возвращаемых методами представления коллекции всех методов этого класса, создаются из итераторов соответствующих коллекций.

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