Czym jest kolizja haszowania i jakie metody jej rozwiązania istnieją?

Kolizja haszowania występuje, gdy dwa różne wejściowe wartości dają ten sam wynik funkcji haszującej. Jest to nieuniknione, ponieważ zbiór możliwych wejść jest zazwyczaj większy niż zbiór możliwych wartości haszujących.

Metody rozwiązywania kolizji:

1. Otwarte adresowanie — w przypadku kolizji szuka się następnej wolnej komórki w określonej sekwencji (sondowanie liniowe, kwadratowe, podwójne haszowanie).
2. Łańcuchowanie — w każdej komórce tablicy haszującej przechowuje się listę powiązaną wszystkich elementów z tym samym wynikiem haszowania.
3. Rehaszowanie — w przypadku kolizji stosuje się inną funkcję haszującą.

Przykład z łańcuchowaniem w Pythonie:

tablica_haszująca = [[] for _ in range(10)]

def wstaw(k, v):
    indeks = hash(k) % 10
    tablica_haszująca[indeks].append((k, v))

wstaw('jabłko', 1)
wstaw('pajb', 2)  # możliwa kolizja