Hash tabuľka uchováva dvojice kľúč a hodnota. Podľa kľúča vieme hodnotu vložiť, nájsť, zmeniť alebo vymazať. Napríklad ku kľúču "meno" priradíme hodnotu "Eva". Kľúč je v tabuľke najviac raz; ďalšie priradenie k tomu istému kľúču nahradí jeho hodnotu.

Úložiskom je pole, ktoré v Pythone reprezentujeme zoznamom. Jeho počet pozícií nazývame kapacita. Počet skutočne uložených dvojíc môže byť menší. Tabuľka s kapacitou desať a tromi dvojicami má stále desať pozícií.

Ako funguje hash tabuľka

V tomto príklade využijeme objektové programovanie na vytvorenie hash tabuľky, ktorá sa bude pri podporovaných operáciách správať podobne ako slovník.

Základný zápis si ukážeme na triede HashTable. Jej atribút slots bude zoznam, do ktorého uložíme dáta.

Zoznam slots uchováva referencie na objekty. Každá jeho pozícia bude odkazovať na jednu z troch možností:

• self.empty: referencia nikdy nepoužitého miesta.
• self.deleted: referencia miesta, z ktorého sme položku vymazali.
• N-tica (tuple) (key, value): aktívna položka s kľúčom a hodnotou.

Sloty rozpoznávame pomocou referencie a operátora is, napríklad self.slots[i] is self.empty alebo self.slots[i] is self.deleted.

Zoznam 10 slotov, z ktorých všetky sú prázdne, vytvoríme zápisom [self.empty] * 10. V pamäti bude vyzerať takto:

Index | Obsah
0     | self.empty
1     | self.empty
2     | self.empty
3     | self.empty
4     | self.empty
5     | self.empty
6     | self.empty
7     | self.empty
8     | self.empty
9     | self.empty

Do slotu empty možno vložiť novú dvojicu. Pri vložení napríklad priradíme self.slots[index] = (key, value). Tým nahradíme referenciu na značku referenciou na novú n-ticu.

Pri vymazaní použijeme self.slots[index] = self.deleted. Samotný zoznam sa tým neskráti a ostatné položky zostanú na svojich indexoch.

Ak zoznam obsahuje aktívnu položku a vymazanú položku, bude vyzerať napríklad takto:

Index | Obsah
0     | self.empty
1     | self.empty
2     | self.deleted
3     | self.empty
4     | self.empty
5     | self.empty
6     | ("meno", "Eva")
7     | self.empty
8     | self.empty
9     | self.empty

Tento zoznam obsahuje jednu aktívnu položku s kľúčom "meno" a hodnotou "Eva", jednu vymazanú položku a osem nikdy nepoužitých miest. Jeho kapacita je desať, počet aktívnych položiek je jedna.

Faktor zaplnenia (load factor) je počet aktívnych položiek delený kapacitou. V tomto príklade je 1/10 = 0.1.

Hashovanie reťazca: hash(self, key)

Hashovacia funkcia prevedie reťazec na celé číslo polynomiálnym výpočtom a potom ho pomocou modulo operácie prevedie na index v poli.

Obyčajný súčet kódov znakov nie je vhodný, lebo nerozlišuje poradie znakov: reťazce "ab" a "ba" by mali rovnaký súčet. Namiesto toho použijeme polynomiálny súčet, ktorý sa často používa pri vyhľadávaní reťazcov.

Polynomiálny súčet berie hodnoty znakov ako koeficienty polynómu so základom 31.

Napríklad, pre reťazec "abc" je to:

ord("a") * 31^2 + ord("b") * 31^1 + ord("c") * 31^0

Pri výpočte polynómu sa snažíme vyhnúť operátorom mocniny. Namiesto toho sa priebežný výsledok vynásobí základom a pripočíta sa kód ďalšieho znaku:

result = 0
for char in key:
    result = result * 31 + ord(char)

Tento postup sa nazýva Hornerovo schéma.

Výsledok na konci sa vydelí kapacitou, aby sme dostali index v rozsahu od nuly po kapacitu mínus jeden. Nepoužíva sa operácia celočíselného delenia, ale operátor % (modulo), ktorý vráti zvyšok po delení. Pri kladnej kapacite tak výsledok leží v rozsahu indexov od 0 po capacity - 1.

Kľúč v tomto cvičení musí byť reťazec. Metódy pracujúce s kľúčom vrátane hash a probe majú pri inom type vyvolať TypeError.

Lineárne sondovanie: probe(self, key)

Viac rôznych kľúčov môže dostať rovnaký index. Tomu hovoríme kolízia. Neznamená to, že sa kľúče rovnajú. V našej úlohe majú napríklad pri kapacite desať kľúče "a", "k" a "u" rovnaký počiatočný index sedem.

Ak je počiatočné miesto obsadené iným kľúčom, skúšame nasledujúce miesto, potom ďalšie, až nájdeme vhodnú pozíciu. Za koncom poľa pokračujeme od nuly. Tento postup sa nazýva lineárne sondovanie alebo linear probing.

Po postupnom vložení uvedených troch kľúčov môže časť poľa vyzerať takto:

Index	Obsah
6	nikdy nepoužité miesto
7	kľúč "a" a jeho hodnota
8	kľúč "k" a jeho hodnota
9	kľúč "u" a jeho hodnota
0	nikdy nepoužité miesto

Pri hľadaní "u" začneme na indexe sedem a porovnávame uložené kľúče. Až na indexe deväť nájdeme zhodu. Samotná zhoda hashov nestačí.

Funkcia probe(key) je spoločná pre čítanie, vkladanie aj mazanie. Vracia index, nie uloženú hodnotu. Pri existujúcom kľúči vráti jeho pozíciu; inak vhodné miesto na vloženie. Samotné sondovanie tabuľku nemení.

Pri hľadaní nikdy nepovažujte značku deleted za koniec hľadania: kľúč môže byť uložený až za ňou. Značka empty naopak znamená, že sa daný reťazec sondovania skončil a hľadaný kľúč v ňom nie je. Sondovanie musí mať hornú hranicu najviac capacity krokov, aby sa skončilo aj v tabuľke bez značky empty.

Pri vkladaní si zapamätajte prvý slot deleted, ale pokračujte v sondovaní. Až keď nájdete existujúci kľúč alebo koniec reťazca, rozhodnete, či ide o aktualizáciu, alebo nové vloženie. Tak sa nestane, že vložíte druhú kópiu kľúča, ktorý sa nachádza až za vymazaným slotom. Ak sa sondovaním nenájde voľný slot, možno použiť zapamätaný slot deleted.

Vytvorenie triedy HashTable

Táto úvodná verzia iba vytvorí prázdnu tabuľku; ďalšie metódy doplníme postupne:

class HashTable:
    def __init__(self, capacity=10):
        self.empty = object()
        self.deleted = object()
        self.slots = [self.empty] * capacity

prva = HashTable(3)
druha = HashTable()
assert all(slot is prva.empty for slot in prva.slots)
assert len(prva.slots) == 3
assert len(druha.slots) == 10
assert prva.slots is not druha.slots

Kapacita musí byť kladné celé číslo. Hodnoty ako 10.0, "10" aj booleovské hodnoty True a False nie sú platnou kapacitou; nekladná kapacita vyvolá ValueError a hodnota nesprávneho typu TypeError.

__init__ sa zavolá pri inicializácii novej inštancie. Parameter self odkazuje na konkrétny objekt. Priradením do self.slots uložíme atribút, ktorý zostane dostupný aj po skončení metódy. Obyčajná lokálna premenná patrí iba danému volaniu metódy.

Každé volanie object() vytvorí nový objekt. Atribúty self.empty a self.deleted preto odkazujú na dve rôzne značky stavov pozície. Výraz [self.empty] * capacity vytvorí zoznam, ktorého všetky pozície odkazujú na tú istú značku self.empty. Nevytvára novú značku pre každú pozíciu. Pri každom volaní konštruktora však vznikne samostatný zoznam a vlastné značky danej tabuľky.

Ako špeciálne metódy vytvoria rozhranie dict

Python umožňuje definovať správanie operátorov pomocou špeciálnych metód s dvoma podčiarkovníkmi na začiatku a na konci názvu. Vďaka nim sa vlastná trieda používa podobne ako vstavaný kontajner.

Keď použijete zodpovedajúci operátor, Python vyhľadá príslušnú špeciálnu metódu a zavolá ju. Na implementáciu týchto operácií netreba dediť z dict. Tento prístup súvisí s duck typingom: objekt možno používať podľa toho, aké operácie podporuje. Samotné tieto metódy z neho však neurobia plnohodnotný vstavaný dict.

Na to, aby sa vlastná trieda pri základných operáciách správala podobne ako dict, treba implementovať tieto metódy:

Zápis používateľa	Metóda triedy	Čo má zabezpečiť
table[key]	__getitem__(self, key)	Vrátiť hodnotu alebo vyvolať KeyError.
table[key] = value	__setitem__(self, key, value)	Vložiť alebo aktualizovať dvojicu.
del table[key]	__delitem__(self, key)	Vymazať dvojicu alebo vyvolať KeyError.
key in table	__contains__(self, key)	Vrátiť booleovskú informáciu o prítomnosti kľúča.
len(table)	__len__(self)	Vrátiť nezáporný celočíselný počet aktívnych dvojíc.
iter(table) a for key in table	__iter__(self)	Vrátiť iterátor aktívnych kľúčov.

Vo vnútri využívajte spoločné metódy, napríklad probe a hash, namiesto rôznych verzií rovnakého vyhľadávania.

Týmto implementujete základné rozhranie požadované úlohou.

__getitem__: čítanie a kontrola prítomnosti

Vo vnútri špeciálnych metód nepoužívajte operátory, ktoré sa snažíte definovať. Napríklad v __getitem__ nečítajte hodnotu zápisom self[key]: ten by opäť zavolal tú istú metódu a spôsobil rekurziu. Podobne v __len__ nepoužívajte len(self). Pracujte so svojím úložiskom a evidovaným počtom položiek.

Index vrátený z probe ešte nezaručuje, že kľúč existuje. Môže označovať iba miesto na jeho budúce vloženie. Pred čítaním preto overte stav položky. Chýbajúci kľúč má viesť ku KeyError(key).

Prítomnosť neposudzujte podľa pravdivosti hodnoty. Aj None, False, 0 či prázdny zoznam môžu patriť existujúcemu kľúču.

__iter__: Prechádzanie hodnôt

Pre __iter__ sa hodí generátor s yield, ktorý postupne poskytuje kľúče aktívnych položiek. Vynecháva prázdne aj odstránené miesta. Iterácia vracia kľúče, nie hodnoty ani dvojice; každý aktívny kľúč musí poskytnúť práve raz. Poradie vloženia toto cvičenie nevyžaduje.

__setitem__ a __contains__: vkladanie a aktualizácia

Najprv rozlíšte aktualizáciu existujúceho kľúča od vloženia nového. Aktualizácia mení iba hodnotu. Nezvyšuje počet položiek a nevyžaduje zväčšenie kapacity.

Pri novom kľúči posudzujte zaplnenie, ktoré vznikne po jeho pridaní. Hranica je striktne nad 70 %: pri kapacite 10 siedma položka tabuľku nezväčší, ôsma už áno. Aktualizácia existujúceho kľúča počet položiek ani kapacitu nemení.

Pri prekročení hranice zdvojnásobte kapacitu a vytvorte nové pole. Znovu vložte doň iba aktívne dvojice; značky deleted sa neprenášajú. Každý kľúč musí dostať nový hash podľa novej kapacity a nové miesto cez sondovanie. Index získaný pred zväčšením už preto nepoužívajte. Po prehashovaní vložte novú dvojicu a počet položiek zvýšte práve raz.

__delitem__: mazanie

Nájdite existujúci kľúč, nahraďte jeho položku značkou odstránenia a upravte počet aktívnych položiek. Zachovajte priechodnosť kolízneho reťazca. Pri chýbajúcom kľúči vyvolajte KeyError(key) bez zmeny stavu. Opakované mazanie toho istého kľúča nesmie opakovane znižovať počet položiek.

Next Post