Mis on hash-kollisioon ja millised meetodid selle lahendamiseks olemas on?

Hashi kokkupõrge tekib siis, kui kaks erinevat sisendväärtust annavad sama hash-funktsiooni väärtuse. See on vältimatu, kuna võimalikud sisendite kogum on tavaliselt suurem kui võimalikud hash-väärtuste kogum.

Kokkupõrgete lahendamise meetodid:

1. Ava aadressimine — kokkupõrke korral otsitakse järgmine vaba lahter kindlas järjekorras (jooneline, ruutne, topelt-hashimine).
2. Kettimine (chaining) — iga hash-tabeli lahtris hoitakse seotud nimekiri kõigist elementidest, millel on sama hash-väärtus.
3. Uuesti hashimine — kokkupõrke korral rakendatakse teist hash-funktsiooni.

Python näide kettimisest:

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

def lisa(kluc, väärtus):
    indeks = hash(kluc) % 10
    hash_tabel[indeks].append((kluc, väärtus))

lisa('õun', 1)
lisa('pma', 2)  # võimalik kokkupõrge