Kas ir hash kolīzija un kādas ir tās risināšanas metodes?

Hesīsa kolīzija rodas, kad divi dažādi ievades vērtības dod to pašu hesīsa funkcijas vērtību. Tas ir neizbēgami, jo iespējamās ievades vērtību kopums parasti ir lielāks nekā iespējamās hesīsa vērtības.

Kolīziju risināšanas metodes:

1. Atvērta adrešu piešķiršana — kolīzijas gadījumā tiek meklēta nākamā brīvā šūna noteiktā secībā (līnija, kvadrātiska, dubultā hesīsa).
2. Saistīšana (chaining) — katrā hesīsa tabulas šūnā tiek glabāta saistīta saraksta ar visiem elementiem ar to pašu hesīsa vērtību.
3. Jauna hesīsa — kolīzijas gadījumā tiek piemērota cita hesīsa funkcija.

Python piemērs ar saistīšanu:

hesīsa_tabula = [[] for _ in range(10)]

def ievietot(atslēga, vērtība):
    indekss = hash(atslēga) % 10
    hesīsa_tabula[indekss].append((atslēga, vērtība))

ievietot('ābols', 1)
ievietot('pma', 2)  # iespējamā kolīzija