Java LinkedHashMap detaljno (sa izvornim kodom)

Ovaj članak nastavljamo u drugačijem stilu, radi malo svežine.

Kažu da „ni zlato nije sasvim čisto, ni čovek savršen” — ni HashMap nije izuzetak. Jednu potrebu on ne može da zadovolji: ako nam treba kolekcija parova ključ-vrednost uređena po redosledu umetanja, HashMap tu ne može da pomogne. Šta onda? Obavezno moramo na scenu dovesti današnjeg glavnog junaka — LinkedHashMap.

Zdravo svima, da li se sećate članka o HashMap? Lično mislim da je ispao odlično — i pristupačan i uz detaljno pronicanje u izvorni kod, zaista temeljna analiza. (Eto, opet nabrah tri prideva — vidite kako sam pismen?) HashMap je dobar u svemu — zaista, čim pomislite na parove ključ-vrednost, prvo što vam pada na pamet treba da bude on.

Da bi povećao efikasnost pretrage, HashMap pri umetanju nad ključem primenjuje heš algoritam, zbog čega su umetnuti elementi neuređeni.

Kome ovo i dalje nije jasno, neka se vrati na članak o HashMap, pogleda metod hash i moj komentar metode put() — brzo će mu pasti na pamet. Ovde ćemo samo ukratko podsetiti.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

               boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
    // ①. Kada je niz table null, pozivamo resize da kreiramo niz podrazumevane dužine
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // ②. Izračunavamo indeks; ako na toj poziciji nema vrednosti, popunjavamo je
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
}

Vrednost izraza i = (n - 1) & hash je indeks (pozicija) ključa u nizu (kofa), ali se parovi ključ-vrednost ne ubacuju po uređenim indeksima 0, 1, 2, 3, 4, 5, već uz izvesnu slučajnost.

Na primer, u HashMap-u podrazumevane dužine 16, kada se pozove put sa 4 para ključ-vrednost, indeksi mogu biti 0, 4, 9, 11 — pri čemu pri obilasku HashMap-a redosled ne mora odgovarati redu umetanja.

Pogledajte sledeći primer.

// Kreiramo HashMap čiji su i ključ i vrednost tipa String
Map<String, String> map = new HashMap<>();

// Dodajemo podatke u HashMap metodom put()
map.put("chenmo", "Chenmo");
map.put("wanger", "Wang Er");
map.put("chenqingyang", "Chen Qingyang");

// Obilazimo HashMap i ispisujemo sve parove ključ-vrednost
for (Map.Entry<String, String> entry : map.entrySet()) {
    String key = entry.getKey();
    String value = entry.getValue();
    System.out.println("Key: " + key + ", Value: " + value);
}

Pogledajmo rezultat ispisa:

Key: chenmo, Value: Chenmo
Key: chenqingyang, Value: Chen Qingyang
Key: wanger, Value: Wang Er

Ako uporedimo rezultat, vidi se da je pri pozivu put redosled bio Chenmo, Wang Er, Chen Qingyang, ali pri obilasku redosled nije poštovan: Chenmo, Chen Qingyang, Wang Er — jer je HashMap neuređen.

Kako onda obezbediti redosled umetanja parova ključ-vrednost?

LinkedHashMap je nastao baš da odgovori na tu potrebu. LinkedHashMap nasleđuje HashMap, pa ima sve funkcije nad parovima ključ-vrednost koje ima i HashMap.

public class LinkedHashMap<K,V>

    extends HashMap<K,V>

    implements Map<K,V>{}

Pored toga, LinkedHashMap interno dodaje dvostruko povezanu listu koja održava redosled umetanja elemenata. Obratite pažnju na polja before i after u kodu ispod — oni služe baš za održavanje redosleda prethodnog i sledećeg elementa u odnosu na trenutni.

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);
    }
}

Za dvostruko povezanu listu možete pogledati moj članak o LinkedList — dosta će vam pomoći u razumevanju LinkedHashMap-a.

Zamenimo HashMap sa LinkedHashMap i ponovo uporedimo rezultate.

// Kreiramo LinkedHashMap čiji su i ključ i vrednost tipa String
Map<String, String> map = new LinkedHashMap<>();

// Dodajemo podatke u LinkedHashMap metodom put()
map.put("chenmo", "Chenmo");
map.put("wanger", "Wang Er");
map.put("chenqingyang", "Chen Qingyang");

// Obilazimo LinkedHashMap i ispisujemo sve parove ključ-vrednost
for (Map.Entry<String, String> entry : map.entrySet()) {
    String key = entry.getKey();
    String value = entry.getValue();
    System.out.println("Key: " + key + ", Value: " + value);
}

Pogledajmo rezultat:

Key: chenmo, Value: Chenmo
Key: wanger, Value: Wang Er
Key: chenqingyang, Value: Chen Qingyang

Vidite, LinkedHashMap je zadržao redosled umetanja? Tako je.

01,Redosled umetanja

U članku o HashMap pomenuo sam jednu stvar — ne znam da li se sećate: vrednost null umeće se na prvo mesto u HashMap-u.

Map<String, String> hashMap = new HashMap<>();
hashMap.put("chen", "Chenmo Wang Er");
hashMap.put("mo", "Chenmo Wang Er");
hashMap.put("wang", "Chenmo Wang Er");
hashMap.put("er", "Chenmo Wang Er");
hashMap.put(null, null);

for (String key : hashMap.keySet()) {
    System.out.println(key + " : " + hashMap.get(key));
}

Rezultat ispisa je:

null : null
mo : Chenmo Wang Er
chen : Chenmo Wang Er
wang : Chenmo Wang Er
er : Chenmo Wang Er

Iako je null unešen kao poslednji, pri obilasku i ispisu on se pojavljuje na prvom mestu.

A sada da uporedimo LinkedHashMap.

Map<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("chen", "Chenmo Wang Er");
linkedHashMap.put("mo", "Chenmo Wang Er");
linkedHashMap.put("wang", "Chenmo Wang Er");
linkedHashMap.put("er", "Chenmo Wang Er");
linkedHashMap.put(null, null);

for (String key : linkedHashMap.keySet()) {
    System.out.println(key + " : " + linkedHashMap.get(key));
}

Rezultat ispisa je:

chen : Chenmo Wang Er
mo : Chenmo Wang Er
wang : Chenmo Wang Er
er : Chenmo Wang Er
null : null

null je unešen poslednji i ispisan je poslednji.

Rezultat još jednom potvrđuje da HashMap ne održava redosled, dok LinkedHashMap može da održava redosled umetanja.

Kako LinkedHashMap to postiže? Verujem da, kao i ja, veoma želite da saznate razlog.

Da bismo to razjasnili, moramo dublje proučiti izvorni kod LinkedHashMap-a. LinkedHashMap nije redefinisao metod put() iz HashMap-a, već je redefinisao interni metod newNode() koji put() poziva.

Ovo je metod iz HashMap-a.

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

A ovo je iz LinkedHashMap-a.

HashMap.Node<K,V> newNode(int hash, K key, V value, HashMap.Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

Ranije smo pomenuli da LinkedHashMap.Entry nasleđuje HashMap.Node i dodaje dva polja, before i after, koja održavaju odnose među parovima ključ-vrednost.

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);
    }
}

U LinkedHashMap-u se redosled čvorova u listi održava prema redu umetanja. Kada se metodom put() doda par ključ-vrednost, novi čvor se umeće na kraj liste i ažuriraju se polja before i after kako bi se očuvao redosled — ovo obavlja metod linkNodeLast():

/**
 * Umeće zadati čvor na kraj liste
 *
 * @param p čvor koji se umeće
 */
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail; // uzimamo repni čvor liste
    tail = p; // postavljamo p kao repni čvor
    if (last == null)
        head = p; // ako je lista prazna, p postaje glavni čvor
    else {
        p.before = last; // prethodnik čvora p postaje repni čvor liste
        last.after = p; // sledbenik repnog čvora liste postaje p
    }
}

Vidite? Kada LinkedHashMap doda prvi element, head se postavlja na taj prvi element; kada se doda drugi, before drugog elementa postaje prvi element, a after prvog elementa postaje drugi element.

Tako je zagarantovan redosled parova ključ-vrednost po redu umetanja — jasno, zar ne?

02,Redosled pristupa

LinkedHashMap ne samo da održava redosled umetanja, već i redosled pristupa. Pristup obuhvata pozive metoda get(), remove() i put().

Da bi se održavao redosled pristupa, prilikom deklaracije LinkedHashMap potrebno je navesti tri parametra.

LinkedHashMap<String, String> map = new LinkedHashMap<>(16, .75f, true);

Prva dva parametra su već poznata onima koji su čitali članak o HashMap — to su početni kapacitet i faktor opterećenja.

Ako je treći parametar true, LinkedHashMap održava redosled pristupa; inače, održava redosled umetanja. Podrazumevana vrednost je false.

Map<String, String> linkedHashMap = new LinkedHashMap<>(16, .75f, true);
linkedHashMap.put("chen", "Chenmo Wang Er");
linkedHashMap.put("mo", "Chenmo Wang Er");
linkedHashMap.put("wang", "Chenmo Wang Er");
linkedHashMap.put("er", "Chenmo Wang Er");

System.out.println(linkedHashMap);

linkedHashMap.get("mo");
System.out.println(linkedHashMap);

linkedHashMap.get("wang");
System.out.println(linkedHashMap);

Rezultat ispisa je sledeći:

{chen=Chenmo Wang Er, mo=Chenmo Wang Er, wang=Chenmo Wang Er, er=Chenmo Wang Er}
{chen=Chenmo Wang Er, wang=Chenmo Wang Er, er=Chenmo Wang Er, mo=Chenmo Wang Er}
{chen=Chenmo Wang Er, er=Chenmo Wang Er, mo=Chenmo Wang Er, wang=Chenmo Wang Er}

Kada metodom get() pristupimo elementu pod ključem „mo”, u rezultatu ispisa par mo=Chenmo Wang Er dolazi na kraj; kada pristupimo elementu pod ključem „wang”, par wang=Chenmo Wang Er dolazi na kraj, a mo=Chenmo Wang Er na pretposlednje mesto.

Drugim rečima, ono čemu se najređe pristupa nalazi se na početku — i tu postaje zanimljivo. Na šta mi to ciljamo?

03,LRU keš

LinkedHashMap možemo iskoristiti za realizaciju LRU keša. LRU je skraćenica od Least Recently Used — „najmanje korišćeno”. To je uobičajen algoritam za zamenu stranica koji bira stranicu kojoj se najduže nije pristupalo i nju izbacuje.

/**
 * Prilagođena klasa MyLinkedHashMap koja nasleđuje ugrađenu LinkedHashMap<K, V>.
 * Služi za realizaciju keša fiksne veličine — kada keš dostigne maksimalni kapacitet,
 * automatski se uklanja najranije dodat element, čime se oslobađa mesto za novi.
 *
 * @param <K> tip ključa
 * @param <V> tip vrednosti
 */
public class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V> {

    private static final int MAX_ENTRIES = 5; // najveći broj parova ključ-vrednost u MyLinkedHashMap

    /**
     * Konstruktor — poziva super() sa tri parametra: initialCapacity, loadFactor i accessOrder.
     *
     * @param initialCapacity početni kapacitet
     * @param loadFactor      faktor opterećenja
     * @param accessOrder     redosled pristupa
     */
    public MyLinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor, accessOrder);
    }

    /**
     * Redefinicija metode removeEldestEntry() iz nadklase — ukazuje na to da li treba ukloniti najranije dodat element.
     * Ako vrati true, najranije dodat element se briše.
     *
     * @param eldest najranije dodat element
     * @return true ako broj elemenata u MyLinkedHashMap prelazi MAX_ENTRIES, inače false.
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

}

MyLinkedHashMap je prilagođena klasa koja nasleđuje LinkedHashMap i redefiniše metod removeEldestEntry() — Map tako može da primi najviše 5 elemenata, a nakon toga najstariji se izbacuje.

Testirajmo to.

MyLinkedHashMap<String,String> map = new MyLinkedHashMap<>(16,0.75f,true);
map.put("chen", "Chenmo Wang Er");
map.put("mo", "Chenmo Wang Er");
map.put("wang", "Chenmo Wang Er");
map.put("er", "Chenmo Wang Er");
map.put("zanimljiv programer", "Zanimljiv programer");

System.out.println(map);

map.put("lep programer", "Lep programer");
System.out.println(map);

map.put("talentovan programer","Talentovan programer");
System.out.println(map);

Rezultat ispisa je sledeći:

{chen=Chenmo Wang Er, mo=Chenmo Wang Er, wang=Chenmo Wang Er, er=Chenmo Wang Er, zanimljiv programer=Zanimljiv programer}
{mo=Chenmo Wang Er, wang=Chenmo Wang Er, er=Chenmo Wang Er, zanimljiv programer=Zanimljiv programer, lep programer=Lep programer}
{wang=Chenmo Wang Er, er=Chenmo Wang Er, zanimljiv programer=Zanimljiv programer, lep programer=Lep programer, talentovan programer=Talentovan programer}

chen=Chenmo Wang Er i mo=Chenmo Wang Er su redom izbačeni.

Ako pre nego što umetnemo „talentovan programer” pozovemo get nad ključem „mo”:

MyLinkedHashMap<String,String> map = new MyLinkedHashMap<>(16,0.75f,true);
map.put("chen", "Chenmo Wang Er");
map.put("mo", "Chenmo Wang Er");
map.put("wang", "Chenmo Wang Er");
map.put("er", "Chenmo Wang Er");
map.put("zanimljiv programer", "Zanimljiv programer");

System.out.println(map);

map.put("lep programer", "Lep programer");
System.out.println(map);

map.get("mo");
map.put("talentovan programer","Talentovan programer");
System.out.println(map);

Rezultat ispisa se menja, zar ne?

{chen=Chenmo Wang Er, mo=Chenmo Wang Er, wang=Chenmo Wang Er, er=Chenmo Wang Er, zanimljiv programer=Zanimljiv programer}
{mo=Chenmo Wang Er, wang=Chenmo Wang Er, er=Chenmo Wang Er, zanimljiv programer=Zanimljiv programer, lep programer=Lep programer}
{er=Chenmo Wang Er, zanimljiv programer=Zanimljiv programer, lep programer=Lep programer, mo=Chenmo Wang Er, talentovan programer=Talentovan programer}

chen=Chenmo Wang Er i wang=Chenmo Wang Er su izbačeni.

Kako LinkedHashMap održava redosled pristupa? Zainteresovani čitaoci mogu proučiti sledeće tri metode.

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

afterNodeAccess() se poziva prilikom poziva metode get(), afterNodeInsertion() prilikom poziva metode put(), a afterNodeRemoval() prilikom poziva metode remove().

Objasniću to na primeru metode afterNodeAccess().

/**
 * Nakon pristupa čvoru, pomera ga na kraj liste
 *
 * @param e čvor koji se pomera
 */
void afterNodeAccess(HashMap.Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) { // ako važi redosled pristupa i čvor kojem se pristupa nije repni
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null; // sledbenik čvora koji se pomera postaje null
        if (b == null)
            head = a; // ako čvor koji se pomera nema prethodnika, sledbenik postaje glavni čvor
        else
            b.after = a; // sledbenik prethodnika čvora koji se pomera postaje sledbenik tog čvora
        if (a != null)
            a.before = b; // ako čvor koji se pomera ima sledbenika, prethodnik sledbenika postaje prethodnik čvora koji se pomera
        else
            last = b; // ako čvor koji se pomera nema sledbenika, prethodnik tog čvora postaje repni čvor
        if (last == null)
            head = p; // ako je repni čvor null, čvor koji se pomera postaje glavni čvor
        else {
            p.before = last; // prethodnik čvora koji se pomera postaje repni čvor
            last.after = p; // sledbenik repnog čvora postaje čvor koji se pomera
        }
        tail = p; // čvor koji se pomera postaje repni čvor
        ++modCount; // brojač izmena
    }
}

Koji god element se get-uje, taj element se pomera na kraj. Jasno?

Čitaoce sigurno zanima i zašto LinkedHashMap može da realizuje LRU keš i izbaci element kojem se najređe pristupa.

Pri umetanju elementa poziva se metod put(), koji na kraju poziva metod afterNodeInsertion(), a taj metod je LinkedHashMap redefinisao.

/**
 * Nakon umetanja čvora, po potrezi može obrisati najranije dodat element
 *
 * @param evict indikator da li treba obrisati najranije dodat element
 */
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) { // ako treba obrisati najranije dodat element
        K key = first.key; // ključ elementa koji se briše
        removeNode(hash(key), key, null, false, true); // brisanje elementa metodom removeNode()
    }
}

Metod removeEldestEntry() proverava da li prvi element prelazi maksimalni dozvoljeni opseg; ako prelazi, poziva se removeNode() kojim se briše element kojem se najređe pristupa.

04,Kratak pregled

Pošto LinkedHashMap održava dvostruko povezanu listu, operacije umetanja i brisanja kod njega zahtevaju nešto više vremena nego kod HashMap-a.

Ali to se ne može izbeći, zar ne — ko hoće da nosi krunu, mora da nosi i njen teret. Pošto želimo da održavamo redosled elemenata, moramo platiti nekog cenku.

Da ukratko sumiramo.

Prvo, znamo da je HashMap uobičajena struktura podataka heš tabele koja brzo obavlja pretragu i umetanje parova ključ-vrednost. Ali HashMap sam po sebi ne garantuje redosled parova; ako nam je potrebno da ih obilazimo po redu umetanja ili pristupa, koristimo LinkedHashMap.

LinkedHashMap nasleđuje HashMap i u njega dodaje dvostruko povezanu listu koja održava redosled parova ključ-vrednost. Ta lista može biti uređena po redu umetanja ili po redu pristupa — njen glavni čvor predstavlja najranije umetnuti, odnosno njemu pristupano element, a repni čvor najkasnije. Uloga liste je da omogući LinkedHashMap-u da održava redosled parova i da ih obilazi tim redom.

LinkedHashMap nudi i dva konstruktora kojima se bira način sortiranja — po redu umetanja ili po redu pristupa. Pri sortiranju po redu pristupa, svaki pristup paru ključ-vrednost pomera taj par na kraj liste, tako da najskorije pristupani elementi ostaju na kraju. Ako je potrebno ukloniti najranije dodat element, dovoljno je redefinisati metod removeEldestEntry().

Ukratko, LinkedHashMap održavanjem dvostruko povezane liste čuva redosled parova ključ-vrednost i može ih obilaziti po redu umetanja ili po redu pristupa. Ako treba da obilazite parove zadatim redom, LinkedHashMap je pravi izbor za vas!