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 miliard). Jednotlivé prvky bychom potom vyhledávali přímo přes příslušný index (tj. s konstantní složitostí
).
Nevýhoda tohoto přístupu je zřejmá – pro velké státy s miliardou obyvatel promrháme 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ž . 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.
/**
* 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.
/**
* 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
/**
* 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
/**
* 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
/**
* 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
/**
* 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
/**
* 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
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
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
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
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
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:
/**
* 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.