Структури от данни в картини
От името можете да познаете, че тази структура е симбиоза от свързани списъци и хеш карти. Наистина LinkedHashMap разширява класа HashMap и имплементира интерфейса Map, но какво е толкова специалното на свързаните списъци? Нека да го разберем.
Създайте обект
Новосъздаденият обектlinkedHashMap, в допълнение към свойствата, наследени отHashMap(като table, loadFactor, threshold, size, entrySet и т.н.), също съдържа две допълнителни. свойства:
- headerе "главата" на двойно свързан списък. Сочи към себе си, когато се инициализира;
- accessOrder- указва как ще се осъществява достъп до елементите при използване на итератор. Ако стойността еtrue- по реда на последния достъп (повече за това в края на статията). Когато е зададено наfalse, достъпът се извършва в реда, в който са вмъкнати елементите.
Новият обект е създаден, свойствата са инициализирани, можете да продължите към добавяне на елементи.
Добавяне на елементи
Когато добавяте елемент, първо се извиква методътcreateEntry(hash, key, value, bucketIndex)(по веригатаput()->addEntry()->createEntry())
първите три реда добавят елемент (в случай на сблъсъци, добавянето ще се случи вначалото на веригата, ще видим по-късно)
четвъртият ред отменя връзките на двойно свързания списък
Всичко, което се случва след това в методаaddEntry()или не е от „функционален интерес“ 1 или повтаря функционалността на родителския клас.
Нека добавим още няколко елемента
При добавяне на следващия елемент възниква сблъсък и елементите с ключове 4 и 38 образуват верига
Бих искал да обърна внимание на факта, че ако елемент бъде вмъкнат отново (вече съществува елемент със същия ключ), редът на достъп до елементите няма да се промени.
accessOrder == вярно
Сега нека да разгледаме пример, при който свойствотоaccessOrderима стойностtrue. В такава ситуация поведението наLinkedHashMapсе променя и когато се извикат методитеget()иput(), редът на елементите ще бъде променен - елементът, до който се осъществява достъп, ще бъде поставен в края.
Всичко е доста банално:
И не забравяйте за бързото отказване. Ако вече сте започнали да изброявате елементи, не променяйте съдържанието или се погрижете за синхронизацията предварително.
Вместо суми
Тази структура може да е малко по-ниска по производителност от родителскатаHashMap, докато времето за изпълнение на операциитеadd(), contains(), remove()остава постоянно - O(1). Ще отнеме малко повече място в паметта за съхраняване на елементи и техните връзки, но това е много малка цена за допълнителни чипове.
Като цяло, поради факта, че родителският клас поема цялата основна работа, няма много сериозни разлики в имплементацията наHashMapиLinkedHashMap. Могат да се споменат няколко малки:
- Методиtransfer()иcontainsValue()са подредени малко по-просто поради наличието на двупосочна връзка между елементите;
- КласътLinkedHashMap.Entryимплементира методитеrecordRemoval()иrecordAccess()(този, който поставя елемента в края, когатоaccessOrder = true). ВHashMapи двата метода са празни.
1 – Извикването на методаremoveEldestEntry(Map.Entry eldest)винаги връщаfalse. Предполага се, че този метод може да бъде заменен за някои нужди, например за прилагане на кеширащи структури, базирани наMap(вижте ExpiringCache). След катоremoveEldestEntry()върнеtrue, най-старият елемент ще бъде премахнат, когато макс. броя на елементите.
И тук можете да получите грант за тестов период на Yandex.Cloud. Необходимо е само да въведете "Habr" в полето "секретна парола".