Hash Table
V této části si ukážeme, co je to Hash Table. Jde o datovou strukturu, kterou má většina programovacích jazyků již zabudovanou v sobě.
Co je to Hash Table
Hash Table (často se mu říká také Hash Map) je datová struktura, která slouží k ukládání hodnot pomocí klíčů. Většina programovacích jazyků ji má již zabudovanou v sobě. JavaScript má objekty a od ES6 také mapy. Objekty nám v JavaScriptu slouží k ukládání hodnot pomocí řetězců, jako klíčů.
// vytvoření objektu clovek
const clovek = {
jmeno: "Karel", // uložení hodnoty pod klíč "jmeno"
vek: 35, // uložení hodnoty pod klíč "vek"
vyska: 180, // uložení hodnoty pod klíč "vyska"
vaha: 70 // uložení hodnoty pod klíč "vaha"
};
// získání hodnoty z objektu clovek pod klíčem "jmeno"
let jmeno = clovek.jmeno;Narozdíl od polí jsou objekty rychlé při získávání, vkládání i odstraňování položek. U polí se při odstraňování nebo při přidávání položky posouvají indexy, u objektů ne, u těch používáme jako klíče řetězce.
Důvod, proč používáme pro objekty jako klíče řetězce je ten, že chceme, aby byl kód čitelný pro člověka. Počítač ale neví, co se například nachází pod klíčem "jmeno", neukládá si data pomocí textových klíčů. Proto musíme mít nějaký kód, který textové řetězce převádí na jinou hodnotu, podle které se počítač může podívat, co se pod daným klíčem nachází.
Vytvářet si vlastní Hash Table sice není užitečné, když v JavaScriptu máme objekty a mapy, ale abychom pochopili, jakým způsobem vlastně zhruba fungují, tak si jej vytvoříme. Nejprve si ale řekneme, co to jsou hashovací funkce.
Hashovací funkce
Hodnoty pro náš Hash Table, který si později vytvoříme, budeme ukládat v poli. K přístupu k položkám pole se používají indexy, ale u našeho Hash Tablu namísto nich budeme chtít použít řetězce. Proto si budeme muset napsat nějaký kód, který nám řetězce převede na indexy, pomocí kterých budeme moci požadovanou hodnotu v poli získat nebo nastavit. Vytvoříme si na to funkci, která jako parametr vezme řetězec a vrátí nám index. Podle toho, jaký řetězec do funkce předáme jako argument, dostaneme index. Funkci, která tuto operaci provádí, se říká hashovací funkce.
Existuje velké množství hashovacích funkcí. Používají se pro různé účely, například také při registraci na webových stránkách. Hesla se v databázi neuchovávají tak jak je zadáme, ale nejdříve se projedou hashovací funkcí, která z nich udělá náhodnou posloupnost znaků. Pokud by se někdo do databáze náhodou dostal, tak by se hesla nedozvěděl, protože jsou zahashovaná.
Dobrá hashovací funkce by měla splňovat tyto podmínky (nemusí platit pro všechny typy, hlavně pro naše účely):
- měla by být rychlá (nehledě například na počet znaků v řetězci)
- měla by distribuovat indexy rovnoměrně (neměla by pro jeden řetězec vygenerovat index 0 a pro další třeba až 5326)
- stejný vstup by měl vždy vytvořit stejný výstup (pokud například do funkce předáme řetězec "ahoj" a dostaneme číslo 2, tak bychom toto číslo měli dostat vždy, když funkci s tímto argumentem zavoláme)
Pro náš Hash Table, který si v této části vytvoříme, použijeme vlastní hashovací funkci. Následující ukázka ji ukazuje, ale nemusíte vědět jak funguje. Stačí vám vědět, že když ji zavoláme, tak nám podle předaného řetězce vrátí index, který potom budeme moci použít k přístupu do pole.
// naše hashovací funkce přijímá řetězcový klíč a délku pole (později z této funkce uděláme
// metodu pro třídu HashTable, kterou si vytvoříme a délku pole již přijímat nebude)
function hash(key, arrayLen) {
let total = 0;
const WEIRD_PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * WEIRD_PRIME + value) % arrayLen;
}
return total;
}
// použití hashovací funkce
console.log("ahoj: " + hash("ahoj", 10));
console.log("algoritmus: " + hash("algoritmus", 10));
console.log("jmeno: " + hash("jmeno", 10));
console.log("krtek: " + hash("krtek", 10));
> algoritmus: 5
> jmeno: 7
> krtek: 5
>
Naše hashovací funkce má jeden problém. Nevygeneruje pro každý řetězec unikátní index, takže například pro řetězec "algoritmus" a "krtek" vygeneruje stejný index. Tento problém je nevyhnutelný a řeší se různými způsoby. Jeden z nich si později ukážeme.
Vytvoření základu Hash Tablu
Jak jsem již psal, vytvoříme si vlastní Hash Table. Vytvoříme si pro něj třídu HashTable, která bude uchovávat pole, do kterého později namísto pomocí indexů budeme přistupovat pomocí řetězcových klíčů přes metody, které si pro třídu vytvoříme. Prozatím bude třída obsahovat jen metodu pro hashování, kterou budeme používat v ostatních metodách. Tuto metodu budeme používat jen uvnitř třídy, takže jsme si ji pojmenovali jako _hash. To podtržítko značí, že je metoda privátní a neměli bychom ji používat zvenku třídy. Je to taková zaběhlá konvence.
// třída pro Hash Table
class HashTable {
// při vytváření můžeme předat, jak velké chceme pole pro uchovávání hodnot (defaultně je to 53 položek)
constructor(size=53) {
// vytvoření prázdného pole o požadované velikosti, ve kterém se budou uchovávat hodnoty
this.keyMap = new Array(size);
}
// hashovací funkce k získání indexu pro předaný řetězec
_hash(key) {
let total = 0;
const WEIRD_PRIME = 31;
for (let i = 0; i < Math.min(key.length, 100); i++) {
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * WEIRD_PRIME + value) % this.keyMap.length;
}
return total;
}
}Metoda set
Pro přidání hodnoty do Hash Tablu si vytvoříme metodu set. Tato metoda bude přijímat dva parametry. Prvním bude klíč, pod který chceme vložit hodnotu a druhým bude samotná hodnota.
Protože naše hashovací funkce může pro více různých řetězců vrátit stejný index, tak to musíme nějakým způsobem ošetřit. Existuje více strategií pro řešení tohoto problému. Jedna z nich se jmenuje Linear Probing a ta funguje tak, že když najdeme kolizi, tak v poli hledáme další prázdný slot. Můžeme tak mít na jednom indexu uloženou jen jednu hodnotu. Další je například Separate Chaining a tu pro náš Hash Table použijeme.
Separate Chaining funguje tak, že v poli nejsou uloženy přímo hodnoty, ale jsou tam uloženy další pole. Tato pole uchovávají ještě další pole, které vždy mají na prvním indexu uložený klíč a na druhém hodnotu. Takže díky tomu můžeme na jednom indexu pole uložit více hodnot. Jak takové pole například vypadá můžete vidět v následující ukázce.
// pole, ve kterém jsou uloženy hodnoty Hash Tablu
[
[["jmeno", "Karel"], ["vek", 43]], // hodnoty na indexu 0
[["vyska", 180]], // hodnoty na indexu 1
[["vaha", 70]] // hodnoty na indexu 2
]Metoda set na začátku získá index podle předaného klíče. Poté na tomto indexu v poli keyMap vytvoří nové pole, pokud se tam ještě pole nenachází. Dále se pole v poli keyMap prochází a zjišťuje se, jestli se tam již hodnota pro tento klíč nenachází. Pokud se tam již hodnota nachází, tak se změní na novou hodnotu a pokud ne, tak se do pole přidá.
class HashTable {
/* ... */
// metoda pro nastavení/vložení hodnoty do Hash Tablu
set(key, value) {
// získání indexu pro řetězcový klíč
const index = this._hash(key);
// pokud v poli keyMap na získaném indexu ještě neexistuje pole, tak se tam pole vytvoří
if (!this.keyMap[index]) this.keyMap[index] = [];
// pole v poli keyMap se postupně prochází
for (let i = 0; i < this.keyMap[index].length; i++) {
// pokud se v poli našel klíč, pod který chceme hodnotu nastavit, tak se změní hodnota, kterou uchovává
if (this.keyMap[index][i][0] === key) {
// změnění hodnoty
this.keyMap[index][i][1] = value;
// metoda již dál nepokračuje
return;
}
}
// přidání nové položky do pole v poli keyMap
const keyValuePair = [key, value];
this.keyMap[index].push(keyValuePair);
}
}Metoda get
Pro získání hodnoty z Hash Tablu si vytvoříme metodu get. Tato metoda na začátku získá index podle předaného klíče a poté pomocí cyklu hledá v poli nacházejícím se na tomto indexu v poli keyMap hledanou hodnotu. Až ji najde tak ji vrátí a pokud ji nenajde, tak se vrátí undefined.
class HashTable {
/* ... */
// metoda pro získání hodnoty z Hash Tablu
get(key) {
// získání indexu pro předaný klíč
const index = this._hash(key);
// pokud se na získaném indexu v poli keyMap nenachází pole, tak hodnota pod předaným klíčem neexistuje
if (!this.keyMap[index]) return undefined;
// pole v poli keyMap se postupně prochází a hledá se hodnota s požadovaným klíčem
for (let i = 0; this.keyMap[index].length; i++) {
// pokud se hodnota našla, tak ji metoda vrátí
if (this.keyMap[index][i][0] === key) return this.keyMap[index][i][1];
}
// pokud kód došel až sem, tak hodnota pod předaným klíčem neexistuje
return undefined;
}
}Metoda keys
Jako další metodu si pro náš Hash Table vytvoříme metodu keys, která bude vracet pole klíčů, které Hash Table uchovává. Pole keyMap, které Hash Table uchovává se postupně projede a klíče se přidají do pole, které se na konci metody vrátí. V kódu je použita destrukturovací syntaxe.
class HashTable {
/* ... */
// metoda pro získání pole s klíčy, které Hash Table obsahuje
keys() {
// do tohoto pole se budou postupně ukládat klíče, které Hash Table obsahuje
const keys = [];
// tento cyklus postupně projde pole keyMap
for (const arr of this.keyMap) {
// pokud se na tomto místě nenachází pole, tak se následující kód neprovede a pokračuje se dalším cyklem
if (!arr) continue;
// pole se postupně projde a klíče se přidají do pole keys
// (je použita destrukturovací syntaxe - první položka pole (klíč) se v každém cyklu uloží do proměnné key)
for (const [key] of arr) keys.push(key);
}
// vrácení pole s klíčy
return keys;
}
}Metoda values
Poslední metodou, kterou si pro náš Hash Table vytvoříme, bude metoda values. Pomocí této metody budeme moci získat pole hodnot, které Hash Table uchovává. Tato metoda je podobná metodě keys, rozdíl je v tom, že se namísto klíčů vrací hodnoty. Kromě toho metoda values vrací jen unikátní hodnoty, takže má navíc jednu podmínku, která zjišťuje, jestli se již vkládaná hodnota v poli nevyskytuje.
class HashTable {
/* ... */
// metoda pro získání pole s hodnotami, které Hash Table obsahuje
values() {
// do tohoto pole se budou postupně ukládat hodnoty, které Hash Table obsahuje
const values = [];
// tento cyklus postupně projde pole keyMap
for (const arr of this.keyMap) {
// pokud se na tomto místě nenachází pole, tak se následující kód neprovede a pokračuje se dalším cyklem
if (!arr) continue;
// pole se postupně projde a hodnoty se přidají do pole values
for (const [,value] of arr) {
// pokud se vkládaná hodnota v poli values nenachází, tak se tam přidá
if (!values.includes(value)) values.push(value);
}
}
// vrácení pole s hodnotami
return values;
}
}Big O náročnost Hash Tablu
Na závěr si ještě ukážeme časovou náročnost některých operací s Hash Tablem. Všechny jsou O(1).
- vkládání hodnot: O(1)
- odstraňování hodnot: O(1)
- získávání hodnot: O(1)