Hashovací tabulka je abstraktní datová struktura, která slouží k ukládání dvojic (klíč, hodnota). Hashovací se nazývá, protože k identifikaci prvků využívá hashovací funkci.
Hašovací tabulku tvoří konečná množina přihrádek P = {0, . . . , m − 1}. Dále vyberme hashovací funkci, která nám pomáhá ke každému klíči přiřadit jednu přihrádku.
Řešení kolizí
Může snadno stát, že několik prvků spadne do stejné přihrádky. Naším cílem je zvolit m a h tak, aby se počet těchto situací, tzv. kolizí, minimalizoval.
Hešování s řetízky
Hešovací tabulka je pole m přihrádek, které jsou buď prázdné nebo v nich začínají spojové seznamy uložených prvků.
Hešování s otevřenou adresací
Do každé přihrádky vejde jen jeden prvek. Při pokusu o uložení do obsazené přihrádky budeme postupně zkoušet náhradní přihrádky, dokud nenajdeme volnou Mazané prvky pouze označovat za smazané. Náhrobkem (tombstone) (†). [jinak vyhledávání nějakého jiného prvku skončí předčasně neúspěšně, protože narazí na přihrádku vyprázdněnou mazáním.]
Volba prohledávací posloupnosti: Lineární přidávání h(k, i) = (f(k) + i) mod m [ chování struktury obvykle degraduje. souvislé bloky ] Dvojité hešování h(k, i) = (f (k) + i · g(k)) mod m
Praktické hešovací funkce:
- Lineární kongruence: x → ax mod m.
- Vyšší bity součinu
- Skalární součin
- Polynom