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.
Наконец, помните, что этот связанный список определяет порядок итерации, который по умолчанию является порядком вставки элементов (порядок вставки).
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. Порядок доступа LinkedHashMap
LinkedHashMap предоставляет специальный конструктор, который позволяет нам указать среди пользовательского коэффициента загрузки (LF) и начальной емкости другой механизм/стратегию упорядочения, называемый access-order :
LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, .75f, true);
Первый параметр — это начальная мощность, за ней следует коэффициент загрузки, а последний параметр — это режим заказа . Итак, передав true , мы включили порядок доступа, тогда как по умолчанию был порядок вставки.
Этот механизм гарантирует, что порядок итерации элементов соответствует порядку, в котором к элементам обращались в последний раз, от наименее недавно использованных до наиболее недавно использованных.
Таким образом, создание кеша наименее недавно использованных (LRU) довольно просто и практично с такой картой. Успешная операция ввода или получения приводит к доступу к записи:
@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;
}
}
Наше переопределение выше позволит карте увеличиться до максимального размера 5 записей. Когда размер превышает этот, каждая новая запись будет вставлена за счет потери самой старой записи на карте, т. е. записи, время последнего доступа которой предшествует всем остальным записям:
@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. Вопросы производительности
Как и HashMap , LinkedHashMap выполняет базовые операции добавления, удаления и содержания с картой в постоянное время, если хэш-функция имеет правильные размеры. Он также принимает нулевой ключ, а также нулевые значения.
Однако эта производительность LinkedHashMap с постоянным временем , вероятно, будет немного хуже, чем производительность HashMap с постоянным временем из -за дополнительных накладных расходов на поддержку двусвязного списка.
Итерация по представлениям коллекции LinkedHashMap также занимает линейное время O(n) , аналогичное времени HashMap . С другой стороны, производительность линейного времени LinkedHashMap во время итерации лучше, чем линейное время HashMap .
Это связано с тем, что для LinkedHashMap n в O (n) — это только количество записей на карте независимо от емкости. Принимая во внимание, что для HashMap n - это емкость, а суммированный размер O (размер + емкость).
Load Factor и Initial Capacity определяются точно так же, как и для HashMap . Обратите внимание, однако, что наказание за выбор чрезмерно высокого значения для начальной емкости менее серьезно для LinkedHashMap , чем для HashMap , поскольку время итерации для этого класса не зависит от емкости.
6. Параллелизм
Как и HashMap , реализация LinkedHashMap не синхронизируется. Поэтому, если вы собираетесь обращаться к нему из нескольких потоков и, по крайней мере, один из этих потоков, вероятно, изменит его структурно, тогда он должен быть синхронизирован извне.
Лучше всего сделать это при создании:
Map m = Collections.synchronizedMap(new LinkedHashMap());
Разница с HashMap заключается в том, что влечет за собой структурную модификацию. В связанных хеш-картах с упорядоченным доступом простой вызов API get приводит к структурной модификации . Наряду с этим существуют такие операции, как put и remove .
7. Заключение
В этой статье мы рассмотрели класс Java LinkedHashMap как одну из передовых реализаций интерфейса Map с точки зрения использования. Мы также изучили его внутреннюю работу с точки зрения отличий от HashMap , который является его суперклассом.
Надеемся, что после прочтения этого поста вы сможете принять более обоснованные и эффективные решения о том, какую реализацию Map использовать в вашем случае использования.
Полный исходный код всех примеров, использованных в этой статье, можно найти в проекте GitHub .