Jeśli masz już trochę doświadczenia z programowaniem, prawie na pewno używałeś/aś tablic mieszających.
Stoją one za wieloma interfejsami dostępnymi w różnych językach i, ze względu na swoją wszechstronność, są często wykorzystywane przez programistów. Żeby stworzyć lepszy mentalny obraz tego, o czym będziemy mówić, oto kilka przykładów interfejsów korzystających z tej struktury danych w popularnych językach:
- JavaScript: Map, Set
- Python: Dict, Set
- Java: HashMap, HashSet
- C++: std::unordered_map, std::unordered_set

Zamiast jednak koncentrować się na użyciu gotowców, zobaczymy, co dzieje się poziom niżej i jakie wyzwania czekają na tych, którzy chcą napisać własną implementację.

Zazwyczaj zaczyna się od potrzeby przechowania w pamięci jakiegoś zestawu wartości, np. wyników obliczeń, robiąc to tak, żeby dostęp do każdej z nich, był możliwie szybki. Zwyczyjna tablica, nawet posortowana, może okazać się zbyt wolna. Chąc wydobyć z niej jakąś wartość, najpierw będzie trzeba znać jej indeks, a to wymaga przeszukania tablicy. Potrzebujemy więc sposobu na deterministyczne nadawanie indeksów, tak żeby zawsze było wiadomo, pod jakim adresem jest to, czego szukamy, najlepiej bez przechowywania dodatkowych danych. Potrzeba do tego klucza, który posłuży za bazę, a dalej wygląda to tak:

1. Redukujemy klucz (np. string) do hasha, czyli dosyć długiego ciągu bitów, często zapisywanego jako liczba w systemie szesnastkowym dla ułatwienia.
2. Otrzymany hash zamieniamy na mniejszą liczbę.
3. Tej ostatniej używamy jako indeksu do klasycznej tablicy (ciągłego bloku pamięci), i tam ostatecznie umieszczamy klucz i opcjonalnie inne dane.

Ogólny schemat działania tablicy mieszającej.

Niezależnie od tego, czy chcemy dodać, usunąć czy zmienić zawartość, przechodzimy przez ten sam proces. Za każdym razem wystarczy ponownie zamienć klucz na hash, a ten wskaże miejsce przechowywania powiązanej z nim wartości. Ze względu na duże różnice w działaniu poszczególnych języków, istniejące w nich implementacje tablic mieszających mają rozmaite wymagania co do klucza. Ugólniając, można powiedzieć, że klucz musi być hashowalny. W JS np., oznacza to dosłownie każdą wartość (nawet undefined i NaN), ale większość innych języków jest dużo bardziej restrykcyjna.

Mając już ogólny zarys mechanizmu, możemy przyjrzeć się każdemu etapowi z osobna. Dla uproszczenia dalszego opisu przyjmijmy, że T to tablica (array/vector) z trzeciego kroku, a Idx to indeks do T otrzymany w wyniku hashowania.

Zazwyczaj programiści nie wymyślają koła na nowo i używają któregoś z popularnych algorytmów, m.in. dlatego, że poprawne hashowanie jest bardzo złożone. Dlatego nie będziemy zagłębiać się w tajniki hashowania, a przyjrzymy się raczej, co taki algorytm może dla nas zrobić i jakiego działania od niego oczekujemy.

Jego głównym zadaniem jest zamienienie klucza, np. string "4spacje" na liczbę. Nie jest wymagane, żeby każdy możliwy klucz dawał inną liczbę, a przy odpowiednio dużej liczbie prób na pewno zaczną się one powtarzać. Trywialna implementacja mogłaby wyglądać tak (pseudokod):

W tym przypadku, ciągi "4spacje" i "ejcaps4" (i wszytkie inne permutacje) dadzą ten sam hash.

Proste hashowanie kluczy poprzez zsumowanie kodu ascii wszystkich liter.

Czego więc oczekujemy od prawidłowej implementacji algorytmu?

• Deterministyczny wynik - to najistotniejsze z wymagań. Dla tych samych danych wejściowych, wygenerowany hash musi być zawsze taki sam. Inaczej nie bylibyśmy w stanie konsekwentnie odtworzyć Idx dla konkretnego klucza.

• Równomierne rozłożenie wygenerowanych liczb - jeden z głównych czynników determinujących wydajność. Hash wpływa bezpośrednio na Idx, a jeżeli te nie będą wykorzystywać całej długości T równomiernie, powstanie więcej kolizji, tj. sytuacji, kiedy Idx jest już zajęty przez inną wartość, co zmusi nas do poszukania innego, wolnego.

• Szybkość działania - celem stosowania tablic mieszającyh jest m.in. szybki dostęp do danych, więc i funkcja hashująca nie może nas spowalniać. To bardzo ogólne stwierdzenie, ale ciężko tu o dokładne granice. Każdy powienien dobrać algorytm odpowiedni do własnych potrzeb.

• Bezpieczeństwo - często wymagane jest, żeby klucz użyty to uzyskania hasha był (prawie) niemożliwy do odtworzenia, lub żeby nie dało się znaleźć dwóch kluczy, które hashują się do tej samej wartości. Trochę szerzej o tym w dalszej części.

• Wysoka entropia - mała zmiana wartości wejściowych powinna dać dużą zmianę na wyjściu. Np. "4spacje" --> 8916259, "3spacje" --> 1112323. Wpływa to na kilka rzeczy, m.in. bardziej równomierne rozłożenie hashy i poprawę bezpieczeństwa.

Jasne jest, że simple_hash() nie spełnia większości tych wymagań.
Po zamienieniu klucza na hash, przekazujemy go do funkcji mapującej.

Naszym celem tutaj jest zamienienie hasha, na mniejszą liczbę, która odpowiada długości T. Jeżeli, na przykład, procedura hashująca może wygenerować liczbę od 0 do 4294967295 (maksymalna 32-bitowa liczba bez znaku), a T ma długość 8, to musimy jakoś zmniejszyć oryginalną wartość do zakresu 0-7. Nie możemy tego jednak zrobić dowolnie, żeby nie zaburzyć równomiernego rozłożenia.

Najprostszym sposobem jest wzięcie reszty z dzielenia hasha przez długość T (hash mod T.len).

Kolizja dwóch różnych hashy.

Jeżeli funkcja hashująca jest solidna, następne kroki można pominąć, a jeżeli produkuje ona większe nieregularności, w tym miejscu można je trochę poprawić. Szczególnym przypadkiem jest sytuacja, kiedy długość T i hash mają zawsze ten sam wspólny dzielnik. Spowoduje to, że hash mod T.len zostawi dziury w regularnych odstępach. To dosyć nietypowe, ale może się przytrafić, kiedy kluczami są wskaźniki (ang. pointer). Ze względu na wyrównanie pamięci, wiele wartości będzie pod adresami, które są potęgą 2, 4, lub 8, a w momencie gdy hasher nie jest zbyt zaawansowany, ta właściwość może się przenieść na sam hash. Jeśli tak jest, użycie reszty z dzielenia nie poprawi sytuacji, wręcz przeciwnie, wyolbrzymi problem.
Żeby temu zaradzić, jedni sugerują, że długość T powinna być zawsze liczbą pierwszą, co zmniejsza szansę na to, że T.len i hash mają wspólny czynnik pierwszy i pomoże rozbić regularności. Zmusi nas to niestety do utrzymania dodatkowej tabeli liczb pierwszych, bo T rzadko ma stały rozmiar (żeby go zmienić trzeba będzie znać inne liczby pierwsze), a dodatkowo, jeżeli wspólny czynnik pierwszy wystąpi mimo to, na co jest realna szansa przy małych rozmiarach T, wszystkie hashe zostaną zmapowane do jednego adresu! Zamiast tego, inni proponują dodatkowy krok polegający na policzeniu reszty z dzielenia przez jakąś liczbę pierwszą P, gdzie P > T. Oznacza to mapowanie hash mod P mod T.

Pośredni krok, w celu lepszego rozłożenia elementów.

Ktoś dociekliwy mógłby zapytać, czemu w ogóle musimy mapować hasha do mniejszej liczby? Skoro hash jest liczbą, to czemu nie użyć go od razu jako Idx? Po co przechodzimy przez mapowanie? Okazuje się jednak, że algorytmy hashujące generują stosunkowo duże liczby (np. 32, 64-bitowe, a często większe). Jeżeli uznalibyśmy, że każda z tych liczb może być indeksem, oznaczałoby to, że w przypadku hasha 32-bitowego, T będzie mieć zajmować ponad 4gb w pamięci, i to jeżeli przechowuje zaledwie 1-bajtowe wartości. Dla 64bit byłoby to o rzędy wielkości więcej.
Noweczesne języki i systemy najczęściej nie przydzielą jednak fizycznej pamięci dla całej tablicy z góry (nawet zainicjalizowanej), a jedna z optymalizacji, dotyczy wysokopoziomowych języków jak JavaScript. Np.:

const backingArray = [];
backingArray[4_294_967_294] = 1;

przydzieli pamięć tylko dla jednego elementu (plus dodatkowy koszt metadanych, których wymaga tablica). Żeby osiągnąć ten efekt, silnik JS najprawdopodobniej umieści nasze dane właśnie w tablicy mieszającej, gdzie kluczem będzie indeks, niejako oszukując użytkownika, że ma do czynienia z ciągłą pamięcią. Ta sama sztuczka będzie użyta, jeżeli tablica zawiera wartości różnych typów, nawet jeśli nie jest rzadka, a na ciągły blok możemy liczyć, jeżeli wszystkie wartości są jednorone, lub użyjemy TypedArray (to gwarantuje ciągłą, zainicjalizowaną pamięć).

Ten etap to tylko formalność. Wiemy już, pod jakim adresem powinien znajdować się klucz. Teraz możemy tę wiedzę wykorzystać. W większości implementacji potrzebne są przynajmniej 3 podstawowe operacje:

- wstawianie (np. insert(), set())
- odczytywanie (np. get(), find())
- usuwanie (np. remove(), delete())

Dodając nowy element do tablicy mieszającej, musimy zapisać w nim m.in. klucz użyty do pozyskania hasha (będzie to potrzebne do rozwiązywania kolizji), oraz opcjonalnie inne dane, np. wartość, którą chcemy powiązać z kluczem (hash map), albo wartość hasha (optymalizacja w późniejszym etapie).

Inne często spotykane operacje to sprawdzanie czy dany wpis istnieje, lub wylistowanie wszystkich wpisów.

Do wystąpienia kolizji niekoniecznie potrzebne są 2 identyczne hashe. Etap mapowania znacznie ogranicza przecież rozpiętość wyników. Jeżeli otrzymamy dwa takie same, pojawia się dodatkowe wyzwanie. Potrzeba sposobu na przechowanie ich obu, jednocześnie rozróżniając, który jest który. Popularne są dwie strategie: metoda łańcuchowa i adresowanie otwarte.

Zamiast umieszczać wpis bezpośrednio pod Idx, T może tak na prawdę przechowywać listy (buckets, albo bins), a każda z nich będzie zbiorem wpisów, których klucz ma taki sam hash. Ze względu na swoją prostotę, częstym wyborem jest tutaj lista powiązana (ang. linked list). W takim przypadku, każdy wpis jest dodawany jako kolejne ogniwo, a chcąc znaleźć jeden konkretny, musimy przejść listę od początku i porównywać klucze. Jest to dosyć czasochłonne, ale przy prawidłowej implementacji, kolizji będzie względnie niewiele, więc i listy nie powinny być długie, a wpływ na złożoność operacji niewielki. Lista powiązana, choć prosta w implementacji, nie zawsze jest najlepszym wyborem. Jeżeli, spodziewamy się wielu kolizji, powinniśmy rozważyć np. drzewo binarne, ze względu na szybsze przeszukiwanie.

Rozwiązywanie kolizji metodą łańcuchową.

Wpisy umieszczane są w T tam, gdzie wskazuje Idx, bez użycia dodatkowej listy. W razie kolizji musimy po prostu znaleźć inny wolny indeks (tzw. sondowanie) i możemy to zrobić w zasadzie w dowolny sposób, jeżeli tylko zachowamy konsekwencję i podtrzymamy determinizm tego procesu. Poniżej trzy często spotykane podejścia. Każde z nich polega na zwiększaniu współczynnika i, aż trafimy na wolny indeks:

Sondowanie liniowe: Idx + i
Sondowanie kwadratowe: Idx + i ²
Podwójne hashowanie: wymaga wygenerowania dwóch różnych hashy. Idx₁ + i * Idx₂

Rozwiązanie kolizji adresowaniem otwartym - sondowanie liniowe

To, jakiego sondowania użyjemy, wpłynie na rozłożenie wpisów. Najprostsze sondowanie liniowe często tworzy skupiska zajętych indeksów, ale inne metody (zwłaszcza podwójne hashowanie) wymagają dodatkowych obliczeń i mniej efektywnie używają pamięci podręcznej (kolejne elementy w czasie sondowania są potencjalnie dalej od siebie w pamięci).

Ciekawym uzupełnieniem tematu występowania kolizji jest paradoks dni urodzin. Spośród losowo wybranych 23 osób, szansa na to że dwie z nich obchodzą urodziny w tym samym dniu wynosi ok. 50%. Ma to przełożenie 1 do 1 na dodawanie elementów do tablicy mieszającej i oznacza, że dla T.len = 100 000, próg 50% osiągniemy już przy 373 dodanych elementach!

Ryzyko wystąpienia przynajmniej jednej kolizji w zależności od ilości elementów dla tablicy mieszającej o długości 100 000

Jeżeli tablica mieszająca zawiera X wpisów, X/T nazywamy jej współczynnikiem obciążenia. Celem jest utrzymanie takiego współczynnika obciążenia, żeby ilość kolidujących wpisów, a tym samym konieczność sprawdzenia więcej niż jednego, była jak najmniejsza.

Początkowo, pamięć którą przydzielamy na T, jest raczej niewielka, np. 8 albo 16 slotów. Jest tak dlatego, że najczęściej nie wiadomo ile elementów będziemy tam przechowywać, a nawet jeżeli znamy maksymalną ich liczbę, jaka może się pojawić w którymś momencie, niekoniecznie chcemy utrzymywać potrzebną na to przestrzeń przez cały czas.
Co w takim razie zrobić, kiedy zbliżamy się do zapełnienia T? Przydzielić nową, większą przestrzeń. Jak bardzo to kosztowne? Tak :)
Mówiąc zupełnie poważnie, ta część jest najbardziej kosztowną operacją w całej strukturze. To nie tylko koszt kopiowania wszystkich danych ze starej tablicy do nowej, trzeba też powtórzyć mapowanie (wynik zależy przecież od długości T), lub nawet hashować każdy klucz od początku, jeśli nie przechowujemy hashy razem z kluczami. Dlatego jeżeli już powiększać to zazwyczaj wykładniczo, np. *2. Dzięki temu, ten skomplikowany proces będzie tym rzadszy, im więcej elementów przechowujemy.

Powiększanie tablicy mieszającej.

Zmniejszanie działa analogicznie, kiedy używamy metody łańcuchowej, ale dostarcza dodatkowych trudności przy adresowaniu otwartym. Biorąc pod uwagę, że wszystkie przechowywane wpisy są tam umieszczone bezpośrednio w T, gdy któryś z nich jest usuwany, nie można po prostu ustawić go jako pusty, bo może to przerwać łańcuch sondowania. Potrzeba dodatkowego markera (ang. tombstone), żeby odróżnić te dwa stany, dzięki czemu w trakcie sondowania, trafiając na usunięty element, wiemy, że może nie być on ostatnim do sprawdzenia i przeskakujemy przez niego, aż do znalezienia prawdziwie pustego elementu.

Tombstone - element oznaczony jako usunięty

Skoro więc nic nie usunęliśmy, współczynnik obciążenia też się nie zmienił i sondowanie zajmuje tyle, ile przed tym zabiegiem. To z kolei oznacza, że obciążenie nie powie nam, kiedy mamy już na tyle mało aktywnych elementów, że czas zmniejszyć T. Sami musimy co jakiś czas upewnić się, czy usuniętych elementów nie zrobiło się za dużo, najlepiej przy okazji jakiejś operacji (np. usuwania).

W ramach małego case study, fragment implementacji hash table z silnika V8, używającej adresowania otwartego, która przy każdym usuwaniu klucza, sprawdza czy aktywnych (nieusuniętych) elementów jest mniej niż 1/4 całkowitej pojemności T, i jeśli tak, wywołuje funkcję rehashującą, przydzielając jednocześnie nową przestrzeń, mniejszą o połowę.

Następnie, w czasie rehashowania (zmiana rozmiaru i przeniesienie elementów), usunięte elementy, nazywane tutaj 'hole', są pomijane, co jest jednoznaczne z ich usunięciem.

Ilość "martwych" wpisów sprawdzana jest też w funkcji powiększającej. Jeżeli jest ich mniej niż połowa aktualnego rozmiaru T, tablica jest powiększana normalnie, w przeciwnym przypadku jest rehashowana, zachowując aktualną pojemność.

W przypadku adresowania otwartego dobrym momentem na zwiększenie rozmiaru, jest obciążenie w okolicach 0.5. Od 0.7 aż do 1.0 (całkowite zapełnienie T), wzrost kolizji jest wykładniczy. Dla metody łańcuchowej wartość 1.0 powinna być dobrym targetem, z powodu optymalnego wykorzystania przestrzeni i zachowania szybkiego dostępu - w idealnym scenariuszu wszytkie buckety są używane, a każdy z nich ma tylko jeden element. Możliwe jest tutaj przekroczenie 1.0, bo buckety mogą teoretycznie zawierać tyle elementów, na ile pozwala pamięć, a akceptowalna wartość może być znacznie wyższa dla bucketów podpartych drzewem binarnym zamiast listy połączonej.

Tak prezentuje się oczekiwana długość sondowania (ilość elementów do sprawdzenia) w zależności od metody rozwiązywania kolizji i współczynnika obiciążenia.

Poglądowa funkcja długości sondowania od współczynnika obiążenia.

Stała złożoność obliczeniowa wszystkich najważniejszych operacji na tablicy mieszającej, to często pojawiające się uproszczenie. Chcąc być precyzyjnym, trzeba dopowiedzieć na ten temat parę słów. Przede wszystkim nie każde O(1) jest takie samo. O(1) dla dostępu do klasycznej tablicy, gdzie potrzebujemy jedynie adresu i przesunięcia, wymaga często jednej instrukcji procesora i jest znacznie szybsze niż wydobycie wartości z tablicy mieszającej, ze wszystkimi czynnościami opisanych do tej pory. Mamy natomiast gwarancję, że czas ten nie zmieni się (pod warunkiem poprawnej implementacji) wraz ze ilością przechowywanych elementów. Oprócz tego każda operacja ma jeszcze mały haczyk.

insert(): O(1) ~*
get(): O(1) ~
remove(): O(1) ~

* oznacza amortyzowany koszt. Pojedyncza akcja tego typu zajmuje zazwyczaj O(1), ale raz na jakiś czas trzeba powiększyć lub zmniejszyć rozmiar T, co znacznie wydłuży tę konkretną operację. O amortyzacji można myśleć jak o rozłożeniu ceny jednej, drogiej operacji na wiele innych, tanich.

~ to oczekiwany koszt. Oczekiwany, nie gwarantowany, ze względu na potencjalne kolizje. Ich wystąpienie wymaga wykonania dodatkowych czynności i zwiększa złożoność operacji, w której wystąpiła. W najgorszym przypadku może to być nawet O(n). Utrzymanie odpowiedniego współczynnika obciążenia i równomierne rozłożenie elementów przybliża nas do O(1).

Zarówno osiągnięcie optymalnej wydajności, jak i jej zmierzenie bywa trudne. Nie ma też jednoznacznych odpowiedzi na to, które rozwiązania sprawdzą się najlepiej, bo każdy ma inne potrzeby. Mogę jednak zwrócić uwagę na kilka zalet i wad poszczególnych implementacji.

Zalety:

- rozwiązanie kolizji wymaga zazwyczaj sprawdzenia mniejszej ilości elementów
- wydajności degraduje się liniowo wraz ze wzrostem współczynnika obiciążenia
- umożliwia proste usuwanie elementów - w przypadku listy połączonej wystarczy podmienić jeden wskaźnik
- dobrze znosi duży współczynnik obciążenia
- potencjalnie prostsza implementacja
- w najgorszym przypadku, złożoność wstawiania, usuwania i wyszukiwania to O(log n), pod warunkiem użycia drzewa binarnego

Wady:

- buckety wymagają alokowania dodatkowej pamięci, zależnej od użytej struktury danych
- przechowywane elementy niekoniecznie znajdują się blisko siebie w pamięci. Podowuje to nieefektywne wykorzystanie pamięci podrecznej i stracony czas na długie wycieczki do RAM'u

Zalety:

- nie wymaga dodatkowej struktury danych na buckety
- sondowanie sprawdza elementy umieszczone blisko siebie w pamięci. Być może nawet cała tablica znajduje się w cache'u L1

Wady:

- sprawdza średnio więcej elementów, jeśli trafimy na kolizję
- usuwanie elementów jest dosyć skomplikowane.
- gorzej znosi duży współczynnik obciążenia
- może być trudniej utrzymać równomierne rozłożenie kluczy (sondowanie)
- w najgorszym przypadku, złożoność wstawiania, usuwania i wyszukiwania to O(n)

Funkcje hashujące nie sa tajemnicą, a oprogramowanie jest często otwartoźródłowe. Jeżeli, dodatkowo, użytkownik ma wpływ na zawartość tablicy mieszającej (przesłane przez niego wartości są używane jako klucze), ktoś o złośliwych zamiarach, znając algorym, mógłby znaleźć wiele wartości, których wynikiem jest ten sam hash i za ich pomocą sprowadzić tablicę mieszającą do najgorszej możliwej wydajności, tworząc ogromną ilość kolizji (atak DoS).
Na szczęście jest w miarę prosty sposób, żeby temu zapobiec. Kiedy tablica mieszająca jest inicjalizowana, można wygenerować dodatkowy, unikalny dla niej ciąg znaków (ang. salt), a potem dodać go do każdego klucza przed hashowaniem, dzięki czemu atakujący nie będzie już w stanie przewidzieć hasha na podstawie samego algorytmu.

Mechanizmy hashowania nie dotyczą bezpośrednio tablicy mieszającej i wykraczają poza zakres tego artykułu, ale warto wspomnieć, że jeżeli dane, które przechowujemy, są poufne, np. hasła użytkowników, trzeba przyłożyć znacznie większą uwagę do zabezpieczenia ich hashy metodami kryptograficznymi. Salt nie wystarczy do obrony przed coraz większą mocą obliczeniową nowoczesnych komputerów. Atakujący mogą wykraść hashe z systemu, na którym są przechowywane, a następnie metodą siłową próbować odtworzyć oryginalne wartości.

Mechanizmy, które tu opisałem, należą do podstaw wiedzy o tablicach mieszających. Powstało wiele innych ciekawych implementacji i jest to prawdziwa królicza nora. Szczególnie polecam wykład na temat jednej z nich - SwissTable, która jest dzisiaj częścią takich jezyków jak C++, Rust, czy Go. Zachęcam również do zgłębienia podstaw w książce "The Joys of Hashing: Hash Table Programming with C" autorstwa Thomasa Mailunda, na której oparłem sporą część tego artykułu. Zawiera ona o wiele więcej szczegółów i analiz, a także kod w C.