Wat is een hashbotsing en welke methoden bestaan er om deze op te lossen?

Een hashbotsing treedt op wanneer twee verschillende invoerwaarden hetzelfde hashwaarde geven. Dit is onvermijdelijk, omdat de verzameling van mogelijke invoerwaarden meestal groter is dan de verzameling van mogelijke hashwaarden.

Methoden om botsingen op te lossen:

1. Open adressering — bij een botsing wordt gezocht naar de volgende vrije cel volgens een bepaalde volgorde (lineair, kwadratisch, dubbele hashing).
2. Chaining — in elke cel van de hash-tabel wordt een gekoppelde lijst opgeslagen van alle elementen met dezelfde hashwaarde.
3. Rehashing — bij een botsing wordt een andere hashfunctie toegepast.

Voorbeeld met chaining in Python:

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

def insert(k, v):
    index = hash(k) % 10
    hash_tabel[index].append((k, v))

insert('appel', 1)
insert('pale', 2)  # mogelijke botsing