Jak tablice haszujące obsługują kolizje? (chaining vs open addressing)

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).