Tablica haszująca — jak działa haszowanie i rozwiązywanie kolizji

Tablica haszująca przechowuje pary klucz-wartość, haszując każdy klucz do indeksu w tablicy. Dzięki temu może od razu przejść blisko właściwego miejsca zamiast przeszukiwać wszystkie zapisane elementy po kolei.

Dlatego tablice haszujące często mają średnią złożoność bliską $O(1)$ dla wyszukiwania, wstawiania i usuwania. Ten warunek jest ważny: funkcja haszująca musi dość równomiernie rozkładać klucze, a tablica nadal potrzebuje reguły obsługi kolizji.

Co robi tablica haszująca

Tablica haszująca przechowuje pary klucz-wartość, takie jak "name" -> "Ada" albo 42 -> "blue". Ma dwie główne części:

• tablicę pól lub kubełków
• funkcję haszującą, która przypisuje każdy klucz do jednego z tych pól

Jeśli tablica ma $m$ pól, można myśleć o funkcji haszującej jako o czymś, co zwraca indeks od $0$ do $m-1$.

Dla małego przykładu z liczbami całkowitymi reguła może wyglądać tak:

$$h(k) = k \bmod 8$$

Wtedy klucz $10$ trafia do pola $2$, ponieważ $10 \bmod 8 = 2$.

Rzeczywiste funkcje haszujące projektuje się ostrożniej, zwłaszcza dla napisów i większych zbiorów danych. Ale podstawowa idea pozostaje taka sama: szybko obliczyć indeks, a potem sprawdzić element zapisany w tym miejscu.

Dlaczego kolizje haszowania są nieuniknione

Kolizja występuje wtedy, gdy dwa różne klucze trafiają do tego samego pola.

To normalne, ponieważ tablica zwykle ma mniej pól niż liczba możliwych kluczy. Dla

$$h(k) = k \bmod 8$$

klucze $10$, $18$ i $26$ wszystkie trafiają do pola $2$. Więc nawet jeśli funkcja działa dokładnie tak, jak została zdefiniowana, tablica nadal ma konflikt do rozwiązania.

Tablica haszująca nie obiecuje więc unikalnego pola dla każdego klucza. Obiecuje szybki sposób zawężenia wyszukiwania, pod warunkiem że kolizje są dobrze obsługiwane.

Przykład krok po kroku: jedna tablica, jedna kolizja

Załóżmy, że tablica ma $8$ pól i używa funkcji

$$h(k) = k \bmod 8$$

Wstaw klucze $10$, $18$ i $7$.

Najpierw $10$ trafia do pola $2$, ponieważ $10 \bmod 8 = 2$.

Następnie $18$ także haszuje się do pola $2$, więc dochodzi do kolizji.

Potem $7$ trafia do pola $7$, więc to wstawienie nie powoduje kolizji.

Przydatny schemat zawsze jest taki sam:

1. Zahasuj klucz.
2. Przejdź do wskazanego pola.
3. Jeśli jest tam już inny klucz, zastosuj regułę obsługi kolizji.

Gdy ten schemat jest już jasny, łatwiej zrozumieć dwie główne strategie rozwiązywania kolizji.

Łańcuchowanie a adresowanie otwarte

Łańcuchowanie przechowuje kubełek w każdym polu

W łańcuchowaniu każde pole przechowuje małą kolekcję wpisów zamiast tylko jednego.

Jeśli $10$ i $18$ oba haszują się do pola $2$, kubełek $2$ może przechowywać

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

Aby znaleźć klucz $18$, tablica przechodzi do kubełka $2$ i porównuje tylko wpisy znajdujące się w tym kubełku.

Łańcuchowanie jest pojęciowo proste, a usuwanie zwykle jest łatwiejsze niż przy adresowaniu otwartym. Wadą jest to, że długie kubełki spowalniają operacje.

Adresowanie otwarte pozostaje wewnątrz tablicy

W adresowaniu otwartym każde pole tablicy przechowuje co najwyżej jeden wpis. Jeśli pole bazowe jest zajęte, tablica sonduje inne pola według ustalonej reguły.

Jedną z częstych reguł jest próbkowanie liniowe: jeśli pole $2$ jest zajęte, spróbuj $3$, potem $4$, potem $5$, zawijając na początek tablicy, jeśli trzeba.

To pozwala uniknąć osobnych list kubełków, ale zapełnione sąsiednie pola mogą tworzyć klastry. Trzeba też pamiętać, że wyszukiwanie i usuwanie muszą respektować tę samą regułę próbkowania, która była użyta przy wstawianiu.

Kiedy $O(1)$ to uczciwe stwierdzenie

Tablice haszujące często opisuje się jako mające średnio $O(1)$ dla wyszukiwania, wstawiania i usuwania. To stwierdzenie o średnim przypadku zależy od kilku warunków:

• funkcja haszująca dość równomiernie rozkłada klucze
• współczynnik zapełnienia pozostaje pod kontrolą
• strategia obsługi kolizji jest poprawnie zaimplementowana

Współczynnik zapełnienia to iloraz

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

Jeśli tablica staje się zbyt pełna, kolizje występują częściej, a wydajność spada. Dlatego wiele implementacji powiększa tablicę w miarę jej zapełniania.

W najgorszym przypadku wydajność nadal może pogorszyć się w stronę $O(n)$, jeśli zbyt wiele kluczy nagromadzi się w tym samym obszarze.

Typowe błędy związane z tablicami haszującymi

Założenie, że kolizje oznaczają awarię funkcji haszującej

Nie oznaczają. Kolizje są oczekiwane. Prawdziwe pytanie brzmi, czy tablica obsługuje je efektywnie.

Traktowanie $O(1)$ jako czegoś bezwarunkowego

$O(1)$ to zwykle stwierdzenie o średnim przypadku, a nie obietnica dla każdego wejścia i w każdej chwili.

Mylenie haszowania z szyfrowaniem

Funkcja haszująca w podstawowym kontekście struktur danych służy głównie do szybkiego indeksowania, a nie do zachowania tajności. To są różne cele.

Zapominanie o porównaniu rzeczywistego klucza

Dwa klucze mogą mieć ten sam wynik haszowania. Po trafieniu do właściwego kubełka lub miejsca sondowania tablica nadal musi sprawdzić, czy klucz rzeczywiście się zgadza.

Kiedy używa się tablic haszujących

Tablice haszujące stosuje się wszędzie tam, gdzie ważne jest szybkie wyszukiwanie po kluczu. Typowe przykłady to słowniki, tablice symboli, pamięci podręczne, indeksowanie i zliczanie częstości w danych.

To bardzo dobre rozwiązanie, gdy dokładne wyszukiwanie po kluczu jest ważniejsze niż utrzymywanie elementów w porządku sortowania. Jeśli potrzebujesz przechodzenia w kolejności, zapytań przedziałowych albo najbliższych wartości, lepsza może być inna struktura.

Spróbuj podobnego przykładu z kolizją

Weź małą tablicę z $8$ polami i użyj $h(k)=k \bmod 8$. Wstaw kilka kluczy, takich jak $3$, $11$, $19$ i $27$. Następnie rozwiąż kolizje raz przez łańcuchowanie, a raz przez próbkowanie liniowe.

To jedno ćwiczenie bardzo szybko pokazuje główną ideę: kolizje są nieuniknione, a reguła ich obsługi zmienia zachowanie tablicy. Jeśli chcesz zrobić sensowny kolejny krok, spróbuj własnej wersji z innym rozmiarem tablicy i zobacz, jak zmieniają się kolizje.