Привет, Хабрамен! После долгой паузы я попробую продолжить визуализацию структур данных на Java. В предыдущих статьях отмечалось: ArrayList , Связанный список , Хэшмап .
Сегодня мы заглянем внутрь LinkedHashMap. 
Из названия можно догадаться, что эта структура представляет собой симбиоз связанных списков и хэш-карт. Действительно, LinkedHashMap расширяет класс HashMap и реализует интерфейс Map, но что такого особенного в связанных списках? Давайте разберемся.
Создание объекта
Map<Integer, String> linkedHashMap = new LinkedHashMap<Integer, String>();
Footprint{Objects=3, References=26, Primitives=[int x 4, float, boolean]} size: 160 bytesНедавно созданный объект связанныйHashMap , помимо свойств, унаследованных от Хэшмап (например, таблица, loadFactor, порог, размер, набор записей и т. д.), также содержит два дополнительных.
характеристики:
- заголовок — «голова» двусвязного списка.
При инициализации он указывает на себя;
- доступЗаказ — указывает, как будут осуществляться доступ к элементам при использовании итератора.
Когда значение истинный — в порядке последнего доступа (подробнее об этом см.
конец статьи).
Когда значение ЛОЖЬ доступ осуществляется в том порядке, в котором были вставлены элементы.
А вот инициализация свойства заголовок происходит в переопределенном методе в этом() ( Теперь становится понятно, почему в конструкторах классов Хэшмап есть вызов этой функции ожидания ).
void init()
{
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}
Новый объект создан, свойства инициализированы и можно переходить к добавлению элементов.
Добавление элементов
linkedHashMap.put(1, "obj1"); Footprint{Objects=7, References=32, Primitives=[char x 4, int x 9, float, boolean]} size: 256 bytesПри добавлении элемента сначала вызывается метод createEntry (хеш, ключ, значение, BucketIndex) (по цепочке помещать() -> добавитьEntry() -> создатьEntry() )
void createEntry(int hash, K key, V value, int bucketIndex)
{
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
первые три строки добавляют элемент (в случае коллизий добавление будет происходить в начале цепочки, мы увидим это позже)
четвертая строка переопределяет ссылки двусвязного списка
Все, что происходит дальше в методе добавитьEntry() или не представляет «функционального интереса» 1 или повторяет функциональность родительского класса.
Добавим еще пару элементов linkedHashMap.put(15, "obj15");
Footprint{Objects=11, References=38, Primitives=[float, boolean, char x 9, int x 14]}
size: 352 bytes
linkedHashMap.put(4, "obj4");
Footprint{Objects=11, References=38, Primitives=[float, boolean, char x 9, int x 14]}
size: 448 bytes
При добавлении очередного элемента происходит коллизия и элементы с ключами 4 и 38 образуют цепочку linkedHashMap.put(38, "obj38");
Footprint{Objects=20, References=51, Primitives=[float, boolean, char x 18, int x 24]}
size: 560 bytes
Обратите внимание, что при повторной вставке элемента (элемент с таким ключом уже существует) порядок доступа к элементам не изменится.
доступОрдер == истина
Теперь давайте рассмотрим пример, когда свойство доступЗаказ имеет значение истинный .В такой ситуации поведение LinkedHashMap меняется при вызове методов получать() И помещать() порядок элементов будет изменен — адресуемый элемент будет помещен в конец.
Map<Integer, String> linkedHashMap = new LinkedHashMap<Integer, String>(15, 0.75f, true) {{
put(1, "obj1");
put(15, "obj15");
put(4, "obj4");
put(38, "obj38");
}};
// {1=obj1, 15=obj15, 4=obj4, 38=obj38}
linkedHashMap.get(1); // or linkedHashMap.put(1, "Object1");
// {15=obj15, 4=obj4, 38=obj38, 1=obj1}
Итераторы
Все довольно банально: // 1.
Iterator<Entry<Integer, String>> itr1 = linkedHashMap.entrySet().
iterator();
while (itr1.hasNext()) {
Entry<Integer, String> entry = itr1.next();
System.out.println(entry.getKey() + " = " + entry.getValue());
}
// 2.
Iterator<Integer> itr2 = linkedHashMap.keySet().
iterator();
while(itr2.hasNext())
System.out.println(itr2.next());
// 3.
Iterator<String> itr3 = linkedHashMap.values().
iterator();
while (itr3.hasNext())
System.out.println(itr3.next());
Ну и не забываем про отказоустойчивость.
Если вы уже начали перебирать элементы, не меняйте содержимое и не заботьтесь о синхронизации заранее.
Вместо результатов
Эта структура может немного уступать по производительности своей родительской Хэшмап , а время выполнения операций добавить(), содержит(), удалить() остается постоянным - O(1).Для хранения элементов и их соединений вам понадобится немного больше места в памяти, но это очень небольшая цена за дополнительные возможности.
В целом, благодаря тому, что родительский класс берет на себя всю основную работу, серьезных отличий в реализации нет. Хэшмап И LinkedHashMap Немного.
Можно упомянуть пару незначительных:
- Методы передача() И содержитЗначение() устроены немного проще за счет наличия двунаправленной связи между элементами;
- В классе LinkedHashMap.Entry реализованные методы записьУдаление() И записьДоступ() (тот, который помещает элемент в конец, когда Ордер доступа = истина ).
В Хэшмап оба эти метода пусты.
Ссылки
Источник LinkedHashMap Исходники JDK OpenJDK и trade 6 Source Release — сборка b23 Измерительные инструменты - измеритель памяти И Гуава (Основные библиотеки Google).
1 — Вызов метода RemoveEldestEntry(Map.Entry самый старый) всегда возвращается ЛОЖЬ .
Предполагается, что этот метод можно переопределить под любые нужды, например, для реализации структур кэширования на основе карта (см.
После удалитьЭлдестEntry() вернется истинный , самый старый элемент будет удален, когда будет достигнуто максимальное значение.
количество элементов.
Теги: #java #LinkedHashMap #структуры данных #java
-
Юлиан Флавий Клавдий
19 Oct, 24 -
Икра. Первый День
19 Oct, 24 -
Общие Исключения В Лямбда-Функциях
19 Oct, 24 -
Яндекс Даст Миллион За Хорошее Образование
19 Oct, 24 -
Почему Фантом?
19 Oct, 24
