Ce este o coliziune de hash și ce metode de rezolvare există?

O coliziune de hash apare atunci când două valori de intrare diferite dau aceeași valoare a funcției hash. Acest lucru este inevitabil, deoarece mulțimea posibilă a intrărilor este de obicei mai mare decât mulțimea valorilor hash posibile.

Metode de rezolvare a coliziunilor:

1. Adresare deschisă — în cazul unei coliziuni, se caută următoarea celulă liberă într-o anumită secvență (sondare liniară, pătratică, hash dublu).
2. Încâlcire (chaining) — în fiecare celulă a tabelului hash se păstrează o listă legată a tuturor elementelor cu aceeași valoare hash.
3. Rehashing — în cazul unei coliziuni, se aplică o altă funcție hash.

Exemplu cu încâlcire în Python:

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

def insereaza(cheie, valoare):
    indice = hash(cheie) % 10
    tabela_hash[indice].append((cheie, valoare))

insereaza('mar', 1)
insereaza('ram', 2)  # posibilă coliziune