Co je to hashovací tabulka?

Hash tabulka je datová struktura, která implementuje asociativní pole (slovník). Ukládá páry "klíč-hodnota", kde jsou klíče jedinečné.

Základní principy:

• Hash funkce: Převádí klíč na číslo (hash kód nebo index). Tento index ukazuje na místo uložení hodnoty v poli (koš).
• Pole (koše): Skutečné uložení párů "klíč-hodnota".
• Kolize: Situace, kdy různé klíče generují stejný hash kód.

Řešení kolizí:

• Metoda řetězení (Separate chaining): V každém koši je seznam (nebo jiná datová struktura) prvků se stejným hash kódem.
• Otevřené adresování (Open addressing): Při kolizi se hledá volný koš pomocí různých strategií (lineární sondování, kvadratické sondování, dvojité hashování).

Charakteristiky:

• Rychlý přístup: V ideálním případě O(1) pro operace vkládání, hledání a mazání.
• Závislost na hash funkci: Kvalita hash funkce a strategie řešení kolizí výrazně ovlivňují výkon.
• Využití paměti: Vyžaduje dodatečnou paměť pro pole košů.

Použití v QA:

• Ukládání testovacích dat (klíč - název parametru, hodnota - očekávaná nebo skutečná hodnota).
• Kontrola unikátnosti prvků (například ID uživatelů).
• Implementace cache (mezipaměti).