Wyszukanie klucza w Pythonowym dict z dziesięcioma wpisami zajmuje tyle samo czasu, co w dict z dziesięcioma milionami. To nie wynika z szybkości języka. Pythonowy dict, Javowy HashMap i Map w JavaScript to wszystko tabele haszujące, a cały ten projekt istnieje po to, by wyszukiwanie, wstawianie i usuwanie działały średnio w O(1). Notacja Big O nazywa to wyszukiwanie “czasem stałym”. Oto mechanizm, który na to zasługuje.

Jak tabela haszująca zmienia klucz w indeks tablicy

Tabela haszująca to tablica plus funkcja, która zmienia klucz w pozycję w tej tablicy.

1

indeks kubełka = hash(klucz) % liczba_kubełków

hash() przyjmuje klucz dowolnego rozmiaru (string, tuple, obiekt) i zwraca liczbę całkowitą. W ramach jednego uruchomienia programu ten sam klucz zawsze daje tę samą liczbę, a dobra funkcja hashująca rozprowadza te liczby prawie równomiernie po całym zakresie wyjściowym. Bierzesz tę liczbę modulo długość tablicy i masz slot. Zapisujesz tam klucz i wartość. Kolejne wyszukanie liczy ten sam hash, trafia w ten samy slot i odczytuje wartość. Żadnego przeglądania, żadnego porównywania z innymi kluczami.

Wszystko inne w prawdziwej tabeli haszującej, od obsługi kolizji przez zmianę rozmiaru po dokładną sekwencję sondowania, służy temu, żeby to jednokrokowe wyszukiwanie działało, gdy tabela się wypełnia.

Minimalna wersja ignorująca kolizje:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class TinyTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [None] * size

    def put(self, key, value):
        index = hash(key) % self.size
        self.buckets[index] = (key, value)

    def get(self, key):
        index = hash(key) % self.size
        if self.buckets[index] is None:
            raise KeyError(key)
        stored_key, value = self.buckets[index]
        if stored_key != key:
            raise KeyError(key)
        return value

1
2
3
4

>>> t = TinyTable()
>>> t.put("user:42", {"name": "Dana"})
>>> t.get("user:42")
{'name': 'Dana'}

To się psuje, gdy dwa różne klucze zahaszują na ten sam indeks. hash("user:42") % 8 i hash("user:17") % 8 mogą obie wyjść 3, a TinyTable ma miejsce tylko na jeden z nich: drugie put bez ostrzeżenia nadpisuje pierwsze. To jest kolizja.

Jak tabele haszujące obsługują kolizje: chaining vs. open addressing

Są dwa standardowe sposoby zachowania obu kluczy, gdy trafiają w ten sam slot.

Chaining zmienia każdy kubełek w mały kontener, zwykle listę wiązaną. Kolizja znaczy, że kubełek trzyma dwa wpisy zamiast jednego, a wyszukiwanie przechodzi przez tę listę, aż znajdzie pasujący klucz.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class ChainedTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def put(self, key, value):
        index = hash(key) % self.size
        bucket = self.buckets[index]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self.buckets[hash(key) % self.size]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

HashMap w Javie to tabela z chainingiem. Każdy kubełek zaczyna jako lista wiązana. Jeśli kubełek zbierze co najmniej 8 wpisów, a tabela ma co najmniej 64 kubełki, ten kubełek zmienia się w czerwono-czarne drzewo (TREEIFY_THRESHOLD i MIN_TREEIFY_CAPACITY w kodzie JDK), dzięki czemu przeglądanie O(n) w najgorszym przypadku przeciążonego kubełka staje się O(log n). Wraca do listy, jeśli zmiana rozmiaru zostawi mu 6 wpisów lub mniej.

Open addressing trzyma każdy wpis prosto w tablicy, bez dodatkowej struktury i bez wskaźników. Przy kolizji sonduje: próbuje innego slotu, według ustalonej reguły, aż znajdzie wolny. dict w CPythonie działa właśnie tak, a komentarz o wyszukiwaniu w Objects/dictobject.c podaje powód: “Open addressing is preferred over chaining since the link overhead for chaining would be substantial.” CPython unika też czystego liniowego sondowania, które mocno się zlepia, gdy klucze pojawiają się w przewidywalnej kolejności. Każdy krok sondowania miesza więcej bitów hasza w następny indeks, więc dwa klucze, które zderzają się na niskich bitach, rozdzielają się po kilku krokach.

Obie strategie zawodzą inaczej. Tabela z chainingiem, która się wypełnia, staje się wolniejsza, a w najgorszym przypadku każdy wpis trafia do jednej długiej listy. Tabela z open addressing nie ma gdzie wsadzić wpisu, kiedy tablica jest pełna, więc musi zmienić rozmiar, zanim do tego dojdzie.

Co to jest load factor i czemu tabela zmienia rozmiar przed zapełnieniem

Load factor to liczba wpisów podzielona przez liczbę kubełków. Obie strategie go śledzą, żeby zdecydować, kiedy zmienić rozmiar, a Java i CPython wybierają różne progi.

HashMap w Javie zmienia rozmiar, gdy liczba wpisów przekroczy pojemność razy load factor. Javadoc konstruktora bez argumentów podaje wartości domyślne: 16 kubełków, load factor 0,75, więc pierwsza zmiana rozmiaru następuje przy 12. wpisie. Zmiana rozmiaru w przybliżeniu podwaja liczbę kubełków i ponownie haszuje każdy istniejący wpis do nowej tablicy. Dlatego Javadoc poleca ustalić rozmiar mapy z góry za pomocą HashMap.newHashMap(expectedSize) (Java 19+), gdy z góry wiesz, ile wpisów będzie w niej trzymanych: unikasz powtarzających się rehaszów.

dict w CPythonie zmienia rozmiar później i rośnie szybciej. Komentarz USABLE_FRACTION w kodzie mówi, że tabela zmienia rozmiar, gdy jest wypełniona w dwóch trzecich, a GROWTH_RATE ustawia rozmiar nowej tabeli na około trzy razy aktualną liczbę żywych wpisów, a nie na proste podwojenie.

Żadna z tych liczb nie jest przypadkowa. Load factor bliski 1 wypełnia tablicę maksymalnie, ale sprawia, że każda operacja staje się wolniejsza, gdy kubełki się zapełniają; load factor bliski 0 zużywa pamięć na sloty, których nikt jeszcze nie używa. Oba projekty osiadają między 0,66 a 0,75, gdzie dodatkowa pamięć przestaje kupować znacznie krótsze sondowania.

Czemu wyszukiwanie w tabeli haszującej jest O(1) średnio, nie zawsze

Czas stały trzyma się tylko tak długo, jak hasze rozprowadzają klucze prawie równomiernie między kubełki. Dwie rzeczy to łamią.

Słaba lub przewidywalna funkcja haszująca. Jeśli każdy wstawiany klucz haszuje do tego samego kubełka, tabela z chainingiem degeneruje do jednej listy wiązanej z wyszukiwaniem O(n) - dokładnie tego, czemu ta struktura miała zapobiegać. Dzieje się to na produkcji. Serwer, który haszuje dane kontrolowane przez atakującego (nazwy pól formularza, nagłówki HTTP, klucze JSON) przewidywalną funkcją, jest narażony na atak przez złożoność algorytmiczną: atakujący wysyła tysiące kluczy zbudowanych tak, by się zderzały, i wymusza najgorsze zachowanie przy każdym żądaniu. Python od wersji 3.3 randomizuje hasz str i bytes na poziomie procesu (kontrolowane przez PYTHONHASHSEED) właśnie z tego powodu. Ten sam string haszuje się różnie w dwóch uruchomieniach interpretera, więc nikt nie może z wyprzedzeniem policzyć zestawu kolizji offline.

Zmiana klucza po wstawieniu. Kubełek, w którym żyje klucz, został wybrany na podstawie jego hasza, więc tabela przyjmuje, że ten hasz nigdy się nie zmieni. Python wymusza to na poziomie typu: mutowalne wbudowane typy jak list i dict ustawiają __hash__ na None, a użycie jednego z nich jako klucza wywołuje TypeError: unhashable type: 'list', zanim błąd zdąży się zdarzyć. Tuple i stringi są haszowalne, bo są niemutowalne. Dla własnej klasy klucza zaimplementuj __hash__ i __eq__ razem i oprzyj je tylko na polach, które nigdy się nie zmieniają. W przeciwnym razie zmieniony klucz “gubi się”: wpis wciąż jest w tabeli, w kubełku wskazywanym przez jego stary hasz, ale wyszukiwanie szuka gdzie indziej.

Kiedy nie używać tabeli haszującej

Tabela haszująca szybko odpowiada na jedno pytanie: czy ten klucz istnieje i jaka jest jego wartość? Prawie wszystko inne robi słabo.

  • Zapytania o zakres i kolejność. “Wszyscy użytkownicy utworzeni w tym miesiącu” albo “następny klucz po tym” potrzebują struktury sortowanej. Tabela haszująca nie ma kolejności. dict w CPythonie gwarantuje kolejność wstawiania od wersji 3.7, ale to kolejność iteracji, nie kolejność sortowania, i nic nie daje przy “wszystko między X i Y”. Takim zapytaniem dobrze zajmuje się B-drzewo, dlatego większość baz danych domyślnie używa indeksów B-drzewa, a nie indeksów haszujących. Jak działają indeksy w bazie danych opisuje kompromis skanowania i seeka stojący za tym domyślnym wyborem.
  • Dopasowanie po prefiksie lub rozmyte. “Klucze zaczynające się od user:” znaczy sprawdzenie każdego klucza po kolei. Trie albo sortowana struktura z wyszukiwaniem binarnym robi to bezpośrednio.
  • Małe klucze całkowite w wąskim zakresie. Jeśli klucz jest już dniem tygodnia albo klasą kodu statusu HTTP, pomiń funkcję haszującą i indeksuj tablicę prosto. Jedna warstwa mniej, żadnych kolizji.

Kiedy tabela haszująca jest właściwą strukturą, prawie nigdy nie piszesz jej sam od zera. dict, HashMap, Map i std::unordered_map są już zoptymalizowane i poprawne. Używasz ich też pośrednio częściej, niż myślisz: funkcja opatrzona functools.lru_cache, opisana w Dekoratory w Pythonie wyjaśnione, buduje klucz z argumentów wywołania i szuka go w dict.

Decyzja jest więc krótka. Jeśli operacja to “znajdź to po dokładnym kluczu”, użyj wbudowanej tabeli haszującej i nie pisz własnej. Jeśli pytanie dotyczy kolejności, zakresów albo częściowych dopasowań, od razu wybierz sortowaną strukturę albo trie, bo żadna funkcja haszująca nie naprawi struktury, która odpowiada na niewłaściwe pytanie.

Powiązane artykuły