«1. Обзор
В этой статье мы рассмотрим внутреннюю реализацию класса LinkedHashMap. LinkedHashMap — это обычная реализация интерфейса Map.
Эта конкретная реализация является подклассом HashMap и, следовательно, разделяет основные строительные блоки реализации HashMap. В результате настоятельно рекомендуется освежить в памяти это, прежде чем приступить к этой статье.
2. LinkedHashMap и HashMap
Класс LinkedHashMap очень похож на HashMap во многих аспектах. Однако связанная хеш-карта основана как на хэш-таблице, так и на связанном списке, чтобы расширить функциональность хэш-карты.
Он поддерживает двусвязный список, проходящий через все его записи, в дополнение к базовому массиву размера по умолчанию 16.
Чтобы сохранить порядок элементов, связанная хэш-карта изменяет класс Map.Entry HashMap, добавляя указатели. к следующей и предыдущей записям:
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}Обратите внимание, что класс Entry просто добавляет два указателя; до и после чего позволяет ему подключиться к связанному списку. Кроме того, он использует реализацию класса Entry для HashMap.
Наконец, помните, что этот связанный список определяет порядок итерации, который по умолчанию является порядком вставки элементов (insertion-order).
3. Порядок вставки LinkedHashMap
Давайте посмотрим на экземпляр связанной хеш-карты, который упорядочивает свои записи в соответствии с тем, как они вставляются в карту. Это также гарантирует, что этот порядок будет поддерживаться на протяжении всего жизненного цикла карты:
@Test
public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect() {
LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
map.put(1, null);
map.put(2, null);
map.put(3, null);
map.put(4, null);
map.put(5, null);
Set<Integer> 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]);
}
}Здесь мы просто проводим элементарный, не окончательный тест на порядок записей в связанной хеш-карте.
Мы можем гарантировать, что этот тест всегда будет проходить, так как порядок вставки всегда будет поддерживаться. Мы не можем дать такую же гарантию для HashMap.
Этот атрибут может иметь большое преимущество в API, который получает любую карту, делает копию для управления и возвращает ее вызывающему коду. Если клиенту нужно, чтобы возвращенная карта была упорядочена таким же образом перед вызовом API, тогда лучше использовать связанную хэш-карту.
Порядок вставки не изменяется, если ключ повторно вставляется в карту.
4. Access-Order LinkedHashMap
LinkedHashMap предоставляет специальный конструктор, который позволяет нам указать, помимо пользовательского коэффициента загрузки (LF) и начальной емкости, другой механизм/стратегию упорядочения, называемый access-order:
LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, .75f, true);~~ ~ Первый параметр — начальная мощность, за ним следует коэффициент загрузки, а последний параметр — режим заказа. Итак, передав true, мы включили порядок доступа, тогда как по умолчанию был порядок вставки.
Этот механизм гарантирует, что порядок итерации элементов соответствует порядку, в котором к элементам обращались в последний раз, от наименее недавно использованных до наиболее недавно использованных.
Таким образом, создание кеша наименее недавно использованных (LRU) довольно просто и практично с такой картой. Успешная операция put или get приводит к доступу к записи:
@Test
public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() {
LinkedHashMap<Integer, String> 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<Integer> 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:
public class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
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;
}
}«
@Test
public void givenLinkedHashMap_whenRemovesEldestEntry_thenCorrect() {
LinkedHashMap<Integer, String> 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<Integer> 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 записей. Когда размер превышает этот, каждая новая запись будет вставлена за счет потери самой старой записи на карте, т. е. записи, время последнего доступа которой предшествует всем остальным записям:
Обратите внимание, сколько самых старых записей в начале набора ключей продолжают исчезать по мере добавления новых на карту.
5. Вопросы производительности
Так же, как и HashMap, LinkedHashMap выполняет базовые операции добавления, удаления и содержания с картой за постоянное время, если хэш-функция имеет правильные размеры. Он также принимает нулевой ключ, а также нулевые значения.
Однако эта производительность LinkedHashMap с постоянным временем, вероятно, будет немного хуже, чем производительность HashMap с постоянным временем из-за дополнительных накладных расходов на поддержку двусвязного списка.
Перебор представлений коллекций LinkedHashMap также занимает линейное время O(n), как и у HashMap. С другой стороны, производительность линейного времени LinkedHashMap во время итерации лучше, чем линейное время HashMap.
Это связано с тем, что для LinkedHashMap n в O(n) — это только количество записей на карте независимо от емкости. Принимая во внимание, что для HashMap n — это емкость, а суммированный размер — O (размер + емкость).
Фактор нагрузки и начальная емкость определяются точно так же, как и для HashMap. Обратите внимание, однако, что наказание за выбор чрезмерно высокого значения для начальной емкости менее серьезно для LinkedHashMap, чем для HashMap, поскольку время итерации для этого класса не зависит от емкости.
6. Параллелизм
Как и HashMap, реализация LinkedHashMap не синхронизируется. Поэтому, если вы собираетесь обращаться к нему из нескольких потоков и, по крайней мере, один из этих потоков, вероятно, изменит его структурно, тогда он должен быть синхронизирован извне.
Map m = Collections.synchronizedMap(new LinkedHashMap());Лучше всего сделать это при создании:
Разница с HashMap заключается в том, что влечет за собой структурную модификацию. В связанных хеш-картах с упорядоченным доступом простой вызов API get приводит к структурной модификации. Наряду с этим есть такие операции, как поставить и удалить.
7. Заключение
В этой статье мы рассмотрели класс Java LinkedHashMap как одну из передовых реализаций интерфейса Map с точки зрения использования. Мы также изучили его внутреннюю работу с точки зрения отличий от HashMap, который является его суперклассом.
Надеюсь, прочитав этот пост, вы сможете принять более обоснованные и эффективные решения о том, какую реализацию карты использовать в вашем случае использования.