Hashování

Tento text posledními třemi paragrafy již překračuje zkoušenou látku.

Hashování a kolize

Budiž h funkce z M do N (což jsou řekněme dva diskrétní prostory, N pole konečné velikosti). Reprezentujme (neuspořádanou) množinu S prvků M takto: pokud N[h(m)]=nic, m není prvkem S; pokud N[h(m)]=m, m prvkem S jest. Přidávání, ubírání, detekce prvků v konstantním čase jest vcelku triviální. Nebo ne? Je-li M menší či obdobně rozsáhlý jako N, nemá hashování smysl. Je-li však M podstatně větší, nežli N, například nekonečný (například prostor céčkových řetězců), hashovací funkce h nemůže být prostá, to jest pro některé a,b bude h(a)=h(b), což nazveme kolizí. Toto je moment, kdy výše nastíněná reprezentace podmnožin M selhává; jsme tedy nuceni stáhnout tezi o konstantní časové složitosti elementárních množinových operací prostřednictvím hashování. Věnujme tedy nějaký čas metodám řešení kolizí.

Otevřené adresování

Pokud h(a)=h(b) v okamžiku přidávání druhého prvku b do množiny již obsahující a, zkrátka b umístíme někam jinam. Například hned za a, tedy na pozici h(b)+1; přelezeme-li takto hashovací tabulku, tedy N, půjdeme raději na nulu, to jest první prvek N . Je-li i na h(b)+1 obsazeno, jdeme na h(b)+2 atd. Při detekci však na toto musíme brát zřetel a najdeme-li při pátrání po x na h(x) cizáka, musíme prohledávat hashovací tabulku tak dlouho, dokud nenajdeme volnou položku. Výmaz prvku je ještě méně příjemný - vždyť uvolníme-li položku dosud obsazenou vymazávaným prvkem, můžeme takto odříznout jiný prvek, který s ním kolidoval a byl tedy odstrčen dále do tabulky! Co s tím? Vymazávané prvky nahradíme dohodnutou konstantou (podobně, jako už používáme konstantu nic) a tato konstanta pak přebírá chování konstanty nic s tím, že detekce (ne však přidávání) prvků pokračuje s vyhledáváním prvků i za přes tuto konstantu. Funguje to dobře? Nijak zvlášť. Pakliže delší dobu přidáváme a ubíráme prvky v hashovací tabulce, tabulka se beznadějně zaplní exempláři této nové konstanty a detekce se zvrhne v nekonečné cyklování v tabulce. Takže pardon, uděláme to lépe. Vymazávaný prvek nahradíme kterýmkoli z následujících prvků v tabulce, který ovšem (jak zjistíme z jeho hashovací funkce) při zařazování do tabulky projížděl právě uvolňovanou položkou. Tímtéž postupem pak vymažeme tento přemisťovaný prvek z jeho dosavadního bydliště. Pokud takovýto prvek neexistuje, lze jej bezpečně nahradit konstantou nic. (Poznámka: s trochou zdravého rozumu mohou být všechny tyto operace naprogramovány lineárně vzhledem k velikosti shluku obsazených položek.)

Řetězení

Ke každé položce v hashovací tabulce připojíme pointer na spojový seznam prvků kolidujících s danou položkou. Přidávání, odebírání i detekce jsou triviální v čase lineárním vzhledem k velikosti shluku kolidujících prvků, jež je ovšem v průměru lineárně závislá na koeficientu obsazení tabulky. Leč proč bychom museli používat spojový seznam, když už kolize nastala? Použijme raději vyhledávací strom a z lineární závislosti složitosti operací na koeficientu zaplnění tabulky máme logaritmickou. Pracujeme-li v Basicu (v němž dynamická alokace nebývá k dispozici), připravíme si druhé pole obdobné N a namísto pointerů použijeme indexy do tohoto pole (jehož položky jsou rovněž doplněny takovým indexem). Tomuto druhému poli se občas říká sekundární hashovací tabulka.

Hashovací funkce

Podívejme se nyní na hashovací funkci h . Prostá, zdá se, nebude. Bylo by nicméně žádoucí, kdyby byla co nejrovnoměrněji rozložena po celém poli N (tedy prostoru výsledků hashovací funkce). Odtud plyne, že čím je h nesmyslnější a nepředvídatelnější, tím lépe (většinou). Velice oblíbený trik je metoda dělení - z hashovaného prvku m vypočteme nějakou prozatímní funkci H(m) a poté vezmeme h(m)=H(M) mod n, kde n jest kardinalita N . H(m) může být například přímo m, je-li M prostor nějakého druhu celých čísel. A když M nejsou čísla, ale řetězce? Pro jednoznakový řetězec s vezmeme H(s)=s, pro víceznakový řetězec sS, kde s je jediný znak, vezmeme například H(sS)=H(s)+kH(S) pro vhodné k . A jaké předpoklady mají platit pro n a popřípadě i pro k ? V první řadě by neměly mít nic společného s hodnotami M a pochopitelně ani mezi sebou navzájem. Zkušenosti ukazují, že nejhorší výsledky poskytuje n=2i a vůbec čísla více či méně sudá. Nejlepší výsledky naopak připadají na prvočísla: máme-li tedy k dispozici 1024 položek hashovací tabulky, časová (a v případě řetězení i prostorová) složitost elementárních operací obvykle podstatně vzroste, ponecháme-li poslední tři položky volné, vzhledem k tomu, že 1021 je prvočíslem. Podotkněme ještě, že v následujícím se tak nějak předpokládá, že je použita právě metoda dělení, i když to není jediný používaný způsob hashování.

Clustering

Jeden hloupý rys dosud popsané metody otevřeného adresování je vznik takzvaných clusterů, tedy dlouhých posloupností prvků, jež se nahashovaly přibližně tamtéž do N a nyní zdržují elementární operace v zasažené oblasti. Pravda, toto zdržení můžeme u vyhledávání redukovat jakýmsi seřazením kolidujících prvků, to jest zachováním invariantu N[y]>x pro všechny y mezi h(x) a skutečným umístěním prvku x . Předpokládáme-li, že nic je menší, než kterýkoli jiný prvek, není obtížné implementovat přidávání a detekci prvku a po chvíli odladíme i odebírání. Jako prémii však získáváme další operaci - porovnání dvou množin, reprezentovaných hashovacími tabulkami: dvě takto seřazené hashovací tabulky jsou totiž identické právě tehdy, když obsahují tytéž prvky, jinými slovy nezáleží na pořadí jejich zařazení a ani přidání a pozdější odstranění prvku nehraje roli! To ovšem pouze za předpokladu, že ověříme, že vždy je x(1)>x(2) nebo x(2)>x(1). Další možnost je zabránit, aby se dva řetězy pocházející ze dvou položek v hashovací tabulce spojovaly do jednoho dvojnásobné délky. Použijme tedy metody h(0)(x)=h(x), h(i+1)(x)=h(i)(x)+k(x), kde k závisí na x, podobně, jako h(x) . Docela rozumné řešení je k(x)=H(x) mod n-2, jsou-li n i n-2 prvočísla, jako například 1021 a 1019. Poznamenejme však, že odebírání prvků se zproblematizuje.

Self-Adjusting Tables

Hashovací tabulky se obvykle používají v kompilátorech, slovnících či v operačních systémech pro častý přístup k nějaké datové struktuře. V těchto aplikacích se povětšinou vyskytují prvky navzájem nestejně často používané a bylo by sympatické, kdyby se často potřebné prvky nacházely v nejbližším okolí svých hashovacích funkcí, zatímco nepoužívané prvky nechť si bídně hynou někde na koncích clusterů. Použitelných metod je přehršel. Poměrně elegantní trik, používáme-li při kolizích např. metodu h(i+1)=h(i)+1, je vyměnit každý právě nalezený prvek s jeho předchůdcem, pakliže se už nenachází na místě daném přímo jeho hashovací funkcí. Pakliže považujeme takto intenzivní turistický ruch za zbytečně zdržující, můžeme dotyčný přesun provádět dejme tomu při každém sedmnáctém vyhledávání v hashovací tabulce. Tento způsob je značně adaptabilní; změní-li se během práce složení požadavků, hashovací tabulka se poměrně rychle přizpůsobí. V tomto ohledu je výhodnější, nežli dosti intuitivní řešení prostřednictvím výše popsaného řazení prvků, tentokrát ne podle jejich hodnoty, leč podle dosavadního počtu referencí. Takovéto sebeorganizující tabulky ovšem mají smysl zejména v tabulkách víceméně zaplněných. Používáme-li však otevřené adresování, je v takovém případě velice žádoucí tabulku rozšířit, jinak se zcela zaplní a zatuhne. Takže...

Rozšiřování tabulek

Je-li tabulka příliš zaplněná, základní operace jsou pomalé. Je-li téměř prázdná, plýtváme místem. Co s tím, nedokážeme-li předem odhadnout, s jak velkými množinami budeme pracovat? Jistě, kdykoli za běhu ponecháme základní funkci H a změníme n ; nato celou tabulku přehashujeme do nové tabulky. To však zhusta nebude uspokojivé - jednak, kdo se má čekat, až přehashujeme celou tabulku? A za druhé, co když máme dost místa na malou či velkou tabulku, ale ne už na obě najednou? V tom případě můžeme použít následujícího triku: n se bude měnit pouze aritmetickými posuny doleva či doprava (takže musíme ubrat ze svých nároků na jeho prvočíselnost či lichost). Přehashování bude průběžně provádět jiný proces, který bude zároveň aktualizovat ukazatel nejvyšší dosud přehashované položky; pakliže během přehashovávání přijde požadavek na hashovací tabulku ohledně prvku m (ať už jde o kteroukoli operaci), stačí vypočítat h(m) do oné větší tabulky; jde-li o již přehashovanou hodnotu, použije se nový přepočet, není-li h(m) dosud přehashovaná, použije se starý přepočet. Používáme-li metodu otevřeného adresování, musíme si ovšem uvědomit, že že i při řešení kolizí je třeba kontrolovat, nepřecházíme-li mezi již přehashovanou a dosud nepřehashovanou oblastí.

Dokonalé hashování

Mějme danou pevnou S podmnožinu M . Chceme implementovat takovou h z M do N tak, aby h łS byla prostá a N nebyla o mnoho větší než S. Těžké, dosud není příliš uspokojivě řešeno. Buďte N a S přesně stejně velké. Pak řekneme, že h je minimální dokonalá hashovací funkce. Ještě těžší, pro malé rozsahy S (kolem 40 prvků) lze využít větu, že pro jakékoli S skládající se z kladných celých čísel, existují a,b,c tak, že dolní celá část a/(bx+c), vzatá mod n= łS ł je minimální dokonalou hashovací funkcí. Vyhledání těchto konstant nicméně vyžaduje exponenciální čas.

Literatura: