Java (20) - Hashovací tabulka

V předešlých dílech jsme mimo jiné vytvářeli kolekce – dynamické pole a spojový seznam. Jejich použití nám oproti práci s polem v mnohém usnadnilo práci, zejména pak pokud jde o ukládání dat předem neznámé délky. Jedna otázka ovšem zůstala otevřená – vyhledávání.

Vyhledávání

Seznam

Představme si, že vytváříme evidenci obyvatel nějakého státu. Prvním řešením, které nás napadne, je uložit všechny obyvatele do seznamu. Pokud budeme chtít zjistit, zda-li daný obyvatel existuje nebo žije, tak celý seznam jednoduše projdeme.

Toto řešení bude perfektně fungovat pro malé státy (Monaco, San Marino...), u těch středně velkých jako je Česká republika se již začne projevovat sekvenčnost prohledávání – v krajním případě nutnost projít každého jednotlivého obyvatele v evidenci. U velmi lidnatých států (Čína, Indie) již bude toto řešení zcela selhávat.

Pole

Alternativně bychom mohli všechny obyvatele umístit do pole, ve kterém bychom vyhledávali pomocí identifikačního čísla obyvatele (rodné číslo, číslo pojistky...). Pokud by identifikační číslo mělo 10 číslic, tak bychom vytvořili pole o velikosti $10^{10}$ (10 miliard). Jednotlivé prvky bychom potom vyhledávali přímo přes příslušný index (tj. s konstantní složitostí O(1) ).

Nevýhoda tohoto přístupu je zřejmá – pro velké státy s miliardou obyvatel promrháme $90\\%$ prostoru pole, pro pro středně velké pak přes 99 procent, u malých států bychom si ani nevšimli, že tam nějaká data jsou...

Hashovací tabulka

Hashovací (rozptýlená) tabulka je struktura postavená nad polem, jež slouží k ukládání dvojic klíč-hodnota, a která kombinuje výhody obou předchozích přístupů – umožňuje vyhledat prvek pomocí průměrně konstantního počtu operací a nevyžaduje velké množství dodatečné (nevyužité) paměti.

Hashovací funkce

Jádrem hashovací tabulky je využití tzv. hashovací funkce, která vypočte pro předaný klíč adresu v rozsahu pole, na níž bude příslušný prvek uložen.

Hashovací funkce má následující vlastnosti:

Konzistentně vrací pro stejné objekty (klíče) stejné adresy (slovo stejné typicky neznamená stejné instance, ale stejná data).
Nezaručuje, že pro dva různé objekty vrátí různou adresu.
Využívá celého prostoru adres se stejnou pravděpodobností.
Výpočet adresy proběhne velmi rychle.

Jelikož funkce dle první vlastnosti vrací konzistentně pro stejný klíč stejnou adresu, lze uložený objekt vyhledat stejným postupem, jakým byl uložen.

Kolize

Dle druhé vlastnosti hashovacích funkcí může dojít k tomu, že dva různé objekty (klíče) dostanou stejnou adresu. Této situaci se říká kolize. Kolize se dá řešit mnoha způsoby, my si ale ukážeme jeden poměrně jednoduchý postup, který ale dosahuje na řídkých tabulkách velmi dobrého výkonu – linear probing.

Linear probing

Linear probing řeší koliza následovně. Je-li adresa (vypočtené místo) obsazená, tak jednoduše zkusí následujíci pozici. Takto postupuje tak dlouho, dokud se mu položku nepodaří uložit (tj. nenarazí na prázdnou buňku). Z jednoduchosti postupu ale plyne také jedna nevýhoda – shlukování (clustering).

Shlukování

Shlukování znamená, že v tabulce vznikají dlouhé jednolité sekvence uložených prvků, v rámci kterých mohou být vypočtené klíče různě pomíchané. Pro nalezení (nebo vyloučení existence) prvku je pak často nutné projít velké množství buňek, což notně degraduje výkon. Naštěstí bylo dokázáno, že k největší degradaci dochází až při zaplnění tabulky z více než $75\\%$ . Stačí tedy tabulku včas natáhnout (a prvky do nové tabulky znovu uložit).

Mazání prvků

Vzhledem k promíchanosti shluků nelze mazaný prvek pouze jednoduše odstranit (nahradit ukazatelem na null), protože by se při vyhledávání stal zbytek shluku nedostupným (vyhledávání je ukončeno při nalezení prvního volného místa). Stejně tak nelze zbytek shluku pouze posunout o jedno místo doleva, protože ve zbytku shluku může existovat prvek, který leží právě na své správné adrese a tento by byl po přesunutí nenávratně ztracen.

Při mazání prvků můžeme postupovat následujícími dvěma způsoby. Tím prvním je zbytek shluku odstranit a znovu uložit. Druhým způsobem je vložit místo smazaného prvku speciální objekt hlídky (sentinel), který je při vyhledávání ignorován (přeskočen), ale při vkládání nového prvku je považován za prázdné místo (a je nahrazen).

Hashovací funkce

Každý javovský objekt obsahuje metodu hashCode (dokumentace), která vrací, v souladu s vlasnostmi hashovací funkce uvedenými výše, celé číslo – hash.

Tuto funkci jsme zmínili již v sedmém dílu, ve kterém jsme překrývali metodu equals. Řekli jsme si tehdy, že mezi těmito dvěma metodami existuje užší vazba. Tato vazba je specifikována pomocí dokumentačního komentáře v třídě Object, v níž jsou obě zmíněné metody deklarovány, a uvaluje funci hashCode následující omezení:

Za předpokladu, že nebyla v objektu změněna žádná informace využívaná metodou equals, tak volání funkce hashCode v rámci jednoho běhu aplikace vrátí vždy stejný výsledek. Tento výsledek se může lišit v rámci jednotlivých běhů aplikace.
Pokud jsou dva objekty totožné dle metody equals, tak hashCode musí pro oba vrátit stejný výsledek.
Pokud dva objekty nejsou totožné, tak hashCode nemusí vrátit různý výsledek.

Příklad

V sedmém dílu jsme vytvářeli třídu zvířátka, které mělo druh a vydávalo různé zvuky. Dva objekty reprezentovaly to samé zvířátko právě tehdy, měly-li uvedené stejný druh a produkovaný zvuky.

Java

/**
 * Zviratko (v kodu jsou uvedeny pouze relevantni pasaze, zbytek je vyteckovan)
 * @author Pavel Micka
 */
public class Animal {
    /**
     * Druh zviratka
     */
    private String kind;
    /**
     * Zvuk, ktery zviratko vydava
     */
    private String sound;
    .
    .
    .
    @Override
    public boolean equals(Object obj) {
        if(obj instanceof Animal){ //je stejneho typu
            Animal animal = (Animal) obj; //muzeme tedy pretypovat
            if(this.kind.equals(animal.kind) && this.sound.equals(animal.sound)){
                return true; //je stejneho druhu a vydava stejny zvuk
            }
        }
        return false;
    }
    @Override
    public int hashCode() {
        int hash = 5;
        hash = 79 * hash + (this.kind != null ? this.kind.hashCode() : 0);
        hash = 79 * hash + (this.sound != null ? this.sound.hashCode() : 0);
        return hash;
    }
}

Metoda equals

Metoda equals nejprve kontroluje, zda-li je porovnávaný objekt typu Animal. Pokud ano, tak jej přetypuje a porovná druh a zvuk. Jsou-li obě tyto vlastnosti totožné, pak objekty reprezentují stejné zvířátko, v opačném případě tomu tak není.

Metoda hashCode

Metoda hashCode musí reflektovat třídní proměnné použité v operaci equals. Z tohoto důvodu smísí výsledek hashovací funkce pro oba použité řetězce.

Zde využívaná hashovací funkce pro řetězce funguje téměř totožně jako naše implementace. Jediným rozdílem je, že se pro výpočet využívá číselných hodnot jednotlivých znaků (a nedochází již k dalšímu volání hashCode).

Z implementačního hlediska je poměrně důležité, aby multiplikativní konstanty byly prvočíselné – minimalizuje se tak počet kolizí. Samotná operace násobení pak společně s modulární povahou primitivního typu integer zaručí, že dojde dobrému rozptýlení výsledných hodnot.

Hashovací tabulka

Nyní již k samotné implementaci tabulky. Budeme ji vytvářet s využitím metody linear probing. Prvky budeme mazat za využití hlídky (sentinelu).

Rozhraní

První věcí, kterou si musíme rozmyslet je rozhraní typu tabulka. Jeho specifikace nám umožní bezbolestně vyměnit implementaci v případě, že s tou stávající nebudeme z nějakého důvodu spokojeni.

Java

/**
 * Rozhrani tabulky
 * @author Pavel Micka
 * @param <KEY> typovy parametr klice
 * @param <VALUE> typovy parametr hodnoty
 */
public interface TableIface<KEY, VALUE> {
    /**
     * Vlozi prvek do tabulky, pokud jiz prvek s danym klicem existuje, tak bude nahrazen
     * @param key klic
     * @param value hodnota
     * @return @null pokud klic v tabulce neexistuje, v opacnem pripade nahrazena hodnota
     * @throws IllegalArgumentException pokud je klic @null
     */
    public VALUE put(KEY key, VALUE value);
    /**
     * Odstrani prvek odpovidajici danemu klici
     * @param key klic
     * @return @null pokud klic v tabulce neexistuje, v opacnem pripade odstranena hodnota
     */
    public VALUE remove(KEY key);
    /**
     * Navrati hodnotu asociovanou s danym klicem
     * @param key klic
     * @return hodnota, @null pokud neni v tabulce obsazena
     */
    public VALUE get(KEY key);
    /**
     * Dotaz na pritomnost prvku s danym klicem
     * @param key klic
     * @return @true, pokud tabulka obsahuje hodnotu asociovanou s danym klicem, @false v opacnem pripade
     */
    public boolean contains(KEY key);
    /**
     * Dotaz na pocet ulozenych prvku
     * @return pocet ulozenych prvku
     */
    public int size();
    /**
     * Kolekce vsech ulozenych hodnot
     * @return kolekce ulozenych hodnot (poradi neni zadnym zpusobem zaruceno)
     */
    public Collection<VALUE> values();
    /**
     * Kolekce vsech klicu
     * @return kolekce vsech klicu, ktere se vyskytuji v tabulce
     */
    public Collection<KEY> keys();
}

Rozhraní je typováno pomocí dvojice generických parametrů – klíče a hodnoty. Toto nám umožní ukládat do tabulky rozdílné typy, aniž bychom ztratili silnou typovost. Metody keys a values vrací object typu Collection (dokumentace). Collection je rozhraní, jež rozšiřuje interface Iterable, a které je implementováno standardními kolekcemi Javy. Díky této abstrakci můžeme vrátit kontejner, který nejvíce odpovídá našim představám (seznam, strom, tabulku, množinu...).

Konstanty, třídní proměnné, vnitřní třída Entry a konstruktory třídy tabulky

Java

/**
 * Hashovaci tabulka
 * @author Pavel Micka
 * @param <KEY> typovy parametr klice
 * @param <VALUE> typovy parametr hodnoty
 */
public class HashTable<KEY, VALUE> implements TableIface<KEY, VALUE> {
 
    /**
     * Pomer zaplneni pri kterem dojde k vytvoreni nove (vetsi) tabulky
     */
    private final float LOAD_FACTOR = 0.75f;
    /**
     * Pomer zaplneni pri kterem dojde k vytvoreni nove (mensi tabulky)
     */
    private final float COLLAPSE_RATIO = 0.1f;
    /**
     * Hodnota, pod kterou nikdy neklesne velikost tabulky
     */
    private final int INITIAL_CAPACITY;
    /**
     * Pocet ulozenych prvku
     */
    private int size = 0;
    private Entry<KEY, VALUE>[] table;
 
    /**
     * Zkonstruuje hashovaci tabulku s vychozi kapacitou 10
     */
    public HashTable() {
        this(10); //vychozi kapacita
    }
 
    /**
     * Zkonstruuje hashovaci tabulku
     * @param initialCapacity kapacita, pod kterou nikdy tabulka neklesne
     */
    public HashTable(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Kapacita nesmi byt nulova nebo zaporna");
        }
        this.INITIAL_CAPACITY = initialCapacity;
        this.table = new Entry[initialCapacity];
    }
     
    /**
     * Vnitrni trida reprezentujici zaznam tabulky
     */
    private class Entry<KEY, VALUE> {
 
        /**
         * Klic, @null == prvek je sentinel
         */
        private KEY key;
        /**
         * Hodnota
         */
        private VALUE value;
    }    
}

Deklarace a konstanty

V rámci deklarace musíme nejprve předat získané typové parametry výše definovanému rozhraní. Základem definice pak jsou konstanty LOAD_FACTOR - poměr zaplnění, při kterém bude zalokována nová větší tabulka, COLLAPSE_RATIO - poměr zaplnění, při kterém bude zalokována nová menší tabulka a INITIAL_CAPACITY - hodnota, pod kterou nikdy neklesne velikost tabulky.

Třídní proměnné, vnitřní třída Entry a konstruktory

Tabulka obsahuje dvě třídní proměnné - počet uložených prvků (size) a pole záznamů (table). Tyto položky, a již uvedená konstanta INITIAL_CAPACITY, jsou inicializovány v rámci konstruktorů, z nichž jeden je bezparametrický a druhý umožňuje uživateli nastavit výchozí velikost tabulky.

Jednotlivé záznamy jsou reprezentovány soukromou vnitřní třídou Entry, která má dvě proměnné klíč (key) a hodnotu (value). Pokud má záznam nullový klíč, tak je považován za hlídku (sentinel).

Pomocné metody

Nejprve vytvoříme pomocné metody, které nám usnadní manipululaci s tabulkou samotnou.

Metoda calculateRequiredTableSize

Java

/**
 * Vypocte velikost, jakou by mela tabulka mit
 * @return velikost, jakou by mela tabulka mit
 */
private int calculateRequiredTableSize() {
    if (this.size() / (double) table.length >= LOAD_FACTOR) { //tabulka je preplnena
        return table.length * 2;
    } else if (this.size() / (double) table.length <= COLLAPSE_RATIO) {
        //vratime vetsi z hodnot SOUCASNA_VELIKOST/2 a INITIAL_CAPACITY
        return Math.max(this.INITIAL_CAPACITY, table.length / 2);
    } else {
        return table.length; //tabulka ma spravnou velikost
    }
}

Metoda calculateRequiredTableSize vypočte velikost, jakou by měla tabulka mít vzhledem ke svému obsahu. K tomuto využívá trojice konstant LOAD_FACTOR, COLLAPSE_RATIO a INITIAL_CAPACITY. V případě, že je tabulka příliš krátká, doporučí metoda její zvětšení na dvojnásobnou kapacitu, je-li tabulka příliš dlouhá, tak naopak doporučí poloviční velikost. Má-li tabulka ideální délku, tak tuto hodnotu navrátí (tj. doporučí neměnit velikost).

Metoda getEntry

Java

/**
 * Vrati zaznam, ktery odpovida danemu klice
 * @return
 */
private Entry getEntry(KEY key) {
    int index = key.hashCode() % table.length;
    //dokud nenarazime na volne misto, existujici zaznam pro klic nebo sentinel
    while (table[index] != null) {
        if (key.equals(table[index].key)) { //zaznam existuje
            return table[index];
        }
        index = (index + 1) % table.length; //prejdeme na dalsi adresu
    }
    return null; //nenalezen
}

Metoda getEntry vrátí záznam, který odpovídá předanému klíči. Nejprve proto vypočítá základní adresu, na které buď může být prázdné místo (null) nebo shluk prvků. Metoda poté prověří všechny prvky případného shluku, zda-li nemají hledaný klíč. V případě shody odpovídající prvek vrátí. V případě, že shluk hledaný prvek neobsahuje (nebo je základní adresa prázdná), vrátí metoda null.

Metoda performPut

Java

/**
 * Provede samotnou operace vlozeni, aniz by jakkoliv menil informaci o velikosti
 * pole (size), pripadne menil velikost pole (resize)
 *
 * Je-li klic jiz v tabulce obsazen, tak bude asociovana hodnota nahrazena
 *
 * @param key klic
 * @param value hodnota
 * @return byl-li klic v tabulce jiz obsazen, tak nahrazena hodnota, v opacnem pripade @null
 */
private VALUE performPut(KEY key, VALUE value) {
    Entry<KEY, VALUE> e = getEntry(key);
    if (e != null) {
        //prvek je v tabulce
        VALUE val = e.value;
        e.value = value; //zamenime hodnoty
        return val;
    }
    int index = key.hashCode() % table.length;
    while (table[index] != null && table[index].key != null) { //dokud nenarazime na prazdne misto nebo sentinel
        index = (index + 1) % table.length; //posuneme se o adresu dal
    }
    if (table[index] == null) { //prazdne misto
        table[index] = new Entry<KEY, VALUE>();
    }
    table[index].key = key;
    table[index].value = value;
     
    return null;
} 

Metoda performPut provede prosté vložení prvku do tabulky bez jakýchloliv vedlejších akcí (změna velikosti tabulky, změna počtu prvků v tabulce). Této metody totiž využijeme při dvou příležitostech - při vložení prvku (tehdy si obalující metoda zajistí případné dodatečné akce) a při změně velikosti tabulky, kdy je třeba všechny prvky znovu uložit (v tomto případě jsou jakékoliv další akce nežádoucí, protože nedochází ke vložení nových prvků, ale již těch existujících a navíc má tabulka zaručenou ideální délku).

Nyní již k samotné implementaci této metody. Metoda nejprve zjistí pomocí volání getEntry, jestli tabulka již neobsahuje záznam pro hledaný klíč. Pokud ano, tak nahradí asociovanou hodnotu za novou a vrátí tu původní. V opačném případě musí metoda najít volné místo (nebo sentinel), na které vloží nový záznam. Jelikož se jedná o čisté vložení, tak v souladu s kontaktem metoda vrátí null.

Metoda resize

Java

/**
 * Zmeni velikost tabulky, je-li to nutne
 */
private void resize() {
    int requiredTableSize = calculateRequiredTableSize();
    if (requiredTableSize != table.length) { //pokud je treba zmenit velikost tabulky
        Entry<KEY, VALUE>[] oldTable = table;
        table = new Entry[requiredTableSize]; //tak vytvorime novou tabulku
        for (int i = 0; i < oldTable.length; i++) {
            if (oldTable[i] != null && oldTable[i].key != null) {
                this.performPut(oldTable[i].key, oldTable[i].value); //a hodnoty do ni ulozime
            }
        }
    }
}

Metoda resize zajistí, že má tabulka správnou délku. Nejprve se zeptá metody calculateRequiredTableSize na ideální délku. Odpovídá-li navrácená hodnota současné délce tabulky, tak metoda terminuje. V opačném případě metoda vytvoří novou tabulku ideální délky a nechá do ní uložit všechny prvky stávající tabulky prostřednictvím metody performPut.

Metoda put

Java

public VALUE put(KEY key, VALUE value) {
    if (key == null) {
        throw new IllegalArgumentException("Klic nesmi byt null");
    }    
    VALUE val = performPut(key, value);
    if(val == null){
        size++;
        resize();
    }
    return val;
}

Metoda put vloží do tabulky nový záznam. K tomuto využije pomocné metody performPut. Pokud její volání vrátí null, tak to znamená, že byl vložen nový záznam a je zapotřebí inkrementovat počet obsažených prvků a případně změnit velikost tabulky. V opačném případě došlo pouze k náhradě hodnoty u již existujícího záznamu, počet prvků se proto nemění. V každém případě metoda vrátí návratou hodnotu volání performPut (tj. případnou původní hodnotu záznamu).

Metoda remove

Java

public VALUE remove(KEY key) {
    Entry<KEY, VALUE> e = getEntry(key);
    if (e == null) { //prvek neexistuje
        return null;
    }
 
    VALUE val = e.value;
    e.key = null; //prvek je nyni sentinelem
    e.value = null; //odstranime referenci na hodnotu, aby GC mohl cinit svou praci
 
    size--;
    resize();
 
    return val; //vratime puvodni hodnotu
}

Metoda remove odstraní prvek odpovídající danému klíči. Nejprve proto zjistí prostřednictvím volání getEntry, jestli záznam vůbec existuje. Pokud ne, tak metoda terminuje a vrací null.

Pokud záznam existuje, tak nastaví jeho klíč na null, čímž se z něj stane sentinel a zresetuje hodnotu na null, což umožní její sebrání garbage collectorem. Dále metoda sníží dekrementuje třídní proměnnou size, zajistí možnou změnu veliksoti tabulky a nakonec vrátí hodnotu, která byla uložena ve smazaném záznamu.

Metody get a contains

Java

public VALUE get(KEY key) {
    Entry<KEY, VALUE> e = getEntry(key);
    if (e == null) {
        return null;
    }
    return e.value;
}
 
public boolean contains(KEY key) {
    return getEntry(key) != null;
}        

Metoda get vrátí hodnotu asociovanou s předaným klíčem. Pro toto stačí získat odpovídající záznam voláním getEntry. V případě jeho existence pak metoda vrátí jeho hodnotu (value), v opačném případě null.

Implementace metody contains (dotaz na přítomnost) je pak ještě jednodušší. Jedná se pouze o kontrolu nenullovosti návratové hodnoty volání getEntry.

Metody keys a values

Java

public Collection<KEY> keys() {
    List<KEY> keys = new ArrayList<KEY>(size);
    for (int i = 0; i < table.length; i++) {
        if (table[i] != null && table[i].key != null) {
            keys.add(table[i].key);
        }
    }
    return keys;
}
 
public Collection<VALUE> values() {
    List<VALUE> values = new ArrayList<VALUE>(size);
    for (int i = 0; i < table.length; i++) {
        if (table[i] != null && table[i].key != null) {
            values.add(table[i].value);
        }
    }
    return values;
}

Metody keys a values vytvoří dynamické pole (ArrayList) klíčů (nebo hodnot) a projdou tabulku. Ze záznamů, které nejsou sentinely pak vyberou odpovídající položku. Nakonec tento seznam vrátí.

Metoda size

Java

public int size() {
    return size;
}

Metoda size pouze vrátí odpovídající třídní proměnnou.

Výsledný kód

Kompletní kód hashovací tabulky:

Java

/**
 * Hashovaci tabulka
 * @author Pavel Micka
 * @param <KEY> typovy parametr klice
 * @param <VALUE> typovy parametr hodnoty
 */
public class HashTable<KEY, VALUE> implements TableIface<KEY, VALUE> {
 
    /**
     * Pomer zaplneni pri kterem dojde k vytvoreni nove (vetsi) tabulky
     */
    private final float LOAD_FACTOR = 0.75f;
    /**
     * Pomer zaplneni pri kterem dojde k vytvoreni nove (mensi tabulky)
     */
    private final float COLLAPSE_RATIO = 0.1f;
    /**
     * Hodnota, pod kterou nikdy neklesne velikost tabulky
     */
    private final int INITIAL_CAPACITY;
    /**
     * Pocet ulozenych prvku
     */
    private int size = 0;
    private Entry<KEY, VALUE>[] table;
 
    /**
     * Zkonstruuje hashovaci tabulku s vychozi kapacitou 10
     */
    public HashTable() {
        this(10); //vychozi kapacita
    }
 
    /**
     * Zkonstruuje hashovaci tabulku
     * @param initialCapacity kapacita, pod kterou nikdy tabulka neklesne
     */
    public HashTable(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Kapacita nesmi byt nulova nebo zaporna");
        }
        this.INITIAL_CAPACITY = initialCapacity;
        this.table = new Entry[initialCapacity];
    }
 
    public VALUE put(KEY key, VALUE value) {
        if (key == null) {
            throw new IllegalArgumentException("Klic nesmi byt null");
        }    
        VALUE val = performPut(key, value);
        if(val == null){
            size++;
            resize();
        }
        return val;
    }
 
    public VALUE remove(KEY key) {
        Entry<KEY, VALUE> e = getEntry(key);
        if (e == null) { //prvek neexistuje
            return null;
        }
 
        VALUE val = e.value;
        e.key = null; //prvek je nyni sentinelem
        e.value = null; //odstranime referenci na hodnotu, aby GC mohl cinit svou praci
 
        size--;
        resize();
 
        return val; //vratime puvodni hodnotu
    }
 
    public VALUE get(KEY key) {
        Entry<KEY, VALUE> e = getEntry(key);
        if (e == null) {
            return null;
        }
        return e.value;
    }
 
    public boolean contains(KEY key) {
        return getEntry(key) != null;
    }
 
    public int size() {
        return size;
    }
 
    public Collection<VALUE> values() {
        List<VALUE> values = new ArrayList<VALUE>(size);
        for (int i = 0; i < table.length; i++) {
            if (table[i] != null && table[i].key != null) {
                values.add(table[i].value);
            }
        }
        return values;
    }
 
    public Collection<KEY> keys() {
        List<KEY> keys = new ArrayList<KEY>(size);
        for (int i = 0; i < table.length; i++) {
            if (table[i] != null && table[i].key != null) {
                keys.add(table[i].key);
            }
        }
        return keys;
    }
 
    /**
     * Vrati zaznam, ktery odpovida danemu klice
     * @return
     */
    private Entry getEntry(KEY key) {
        int index = key.hashCode() % table.length;
        //dokud nenarazime na volne misto, existujici zaznam pro klic nebo sentinel
        while (table[index] != null) {
            if (key.equals(table[index].key)) { //zaznam existuje
                return table[index];
            }
            index = (index + 1) % table.length; //prejdeme na dalsi adresu
        }
        return null; //nenalezen
    }
 
    /**
     * Provede samotnou operace vlozeni, aniz by jakkoliv menil informaci o velikosti
     * pole (size), pripadne menil velikost pole (resize)
     *
     * Je-li klic jiz v tabulce obsazen, tak bude asociovana hodnota nahrazena
     *
     * @param key klic
     * @param value hodnota
     * @return byl-li klic v tabulce jiz obsazen, tak nahrazena hodnota, v opacnem pripade @null
     */
    private VALUE performPut(KEY key, VALUE value) {
        Entry<KEY, VALUE> e = getEntry(key);
        if (e != null) {
            //prvek je v tabulce
            VALUE val = e.value;
            e.value = value; //zamenime hodnoty
            return val;
        }
        int index = key.hashCode() % table.length;
        while (table[index] != null && table[index].key != null) { //dokud nenarazime na prazdne misto nebo sentinel
            index = (index + 1) % table.length; //posuneme se o adresu dal
        }
        if (table[index] == null) { //prazdne misto
            table[index] = new Entry<KEY, VALUE>();
        }
        table[index].key = key;
        table[index].value = value;
     
        return null;
    }
 
    /**
     * Vypocte velikost, jakou by mela tabulka mit
     * @return velikost, jakou by mela tabulka mit
     */
    private int calculateRequiredTableSize() {
        if (this.size() / (double) table.length >= LOAD_FACTOR) { //tabulka je preplnena
            return table.length * 2;
        } else if (this.size() / (double) table.length <= COLLAPSE_RATIO) {
            //vratime vetsi z hodnot SOUCASNA_VELIKOST/2 a INITIAL_CAPACITY
            return Math.max(this.INITIAL_CAPACITY, table.length / 2);
        } else {
            return table.length; //tabulka ma spravnou velikost
        }
    }
 
    /**
     * Zmeni velikost tabulky, je-li to nutne
     */
    private void resize() {
        int requiredTableSize = calculateRequiredTableSize();
        if (requiredTableSize != table.length) { //pokud je treba zmenit velikost tabulky
            Entry<KEY, VALUE>[] oldTable = table;
            table = new Entry[requiredTableSize]; //tak vytvorime novou tabulku
            for (int i = 0; i < oldTable.length; i++) {
                if (oldTable[i] != null && oldTable[i].key != null) {
                    this.performPut(oldTable[i].key, oldTable[i].value); //a hodnoty do ni ulozime
                }
            }
        }
    }
 
    /**
     * Vnitrni trida reprezentujici zaznam tabulky
     */
    private class Entry<KEY, VALUE> {
 
        /**
         * Klic, @null == prvek je sentinel
         */
        private KEY key;
        /**
         * Hodnota
         */
        private VALUE value;
    }
}

Více informací

Pokud se chcete dozvědět více o hashovacích tabulkách, přečtěte si tento článek.

Vyhledávání

Seznam

Pole

Hashovací tabulka

Hashovací funkce

Kolize

Linear probing

Shlukování

Mazání prvků

Hashovací funkce

Příklad

Metoda equals

Metoda hashCode

Hashovací tabulka

Rozhraní

Konstanty, třídní proměnné, vnitřní třída Entry a konstruktory třídy tabulky

Deklarace a konstanty

Třídní proměnné, vnitřní třída Entry a konstruktory

Pomocné metody

Metoda calculateRequiredTableSize

Metoda getEntry

Metoda performPut

Metoda resize

Metoda put

Metoda remove

Metody get a contains

Metody keys a values

Metoda size

Výsledný kód

Více informací

Doporučujeme