Przy chaining każdy kubełek trzyma listę/drzewo wpisów z tym samym hashem. Przy open addressing kolizje rozwiązuje się przez próbkowanie innych pól (linear/quadratic/double hashing). Chaining jest prostszy przy większym obciążeniu; open addressing jest cache-friendly, ale wymaga niższego load factor.
Odpowiedź zaawansowana
Głębiej
Tablica haszująca mapuje klucze do kubełków poprzez hash(key) mod capacity. Kolizje są normalne: różne klucze mogą trafić do tego samego kubełka.
Dwie główne strategie:
1) Chaining
Każdy kubełek trzyma małą kolekcję wpisów (lista wiązana albo czasem drzewo).
Działa sensownie nawet przy większym load factor, ale „skakanie po wskaźnikach” psuje lokalność cache.
2) Open addressing
Wszystkie wpisy trzymasz w głównej tablicy.
Przy kolizji próbkujesz kolejne pola (linear / quadratic / double hashing).
Jest cache-friendly, ale wydajność szybko spada, gdy tablica jest zbyt pełna, a usuwanie wymaga tombstones.
Przykłady
Chaining insert(key, value):
i = hash(key) % m
bucket[i].append((key, value))
Linear probing insert:
i = hash(key) % m
while table[i] zajęte i table[i].key != key:
i = (i + 1) % m
table[i] = (key, value)
Co ma znaczenie w praktyce
Load factor i polityka resize (większa tablica => mniej kolizji).
Jakość hashy (słabe hashe tworzą klastry i skrajne przypadki).
Dla open addressing: usuwanie (tombstones) i clustering.
Typowe pułapki
Używanie mutowalnych kluczy (hash/równość zmienia się po wstawieniu).