Čo je kolízia hash a aké metódy jej riešenia existujú?

Kolízia hashovania nastáva, keď dve rôzne vstupné hodnoty dávajú rovnakú hodnotu hash funkcie. To je nevyhnutné, pretože množina možných vstupov je zvyčajne väčšia ako množina možných hash hodnôt.

Metódy riešenia kolízií:

1. Otvárané adresovanie — pri kolízii sa hľadá nasledujúca voľná bunka podľa určitej sekvencie (lineárne, kvadratické, dvojité hashovanie).
2. Reťazenie (chaining) — v každej bunke hash tabuľky je uložený spojený zoznam všetkých prvkov s rovnakou hash hodnotou.
3. Rehashing — pri kolízii sa použije iná hash funkcia.

Príklad s reťazením v Pythone:

hash_tabulka = [[] for _ in range(10)]

def vloz(klic, hodnota):
    index = hash(klic) % 10
    hash_tabulka[index].append((klic, hodnota))

vloz('jablko', 1)
vloz('pajb', 2)  # možná kolízia