Čo je hash tabuľka?

Hash tablica je podatkovná štruktúra, ktorá implementuje asociačný poľ (slovník). Ukladá páry "kľúč-hodnota", kde sú kľúče jedinečné.

Základné princípy:

• Hash funkcia: Premení kľúč na číslo (hash kód alebo index). Tento index ukazuje na miesto uloženia hodnoty v poli (koši).
• Pole (koše): Skutočné uloženie párov "kľúč-hodnota".
• Kolízie: Situácia, keď rôzne kľúče generujú rovnaký hash kód.

Riešenie kolízií:

• Metóda reťazenia (Separate chaining): V každom koši je zoznam (alebo iná dátová štruktúra) prvkov s rovnakým hash kódom.
• Otvárané adresovanie (Open addressing): Pri kolízii sa hľadá voľný koš pomocou rôznych stratégií (lineárne sondovanie, kvadratické sondovanie, dvojité hashovanie).

Charakteristiky:

• Rýchly prístup: V ideálnom prípade O(1) pre operácie vkladania, vyhľadávania a mazania.
• Závislosť od hash funkcie: Kvalita hash funkcie a stratégia riešenia kolízií výrazne ovplyvňujú výkon.
• Využitie pamäti: Vyžaduje dodatočnú pamäť pre pole košov.

Použitie v QA:

• Ukladanie testovacích dát (kľúč - názov parametra, hodnota - očakávaná alebo skutočná hodnota).
• Kontrola jedinečnosti prvkov (napríklad ID používateľov).
• Implementácia cache (medzipamäte).