Hash tabulka

Hašovací tabulka  je datová struktura , která implementuje rozhraní asociativního pole , konkrétně vám umožňuje ukládat páry (klíč, hodnota) a provádět tři operace: operaci přidání nového páru, operaci vyhledávání a operaci odstranění spárovat pomocí klíče.

Úvod

Existují dvě hlavní varianty hashovacích tabulek: řetězené a otevřené adresování. Hashovací tabulka obsahuje nějaké pole , jehož prvky jsou dvojice (otevřená tabulka hash adres) nebo seznamy dvojic (zřetězená tabulka hash).

Provedení operace v hašovací tabulce začíná výpočtem hašovací funkce klíče. Výsledná hodnota hash funguje jako index do pole . Poté je prováděná operace (přidat, odstranit nebo najít) přesměrována na objekt, který je uložen v odpovídající buňce pole .

Situace, kdy je získána stejná hodnota hash pro různé klíče, se nazývá kolize . Takové události nejsou tak vzácné - např. při vložení pouhých 23 prvků do hashovací tabulky 365 buněk už pravděpodobnost kolize přesáhne 50% (pokud každý prvek může spadnout do libovolné buňky se stejnou pravděpodobností) - viz narozeniny paradox . Proto je mechanismus řešení kolizí důležitou součástí každé hashovací tabulky.

V některých speciálních případech je možné kolizím zcela zabránit. Pokud jsou například všechny klíče prvků předem známé (nebo se mění velmi zřídka), pak pro ně lze najít nějakou perfektní hashovací funkci , která je bez kolizí rozdělí mezi buňky hashovací tabulky. Hashovací tabulky, které používají tyto hashovací funkce, nepotřebují mechanismus řešení kolizí a nazývají se hashovací tabulky přímých adres .

Počet uložených prvků dělený velikostí pole (počet možných hodnot hash) se nazývá faktor zatížení hashovací tabulky a je důležitým parametrem, který určuje průměrnou dobu provádění operací.

Vlastnosti hashovací tabulky

Důležitou vlastností hashovacích tabulek je, že za určitých rozumných předpokladů jsou všechny tři operace (vyhledávání, vkládání, mazání prvků) dokončeny v průměru za čas . To však nezaručuje, že doba provedení jedné operace je krátká. To je způsobeno skutečností, že při dosažení určité hodnoty faktoru plnění je nutné znovu sestavit index hashovací tabulky: zvětšit hodnotu velikosti pole a znovu přidat všechny páry do prázdné hashovací tabulky.

Rozlišení kolize

Existuje několik způsobů, jak vyřešit kolize .

Řetězová metoda

Každá buňka pole H je ukazatelem na propojený seznam (řetězec) párů klíč–hodnota odpovídající stejné hodnotě hash klíče. Výsledkem kolizí jsou jednoduše řetězce, které jsou delší než jeden prvek.

Nalezení nebo smazání prvku vyžaduje prohledání všech prvků odpovídajícího řetězce, aby se našel prvek s daným klíčem. Chcete-li přidat prvek, musíte přidat prvek na konec nebo začátek odpovídajícího seznamu, a pokud se faktor vyplnění příliš zvětší, zvětšete velikost pole H a znovu sestavte tabulku.

Za předpokladu, že každý prvek může spadnout na jakoukoli pozici tabulky H se stejnou pravděpodobností a bez ohledu na to, kde skončil jakýkoli jiný prvek, je průměrná doba operace vyhledávání prvku Θ (1 + α ), kde α  je faktor vyplnění tabulky.

Otevřít adresování

Pole H ukládá samotné páry klíč–hodnota. Algoritmus vkládání prvků kontroluje buňky pole H v určitém pořadí, dokud není nalezena první volná buňka, do které bude nový prvek zapsán. Toto řazení je vypočítáváno za běhu, čímž se šetří paměť pro ukazatele požadované v řetězených hašovacích tabulkách.

Sekvence, ve které se vyhledávají buňky hashovací tabulky, se nazývá sekvence sondy . V obecném případě záleží pouze na klíči prvku, to znamená, že se jedná o posloupnost h 0 ( x ), h 1 ( x ), ..., h n  - 1 ( x ), kde x  je klíč prvku a h i ( x ) - libovolné funkce, které mapují každý klíč na buňku v tabulce hash. První prvek v sekvenci se zpravidla rovná hodnotě nějaké hashovací funkce z klíče a zbytek se z ní vypočítá jedním z následujících způsobů. Aby vyhledávací algoritmy fungovaly úspěšně, sekvence sond musí být taková, aby byly všechny buňky hashovací tabulky naskenovány právě jednou.

Algoritmus hledání prohledává buňky hašovací tabulky ve stejném pořadí jako při vkládání, dokud nenajde buď prvek s požadovaným klíčem, nebo volnou buňku (což znamená, že v hašovací tabulce není žádný prvek).

Odstranění prvků v takovém schématu je poněkud obtížné. Obvykle to dělají: pro každou buňku nastaví booleovský příznak, který označí, zda byl prvek v ní odstraněn nebo ne. Pak odstranění prvku spočívá v nastavení tohoto příznaku pro příslušnou buňku hashovací tabulky, ale zároveň je nutné upravit postup hledání existujícího prvku tak, aby smazané buňky považoval za obsazené a postup za jejich přidání, aby je považoval za volné a po přidání resetuje hodnotu příznaku.

Ukázkové sekvence

Následují některé běžné typy ukázkových sekvencí. Ihned upřesněme, že číslování prvků sekvence vzorků a buněk hashovací tabulky je od nuly a N  je velikost hashovací tabulky (a jak bylo uvedeno výše, také délka sekvence vzorků).

• Lineární sondování : buňky hashovací tabulky jsou skenovány sekvenčně s určitým pevným intervalem k mezi buňkami (obvykle k = 1), tj. i -tým prvkem sekvence sondování je buňka očíslovaná (hash( x ) +  ik ) mod  N. Aby byly všechny buňky naskenovány jednou, je nutné, aby k bylo coprime s velikostí hash tabulky.
• Kvadratické sondování : interval mezi buňkami se s každým krokem zvyšuje o konstantu. Pokud je velikost hashovací tabulky mocninou dvou ( N = 2 p ), pak jeden příklad sekvence, ve které bude každý prvek vyhledán jednou, je: hash( x ) mod N , (hash( x ) + (1+1*1)/2) mod N , (hash( x ) + (2+2*2)/2) mod N , (hash( x ) + (3+3*3)/2) mod N , … jsou trojúhelníková čísla .
• Dvojité hašování : interval mezi buňkami je pevný, jako u lineárního sondování, ale na rozdíl od něj se velikost intervalu vypočítává druhou, pomocnou hašovací funkcí, což znamená, že se může pro různé klíče lišit. Hodnoty této hašovací funkce musí být nenulové a musí být spojeny s velikostí hašovací tabulky, čehož lze nejsnáze dosáhnout tak, že se jako velikost použije prvočíslo a vyžaduje se, aby hašovací pomocník přebíral hodnoty mezi 1 a N.  - 1.

Níže je kód demonstrující dvojité hashování: