Ръководство за LinkedHashMap в Java

1. Общ преглед

В тази статия ще разгледаме вътрешното внедряване на класа LinkedHashMap . LinkedHashMap е често срещано изпълнение на интерфейса на Map .

Това конкретно изпълнение е подклас на HashMap и следователно споделя основните градивни елементи на изпълнението на HashMap . В резултат на това е силно препоръчително да се справите с това, преди да продължите с тази статия.

2. LinkedHashMap срещу HashMap

Класът LinkedHashMap е много подобен на HashMap в повечето аспекти. Свързаната хеш карта обаче се основава както на хеш таблица, така и на свързан списък, за да подобри функционалността на хеш картата.

Той поддържа двойно свързан списък, който преминава през всички негови записи в допълнение към основния масив с размер по подразбиране 16.

За да поддържа реда на елементите, свързаната хеш-карта модифицира класа Map.Entry на HashMap, като добавя указатели към следващия и предишния запис:

static class Entry extends HashMap.Node { Entry before, after; Entry(int hash, K key, V value, Node next) { super(hash, key, value, next); } }

Забележете, че класът Entry просто добавя два указателя; преди и след което му позволяват да се закачи за свързания списък. Отделно от това, той използва изпълнението на класа Entry на HashMap.

И накрая, не забравяйте, че този свързан списък определя реда на итерация, който по подразбиране е редът на вмъкване на елементи (ред на вмъкване).

3. Поръчка за вмъкване LinkedHashMap

Нека да разгледаме свързан екземпляр на хеш карта, който подрежда записите си според начина, по който са вкарани в картата. Той също така гарантира, че този ред ще се запази през целия жизнен цикъл на картата:

@Test public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect() { LinkedHashMap map = new LinkedHashMap(); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set 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 map = new LinkedHashMap(16, .75f, true);

Първият параметър е първоначалният капацитет, последван от коефициента на натоварване, а последният параметър е режимът на подреждане . Така че, като предадохме true , включихме реда за достъп, докато по подразбиране беше ред за вмъкване.

Този механизъм гарантира, че редът на итерация на елементите е редът, в който елементите са били последно достъпни, от най-малко наскоро достъпен до последно достъпен.

И така, изграждането на кеш с най-малко наскоро използвани (LRU) е доста лесно и практично с този вид карта. Успешната операция за пускане или получаване води до достъп до записа:

@Test public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() { LinkedHashMap 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 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 extends LinkedHashMap { 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 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 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 изпълнява основните операции на Map за добавяне, премахване и съдържане в постоянно време, стига хеш функцията да е добре оразмерена. Той също така приема нулев ключ, както и нулеви стойности.

Тази постоянна работа на LinkedHashMap обаче вероятно ще бъде малко по-лоша от постоянното време на HashMap поради добавените режийни разходи за поддържане на двойно свързан списък.

Итерацията върху изгледите на колекции на LinkedHashMap също отнема линейно време O (n), подобно на това на HashMap . От друга страна, линейното време на LinkedHashMap по време на итерация е по-добро от линейното време на HashMap .

Това е така, защото, за LinkedHashMap , н в O (N) е само на броя на записите в картата в зависимост от капацитета. Като има предвид, HashMap , п е капацитет и размера обобщи, О (размер + капацитет).

Коефициентът на натоварване и първоначалният капацитет са дефинирани точно както за HashMap . Имайте предвид обаче, че наказанието за избор на прекалено висока стойност за първоначален капацитет е по-малко строго за LinkedHashMap, отколкото за HashMap , тъй като времената на итерации за този клас не се влияят от капацитета.

6. Съвпадение

Точно като HashMap , внедряването на LinkedHashMap не се синхронизира. Така че, ако ще имате достъп до нея от множество нишки и поне една от тези нишки вероятно ще я промени структурно, тогава тя трябва да бъде синхронизирана отвън.

Най-добре е да направите това при създаването:

Map m = Collections.synchronizedMap(new LinkedHashMap());

Разликата с HashMap се крие в това, което води до структурна модификация. В свързани с хеш карти, наредени за достъп, само извикването на API на get води до структурна модификация . Успоредно с това са операции като поставяне и премахване .

7. Заключение

В тази статия проучихме класа Java LinkedHashMap като една от най-важните реализации на интерфейса на Map по отношение на използването. Проучихме и вътрешната му работа по отношение на разликата от HashMap, която е неговият суперклас.

Надяваме се, че след като прочетете тази публикация, можете да вземете по-информирани и ефективни решения относно това коя реализация на картата да използвате във вашия случай на използване.

Пълният изходен код за всички примери, използвани в тази статия, може да бъде намерен в проекта GitHub.