Recepty z programátorské kuchařky
Hešování

V algoritmech někdy potřebujeme použít pole, které neindexujeme čísly, ale jinými objekty (například řetězci). Nebo ho síce indexujeme čísly, ale z obrovského rozsahu, takže si nemůžeme normální pole této velikosti pořídit. Tato kuchařka se zabývá konstrukcí takového pole – budeme mu říkat hešovací tabulka – a popisem implementace základních operací, které potřebujeme pro práci s ním.

Začátkem kuchařky si ale udělejme pořádek v používaných termínech. Samotnému poli, pro nějž používáme výraz hešovací tabulka, se také často říká asociativní pole nebo slovník. Dá se potkat i zkrácené pojmenování heš, více anglické hash, či jiné jazykové zkomoleniny.

Zkrácené verze ale používat nebudeme, protože by se nám pletly s pojmenováním interní operace, na které je tato datová struktura postavena. Tou základní operací je totiž hešovací funkce, která produkuje heš, který pak budeme používat pro indexování. Základní termíny tedy máme, pojďme si projít principy.

Základní principy a použití

Jak jsme si řekli, tak na hešovací tabulku se můžeme dívat jako na pole, které ale neindexujeme po sobě následujícími přirozenými čísly, ale hodnotami nějakého jiného typu (řetězci, velkými čísly, apod.). Hodnotám, kterými hešovací tabulku indexujeme, budeme říkat klíče. K čemu nám taková věc může být dobrá?

• Použití jako překladového slovníku – máme zadán seznam slov a jejich překladů a chceme k zadanému slovu rychle najít jeho překlad. Vytvoříme si hešovací tabulku, kde klíče budou slova a hodnoty jim přiřazené budou překlady.
• Rozpoznávání klíčových slov (například v překladačích programovacích jazyků) – klíče budou klíčová slova, hodnoty jim přiřazené v tomto příkladě moc význam nemají, stačí nám vědět, zda dané slovo v hešovací tabulce je.
• V nějaké malé části programu si u objektů, se kterými pracujeme, potřebujeme pamatovat nějakou informaci navíc a nechceme kvůli tomu do objektu přidávat nové datové položky (třeba proto, aby nám zbytečně nezabíraly paměť v ostatních částech programu). Klíčem hešovací tabulky budou příslušné objekty.
• Potřebujeme najít v seznamu objekty, které jsou „stejné“ podle nějakého kritéria (například v seznamu osob ty, které se stejně jmenují). Klíčem hešovací tabulky tak zvolíme jméno. Postupně procházíme seznam a pro každou položku zjišťujeme, zda už je v hešovací tabulce uložena nějaká osoba se stejným jménem. Pokud není, aktuální položku do tabulky přidáme.

Potřebovali bychom tedy umět do hešovací tabulky přidávat nové hodnoty, najít hodnotu pro zadaný klíč a případně také umět z hešovací tabulky nějakou hodnotu smazat.

Samozřejmě používat jako klíč libovolný typ, o kterém nic nevíme (speciálně ani to, co znamená, že dva objekty toho typu jsou stejné), dost dobře nejde. Proto použijeme hešovací funkci – funkci, která objektu přiřadí nějaké malé přirozené číslo 0≤ x < K, kde K je velikost hešovací tabulky (ta by měla odpovídat počtu objektů N, které v ní chceme uchovávat; v praxi bývá rozumné udělat si tabulku o velikosti zhruba K=2N).

Dále popsaný postup funguje pro libovolnou takovou funkci, nicméně aby také fungoval rychle, je potřeba, aby hešovací funkce byla dobře zvolena. K tomu, co to znamená, si něco řekneme dále, prozatím nám bude stačit představa, že tato funkce by měla rozdělovat klíče zhruba rovnoměrně, tedy že pravděpodobnost, že dvěma klíčům přiřadí stejnou hodnotu, by měla být zhruba 1/K.

Ideální případ by nastal, kdyby se nám podařilo nalézt funkci, která by každým dvěma klíčům přiřazovala různou hodnotu (i to se může podařit, pokud množinu klíčů, kterými chceme indexovat, známe dopředu – viz třeba příklad s rozpoznáváním klíčových slov v překladačích).

Pojďme si pro tento ideální případ zkonstruovat hešovací tabulku. Pak nám stačí použít jednoduché pole velikosti K, jehož prvky budou struktury obsahující hodnotu klíče a jemu přiřazená data:

class polozka_hese:
    obsazeno = 0
    klic = None
    hodnota = None
tabulka = [polozka_hese() for i in range(K)]

struct polozka_hese {
    int obsazeno;
    t_klic klic;
    t_hodnota hodnota;
} tabulka[K];

A operace naprogramujeme zřejmým způsobem (pro jednoduchost zápisu porovnáváme klíče jednoduchým způsobem pomocí ==, pro obecné klíče ale může porovnávání trvat docela dlouho – třeba pro textové řetězce bychom museli porovnat všechny jejich znaky):

def pridej(klic, hodnota):
    index = hesovaci_funkce(klic)
    # Kolize nejsou, čili tabulka[index].obsazeno=0
    tabulka[index].obsazeno = 1
    tabulka[index].klic = klic
    tabulka[index].hodnota = hodnota

def najdi(klic):
    index = hesovaci_funkce(klic)
    # Nic tu není nebo je tu něco jiného:
    if not tabulka[index].obsazeno \
      or klic != tabulka[index].klic:
        return None
    return tabulka[index].hodnota

void pridej(t_klic klic, t_hodnota hodnota) {
    unsigned index = hesovací_funkce(klic);
    // Kolize nejsou, čili tabulka[index].obsazeno=0
    tabulka[index].obsazeno = 1;
    tabulka[index].klic = klic;
    tabulka[index].hodnota = hodnota;
}

t_hodnota *najdi(t_klic klic) {
    unsigned index = hesovaci_funkce(klic);
    // Nic tu není nebo je tu něco jiného:
    if (!tabulka[index].obsazeno
      || klic != tabulka[index].klic)
        return NULL;
    // Našel jsem:
    return &tabulka[index].hodnota;
}

Kolize a jejich řešení

Normálně samozřejmě takové štěstí mít nebudeme a vyskytnou se klíče, jimž hešovací funkce přiřadí stejnou hodnotu (říká se, že nastala kolize). Co potom?

Jedno z řešení je založit si pro každou hodnotu hešovací funkce seznam, do kterého si uložíme všechny prvky s touto hodnotou. Funkce pro vkládání pak bude v případě kolize přidávat do seznamu, vyhledávací funkce si vždy spočítá hodnotu hešovací funkce a projde celý seznam pro tuto hodnotu. Tomu se říká hešování se separovanými řetězci.

Jiná možnost je v případě kolize uložit kolidující hodnotu na první následující volné místo v poli (cyklicky, tj. dojdeme-li na konec pole, pokračujeme zase od začátku – k tomu nám při implementaci dobře pomůže operace modulení).

Samozřejmě pak musíme i příslušně upravit hledání – snadno si rozmyslíme, že musíme projít všechny položky od pozice, kterou nám poradí hešovací funkce, až po první nepoužitou položku (protože seznamy hodnot odpovídající různým hodnotám hešovací funkce se nám mohou spojit). Tento přístup se obvykle nazývá hešování se srůstajícími řetězci. Implementace pak vypadá takto:

def pridej(klic, hodnota):
    index = hesovaci_funkce(klic)
    while tabulka[index].obsazeno:
        index = (index + 1) % K
    tabulka[index].obsazeno = 1
    tabulka[index].klic = klic
    tabulka[index].hodnota = hodnota

def najdi(klic):
    index = hesovaci_funkce(klic)
    while tabulka[index].obsazeno:
        if klic == tabulka[index].klic:
            return tabulka[index].hodnota
        # Něco tu je,ale ne to, co hledám
        index = (index + 1) % K
    # Nic tu není
    return None

void pridej (t_klic klic, t_hodnota hodnota) {
    unsigned index = hesovaci_funkce(klic);
    while (tabulka[index].obsazeno) {
        index = (index + 1) % K;
    }
    tabulka[index].obsazeno = 1;
    tabulka[index].klic = klic;
    tabulka[index].hodnota = hodnota;
}

t_hodnota *najdi(t_klic klic) {
    unsigned index = hesovaci_funkce(klic);
    while (tabulka[index].obsazeno) {
        if (klic == tabulka[index].klic)
            return tabulka[index].hodnota;
        // Něco tu je,ale ne to, co hledám
        index = (index + 1) % K;
    }
    // Nic tu není
    return NULL;
}

Jaká je časová složitost tohoto postupu? V nejhorším případě bude mít všech N objektů stejnou hodnotu hešovací funkce. Hledání může v nejhorším přeskakovat postupně všechny, čili složitost v nejhorším případě může být až O(NT+H), kde T je čas pro porovnání dvou klíčů a H je čas na spočtení hešovací funkce. Laicky řečeno, pro nalezení jednoho prvku budeme muset projít celou hešovací tabulku (v lineárním čase).

Nicméně tohle se nám obvykle nestane – pokud velikost pole bude dost velká (alespoň dvojnásobek prvků, které chceme do hešovací tabulky uložit) a zvolili jsme dobrou hešovací funkci, pak v průměrném případě bude potřeba udělat pouze konstantně mnoho porovnání, tj. časová složitost hledání i přidávání bude jen O(T+H). A budeme-li schopni prvky hešovat i porovnávat v konstantním čase (což například pro čísla není problém), získáme konstantní časovou složitost obou operací.

Mazání prvků může působit menší problémy (rozmyslete si, proč nelze prostě nastavit u mazaného prvku „obsazeno“ na 0). Pokud to potřebujeme dělat, buď musíme použít separované řetězce (což se může hodit i z jiných důvodů, ale je to o trošku pracnější), nebo použijeme následující fígl: když budeme nějaký prvek mazat, najdeme ho a označíme jako smazaný. Nicméně při hledání nějakého jiného prvku se nemůžeme zastavit na tomto smazaném prvku, ale musíme hledat i za ním. Ovšem pokud nějaký prvek přidáváme, můžeme jím smazaný prvek přepsat.

Volba hešovací funkce

Jakou hešovací funkci tedy použít? To je tak trochu magie a dobré hešovací funkce mají mimo jiné hlubokou souvislost s kryptografií a s generátory pseudonáhodných čísel. Obvykle se dělá to, že se hešovaný objekt rozloží na posloupnost čísel (třeba ASCII kódů písmen v řetězci), tato čísla se nějakou operací „slijí“ dohromady a výsledek se vezme modulo K. Operace na slévání se používají různé, od jednoduchého xoru až třeba po různé komplikované vzorce.

Pro ukázku tu uvedeme jednu magickou funkci v jazyce C, kombinující tři čísla do sebe (výsledek je pak to, co zůstane v proměnné c):

#define mix(a,b,c) {                         \
  a-=b; a-=c; a^=(c>>13);                    \
  b-=c; b-=a; b^=(a<< 8);                    \
  c-=a; c-=b; c^=((b&0xffffffff)>>13);       \
  a-=b; a-=c; a^=((c&0xffffffff)>>12);       \
  b-=c; b-=a; b =(b ^ (a<<16)) & 0xffffffff; \
  c-=a; c-=b; c =(c ^ (b>> 5)) & 0xffffffff; \
  a-=b; a-=c; a =(a ^ (c>> 3)) & 0xffffffff; \
  b-=c; b-=a; b =(b ^ (a<<10)) & 0xffffffff; \
  c-=a; c-=b; c =(c ^ (b>>15)) & 0xffffffff; \
}

My se ale spokojíme s málem a ukážeme si jednoduchý způsob, jak hešovat čísla a řetězce. Pro čísla stačí zvolit za velikost tabulky vhodné prvočíslo a klíč vymodulit tímto prvočíslem (s hledáním prvočísel si ani nemusíme dělat starosti, v praxi dobře poslouží tabulka několika prvočísel přímo uvedená v programu).

Pro řetězce se hodí je nějak převést na číslo, rozumná funkce pro to je třeba tato:

def hash_string(str):
    hash = 0
    for c in str:
        hash = hash * 67 + ord(c) - 113
    return hash % K

unsigned hash_string(unsigned char *str) {
    unsigned hash = 0;
    unsigned char c;

    while ((c = *str++) != 0)
        hash = hash * 67 + c - 113;
    return hash % K;
}

Zde můžeme použít vcelku libovolnou velikost tabulky, která nebude dělitelná čísly 67 a 113. Šikovné je vybrat si například mocninu dvojky (což v příštím odstavci oceníme), ta bude s prvočísly 67 a 113 zaručeně nesoudělná. Jen si musíme dávat pozor, abychom nepoužili tak velkou hešovací tabulku, že by 67 umocněno na obvyklou délku řetězce bylo menší než velikost tabulky (čili by hešovací funkce časteji volila začátek tabulky než konec). Tehdy ale stačí místo našich čísel použít jiná, větší prvočísla.

Poznámky

A co když nestačí pevná velikost hešovací tabulky? Použijeme „nafukovací“ tabulku. Na začátku si zvolíme nějakou pevnou velikost, sledujeme počet vložených prvků, a když se jich zaplní víc než polovina (nebo třeba třetina; menší číslo znamená méně kolizí, a tedy větší rychlost, ale také větší paměťové plýtvání), vytvoříme novou hešovací tabulku dvojnásobné velikosti (případně zaokrouhlené na vyšší prvočíslo, pokud to naše hešovací funkce vyžaduje) a starý heš do něj prvek po prvku vložíme.

To na první pohled vypadá velice neefektivně, ale protože se po každém nafouknutí hešovací tabulka zvětší na dvojnásobek, musí mezi přehešováním na N prvků a na 2N přibýt alespoň N prvků, čili průměrně strávíme přehešováváním konstantní čas na každý vložený prvek.

Pokud navíc používáme mazání prvků popsané výše (u prvku si pamatujeme, že je smazaný, ale stále zabírá místo v hešovací tabulce), můžeme při nafukování takové prvky opravdu smazat a konečně je tak odečíst z počtu obsazených prvků.

S hešováním se separovanými řetězci se zachází podobně, nafukování také funguje a navíc je snadno vidět, že po vložení N náhodných prvků bude v každé přihrádce (přihrádky odpovídají hodnotám hešovací funkce) průměrně N/K prvků, čili pro K velké řádově jako N konstantně mnoho.

Pro srůstající řetězce to pravda být nemusí (protože jakmile jednou vznikne dlouhý řetězec, nově vložené prvky mají sklony „nalepovat se“ za něj), ale platí, že bude-li heš naplněna nejvýše na polovinu, bude průměrná délka kolizního řetízku (tak říkáme posloupnosti kolizí) omezená nějakou konstantou nezávislou na počtu prvků a velikosti hešovací tabulky. Důkaz si ovšem raději odpustíme, není úplně snadný.

Bystrý čtenář si jistě všiml, že v případě prvočíselných velikostí heše jsme v důkazu časové složitosti nafukování trochu podváděli – z heše velikosti N přeci přehešováváme do heše velikosti větší než 2N. Zachrání nás ale věta z teorie čísel, obvykle zvaná Bertrandův postulát, která říká, že mezi čísly t a 2t se vždy nachází alespoň jedno prvočíslo. Takže nová tabulka bude maximálně 4× větší, a tedy počet přehešování na jedno vložení bude nadále omezen konstantou.

Zdeněk Dvořák