Jaká je rychlost práce hashovací tabulky?

Rychlost práce hash tabulky, nebo doba přístupu k datům (vyhledávání, vkládání, mazání), je v ideálním případě O(1) — konstantní.

Toho je dosaženo použitím hash funkce, která rychle převádí klíč na index pole.

Skutečná rychlost závisí na:

• Kvalitě hash funkce: Dobrá funkce rovnoměrně rozděluje klíče, minimalizuje kolize.
• Strategiích řešení kolizí:
  • Oddělené řetězce (separate chaining): Při kolizi jsou prvky se stejným hashem uloženy v spojovém seznamu nebo jiném dynamickém poli. Čas přístupu může být v nejhorším případě O(N) (všechny prvky v "koši"), kde N je počet prvků.
  • Otevřené adresování (open addressing): Při kolizi se hledá následující volná buňka v poli. Čas přístupu se může zhoršit při velkém počtu kolizí.
• Zatížení (load factor): Poměr počtu prvků k velikosti hash tabulky. Vysoké zatížení zvyšuje pravděpodobnost kolizí a zpomaluje výkon. Při dosažení určitého prahu je nutné přehashování (rehashing), což je relativně nákladná operace (O(N)).

Protože teoretická rychlost O(1) je nejlepší případ, v praxi může být mírně vyšší kvůli kolizím a nutnosti přehashování, zejména při velkém množství dat nebo neoptimální hash funkci.