LinkedHashMap (mapa): Dátová štruktúra linked hashmap v Jave
Java LinkedHashMap spája rýchlosť hašovacej tabuľky s prehľadnosťou poradia vkladaných položiek. Preto je ideálnym riešením, keď potrebuješ rýchlu mapu s garantovaným poradím vložených položiek. Pozri si jej použitie v simulácii nákupného košíka.
V článku sa dozvieš:
Pojem linked hashmap je všeobecné označenie mapy, ktorá si pamätá poradie vloženia (prípadne prístupu). LinkedHashMap je konkrétna trieda v balíku java.util, ktorá implementuje toto správanie v Jave. Trieda LinkedHashMap kombinuje vlastnosti HashMap a LinkedList na uchovávanie kľúč-hodnota dvojíc s garantovaným poradím vkladania.
Java LinkedHashMap je jednou z množstva dátových štruktúr na jednoduchšiu prácu s dátami. V našom seriáli si postupne predstavíme aj rôzne ďalšie dátové štruktúry. Ukážeme si, ako s nimi pracovať, aké operácie sa s nimi dajú robiť, aké sú najčastejšie používané metódy. Spomenieme výhody a nevýhody a kedy je vhodné konkrétnu dátovú štruktúru použiť.
LinkedHashMap v Java – predstavenie dátovej štruktúry
LinkedHashMap sa nachádza v balíku java.util a rozširuje HashMap a implementuje rozhranie Map. Na rozdiel od dátovej štruktúry HashMap, ktorá nezaručuje poradie iterácie, LinkedHashMap udržiava poradie vloženia prvkov. To znamená, že pri iterácii cez mapu sa prvky zobrazia v poradí, v akom boli pridané.
Táto vlastnosť je dosiahnutá pomocou obojstranne prepojeného zoznamu, ktorý spája všetky záznamy mapy v poradí ich vloženia. Najskôr vložený prvok je prvý a naposledy vložený prvok je posledný, dôležité je ale spomenúť, že ak vkladáme prvok s rovnakým (už existujúcim) kľúčom cez put-metódu, poradie prvkov zostáva nezmenené. Poradie prvkov, ale dokážeme zmeniť pomocou iných put-metód ako je napr. putFirst a putLast. Hodnoty null sú v LinkedHashMap povolené.
LinkedHashMap – konštruktory
Pre vytvorenie inštancie LinkedHashMap môžeme použiť jeden z nasledujúcich konštruktorov:
1. Prázdna LinkedHashMap s predvolenou kapacitou a faktorom zaťaženia
Vytvorí prázdnu LinkedHashMap s predvolenou počiatočnou kapacitou (16) a faktorom zaťaženia (0.75).
LinkedHashMap<K, V> map = new LinkedHashMap<>();2. LinkedHashMap s určenou počiatočnou kapacitou
Vytvorí prázdnu LinkedHashMap s určenou počiatočnou kapacitou a predvoleným faktorom zaťaženia (0.75).
LinkedHashMap<K, V> map = new LinkedHashMap<>(int initialCapacity);3. LinkedHashMap s určenou počiatočnou kapacitou a faktorom zaťaženia
Vytvorí prázdnu LinkedHashMap s určenou počiatočnou kapacitou a faktorom zaťaženia.
LinkedHashMap<K, V> map = new LinkedHashMap<>(int initialCapacity, float loadFactor);4. LinkedHashMap s určenou počiatočnou kapacitou, faktorom zaťaženia a režimom prístupu
Vytvorí prázdnu LinkedHashMap s určenou počiatočnou kapacitou. faktorom zaťaženia a režimom prístupu
LinkedHashMap<K, V> map = new LinkedHashMap<>(int initialCapacity, float loadFactor, boolean accessOrder);5. LinkedHashMap skonštruovaný z Map
Vytvorí novú hašovaciu tabuľku s rovnakým poradím vložených prvkov a mapovaním ako špecifikovaná mapa.
LinkedHashMap<K, V> map = new LinkedHashMap<>(Map<? extends K, ? extends V> m);Režim prístupu (access order)
Pri jednom z konštruktorov môžeme špecifikovať aj vstupný parameter accessOrder – režim prístupu. Ak je accessOrder nastavený na true, iterácia cez prvky bude založená na poradí prístupu (od najstaršieho po najnovšie použité záznamy). Predvolená hodnota je ale false, čo znamená, že iterácia bude v poradí vloženia prvkov.
LinkedHashMap – základné operácie
K základným operáciám s LinkedHashMap patria:
- Vkladanie prvkov
Použitím metódy put(K key, V value) pridáme nový záznam do mapy. Ak kľúč už existuje, jeho hodnota bude prepísaná.
Metóda putAll(Map<? extends K, ? extends V> m) pridá všetky záznamy z inej mapy. - Prístup k hodnotám
Metóda get(Object key) vráti hodnotu priradenú k danému kľúču alebo null, ak kľúč neexistuje.
Metóda getOrDefault(Object key, V defaultValue) vráti hodnotu priradenú k danému kľúču alebo predvolenú hodnotu, ak kľúč neexistuje. - Odstraňovanie prvkov
Metóda remove(Object key) odstráni záznam s daným kľúčom.
Metóda clear() odstráni všetky záznamy z mapy. - Test prázdnosti
Metóda isEmpty() nám zistí, či LinkedHashMap obsahuje nejaký záznam. - Kontrola existencie kľúča alebo hodnoty
Metóda containsKey(Object key) vráti true, ak mapa obsahuje daný kľúč. - Metóda containsValue(Object value) vráti true, ak mapa obsahuje danú hodnotu.
- Zistenie veľkosti
Metóda size() vráti počet všetkých záznamov v tabuľke. - Iterácia cez prvky
Použitím metódy entrySet() získame množinu záznamov <Map.Entry>, cez ktorú môžeme iterovať.
Metódy keySet() a values() vrátia množinu kľúčov a kolekciu hodnôt, cez ktoré môžeme tiež iterovať.
LinkedHashMap – dokumentácia
Kompletný prehľad metód triedy LinkedHashMap, nájdeš v oficiálnej dokumentácii.
Výhody LinkedHashMap – výhody a nevýhody
Výhody LinkedHashMap
- Zachováva poradie vloženia
Na rozdiel od HashMap, ktorá nemá žiadne poradie, LinkedHashMap uchováva prvky v poradí, v akom boli pridané. - Možnosť nastavenia prístupu podľa použitia
S nastavením (accessOrder = true) umožňuje triedenie podľa naposledy použitého prvku, čo je ideálne pre cache mechanizmy (napr. LRU cache) - Rýchlosť porovnateľná s HashMap
Vkladanie, odstraňovanie a vyhľadávanie má O(1) časovú zložitosť, pretože je založená na hash tabuľke. - Možnosť odstrániť najstaršie záznamy
Metóda removeEldestEntry umožňuje automatické odstránenie najstarších položiek, čo je výhodné pre históriu prihlásení, caching a logovanie.
Nevýhody LinkedHashMap
- Vyššia pamäťová náročnosť
Okrem samotnej hash tabuľky LinkedHashMap udržiava aj prepojené zoznamy medzi prvkami (dvojitý zoznam), čo znamená vyššiu spotrebu pamäte v porovnaní s HashMap. - Nie je synchronizovaná
Rovnako ako HashMap, ani LinkedHashMap nie je bezpečná pre viacvláknové operácie, takže pri práci v multithreadingu treba použiť Collections.synchronizedMap(). - Citlivosť na implementáciu hashCode a equals
Ak trieda, ktorú ukladáme ako prvok, nemá správne implementované metódy hashCode() a equals(), môže to viesť k neočakávanému správaniu a zníženiu výkonu. - Výkon v prípade kolízií
Pri veľkom počte kolízií (keď viaceré prvky majú rovnaký hash kód) môže dôjsť k zníženiu výkonu, pretože operácie sa môžu správať pomalšie.
LinkedHashMap – kedy ju použiť a kedy nie?
LinkedHashMap je vhodná v nasledovných prípadoch:
- Keď potrebujeme uchovať poradie vkladania prvkov.
- Keď chceme vytvoriť cache so stratégiou odstránenia najstarších položiek (LRU Cache).
Naopak, nie je vhodná:
- Ak nám nezáleží na poradí, potom použi radšej HashMap, ktorá šetrí pamäť.
- Ak potrebujeme prvky zoradiť podľa kľúča, použi TreeMap.
- Ak potrebujeme synchronizáciu, použi ConcurrentHashMap.
Príklad použitia LinkedHashMap v Jave
Hashovacie mapy majú všestranné použitie. LinkedHashMap vyniká efektívnym ukladaním dvojíc kľúč-hodnota a ich rýchlym vyhľadaním vďaka hashovacej metóde, keď ich potrebujeme načítať a použiť. Navyše uchováva prvky v poradí, v akom boli pridané.
Ako príklad pre reálne využitie dátovej štruktúry LinkedHashMap som si zvolil simuláciu nákupného košíka. Pre vložený tovar do košíku si budeme ukladať názov tovaru a jeho množstvo. Aj keby sme mohli použiť HashMap, v takomto prípade je vhodnejšie použiť LinkedHashMap, pretože nakupujúci by mohol požadovať výpis (faktúru) s položkami presne v takom poradí, ako ich vložil do košíka. Tento príklad demonštruje základné metódy ako napríklad put(), get(), containsKey(), remove() a iterovanie cez položky.
ShoppingCart.java
import java.util.LinkedHashMap;
import java.util.Map;
public class ShoppingCart {
// LinkedHashMap to store product name and its quantity.
private LinkedHashMap<String, Integer> cart;
public ShoppingCart() {
// Create an instance of LinkedHashMap.
cart = new LinkedHashMap<>();
}
// Method to add a product to the shopping cart.
public void addProduct(String product, int quantity) {
// If the product already exists, update the quantity.
if (cart.containsKey(product)) {
cart.put(product, cart.get(product) + quantity);
} else {
cart.put(product, quantity);
}
}
// Method to remove a product from the shopping cart.
public void removeProduct(String product) {
if (cart.containsKey(product)) {
cart.remove(product);
} else {
System.out.println("Product \"" + product + "\" does not exist in the cart.");
}
}
// Method to update the quantity of an existing product.
public void updateProduct(String product, int quantity) {
if (cart.containsKey(product)) {
cart.put(product, quantity);
} else {
System.out.println("Product \"" + product + "\" does not exist in the cart.");
}
}
// Method to display the contents of the shopping cart.
public void displayCart() {
System.out.println("Shopping cart contains products:");
for (Map.Entry<String, Integer> entry : cart.entrySet()) {
System.out.println(entry.getKey() + ", " + entry.getValue() + "pcs");
}
}
public static void main(String[] args) {
// Create an instance of the shopping cart.
ShoppingCart shoppingCart = new ShoppingCart();
// Adding products to the cart.
shoppingCart.addProduct("Bread", 1);
shoppingCart.addProduct("Milk", 5);
shoppingCart.addProduct("Chocolate", 2);
shoppingCart.addProduct("Bananas", 3);
// Display the current state of the cart.
shoppingCart.displayCart();
// Update the quantity for Milk.
System.out.println("\nUpdating quantity for Milk:");
shoppingCart.updateProduct("Milk", 4);
shoppingCart.displayCart();
// Remove the product Pears.
System.out.println("\nRemoving product Bananas:");
shoppingCart.removeProduct("Bananas");
shoppingCart.displayCart();
}
}Výstup z tohto príkladu je:
Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si Java kód pre LinkedHashMap tu.
