Tablice mieszające: co naprawdę siedzi w słowniku i tablicy asocjacyjnej

Słownik w Pythonie, HashMap w Javie, tablica asocjacyjna w PHP, obiekt w JavaScripcie – wszystkie mają tę samą obietnicę: podajesz klucz, dostajesz wartość, a czas nie zależy od tego, ile elementów jest w środku. To najczęściej używana struktura danych w codziennym kodzie i jednocześnie ta, o której najrzadziej myślimy. A warto, bo obietnica ma drobnym drukiem dopisane „średnio” – i widzieliśmy już, co się dzieje, gdy ktoś celowo doprowadzi do najgorszego przypadku.

To pierwsza część serii o strukturach danych, w której interesuje mnie nie definicja, tylko konsekwencje: co z tego wynika dla twojego kodu, dla bazy i dla bezpieczeństwa aplikacji.

Skrót zamiast szukania

Pomysł jest prosty do bólu. Mamy tablicę o n kubełkach i funkcję, która z klucza robi liczbę. Reszta z dzielenia tej liczby przez n wskazuje kubełek. Nie szukamy – liczymy adres.

Powyżej 24 losowe klucze wpadają do 16 kubełków. Zwróć uwagę na dwie rzeczy: kubełki wypełniają się nierówno (to normalne – przy losowym rozrzucie zawsze tak jest) i licznik porównań rośnie bardzo wolno. Teraz przełącz listę na klucze kolizyjne i uruchom jeszcze raz.

Cała tablica zamienia się w jedną listę: jeden kubełek bierze wszystkie klucze, piętnaście pozostałych stoi pustych. Dostęp w czasie stałym znika, bo każde kolejne wstawienie musi przejść przez wszystko, co już w tym kubełku leży – pomarańczowe ogniwo wędrujące w dół kolumny to właśnie ten przegląd. Na koniec licznik pokazuje 276 porównań zamiast dwudziestu kilku, czyli znowu n(n−1)/2. To nie jest usterka implementacji – to definicja: tablica mieszająca jest szybka pod warunkiem, że skróty rozkładają się równomiernie.

Dwie szkoły radzenia sobie z kolizjami

Łańcuchowanie (Java, PHP, większość podręczników): kubełek trzyma listę par klucz-wartość. Proste, odporne na wysokie wypełnienie, ale każdy element to osobny obiekt w pamięci – a to znaczy skok wskaźnikowy przy każdym porównaniu.

Adresowanie otwarte (CPython, Rust): wszystko leży w jednej tablicy, a przy kolizji szukamy kolejnego wolnego miejsca według ustalonej reguły. Dane siedzą obok siebie, więc procesor czyta je z pamięci podręcznej – szybciej, ale przy dużym wypełnieniu wydajność gwałtownie spada i trzeba pilnować progu.

Poniżej wersja z łańcuchami, żeby zobaczyć mechanikę bez magii:

# Python
class HashTable:
    """Tablica mieszająca z łańcuchowaniem – tyle wystarczy, żeby zobaczyć mechanikę."""

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

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for i, (existing, _) in enumerate(bucket):
            if existing == key:               # klucz już jest: podmieniamy wartość
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            self._grow()

    def get(self, key, default=None):
        for existing, value in self._bucket(key):
            if existing == key:
                return value
        return default

    def _grow(self):
        """Podwojenie pojemności wymaga PRZELICZENIA wszystkich skrótów od nowa."""
        old = self.buckets
        self.buckets = [[] for _ in range(2 * len(old))]
        self.size = 0
        for bucket in old:
            for key, value in bucket:
                self.put(key, value)

Współczynnik wypełnienia, czyli dlaczego słownik czasem przycina

Metoda _grow jest tu najciekawsza. Gdy tablica zapełni się powyżej pewnego progu (u mnie 0,75; CPython używa 2/3), trzeba ją powiększyć – a to znaczy przeliczyć skróty wszystkich kluczy od nowa, bo reszta z dzielenia zmienia się razem z liczbą kubełków.

Pojedyncze wstawienie kosztuje wtedy O(n), a nie O(1). W praktyce nie boli, bo tablica podwaja rozmiar: przepisanie zdarza się coraz rzadziej i koszt amortyzowany jednego wstawienia zostaje stały. Ale jeśli mierzysz czas pojedynczych operacji, zobaczysz w wykresie regularne piki – to właśnie przepisywanie. Wiedząc, ile elementów wstawisz, warto od razu poprosić o odpowiednią pojemność (new HashMap<>(1000) w Javie, dict.fromkeys(...) czy wstępna alokacja w innych językach).

Kontrakt, który łatwo złamać

Tablica mieszająca opiera się na umowie między dwiema operacjami: jeśli dwa obiekty są równe, muszą mieć ten sam skrót. Odwrotnie być nie musi – dwa różne obiekty mogą mieć ten sam skrót i po to jest cała maszyneria kolizji.

Złamanie tej umowy nie kończy się wyjątkiem. Kończy się cichym gubieniem danych:

# Python
class Punkt:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

    # UWAGA: brak __hash__ przy własnym __eq__ czyni obiekt niehaszowalnym w Pythonie,
    # ale w wielu językach dostaniesz zamiast tego skrót z adresu w pamięci...

klucze = {Punkt(1, 2): "a"}      # TypeError: unhashable type

Python broni cię tu z urzędu: definiując __eq__, tracisz domyślny __hash__ i obiekt przestaje nadawać się na klucz. W Javie czy C# nikt cię nie zatrzyma – przesłonisz equals bez hashCode, a mapa zacznie gubić wpisy, bo szuka ich w kubełku wyliczonym ze starego, adresowego skrótu.

Druga zasada wynika z pierwszej: klucz musi być niezmienny. Jeśli po wstawieniu zmienisz pole, z którego liczony jest skrót, obiekt zostaje w kubełku, w którym już nikt go nie znajdzie. Dlatego kluczem w Pythonie może być krotka, ale nie lista.

# Python
from dataclasses import dataclass

@dataclass(frozen=True)      # frozen=True daje __hash__ i blokuje zmianę pól
class Punkt:
    x: int
    y: int

{Punkt(1, 2): "a"}[Punkt(1, 2)]     # "a" – działa, bo skrót i równość są spójne

Kiedy tablica mieszająca to zły wybór

Skoro jest tak szybka, po co reszta serii? Bo tablica mieszająca gubi porządek. Nie odpowie na pytania:

• podaj wszystkie klucze z przedziału od X do Y,
• podaj najmniejszy klucz większy niż X,
• przejdź elementy w kolejności rosnącej.

Każde z nich wymaga przejrzenia całości i posortowania – czyli O(n log n) zamiast O(log n). Do takich pytań służą drzewa, którym poświęcę trzecią część tej serii, a ich dyskowej odmianie z baz danych – czwartą.

Trzy różne rzeczy nazywane skrótem

To rozróżnienie kosztuje ludzi realne pieniądze, więc powtórzę je z naciskiem. Słowo „hash” oznacza w informatyce trzy różne narzędzia o sprzecznych wymaganiach:

1. Skrót do wyszukiwania (hash() w Pythonie, hashCode() w Javie). Ma być szybki i równomiernie rozrzucać wartości. Nie ma być bezpieczny – i nie jest. Skrót napisu z Javy da się odwrócić na kartce.

2. Skrót kryptograficzny (SHA-256, BLAKE3). Ma być odporny na znalezienie dwóch wiadomości o tym samym skrócie i na odtworzenie wiadomości ze skrótu. Jest wolniejszy o rzędy wielkości. Służy do sum kontrolnych plików, podpisów, identyfikatorów treści – i tu wraca wątek cyfr kontrolnych, tylko na zupełnie innym poziomie odporności.

3. Skrót do haseł (Argon2id, scrypt, bcrypt). Ma być celowo wolny i pamięciożerny, żeby atakujący z kartą graficzną nie mógł sprawdzać miliardów kandydatów na sekundę. OWASP zaleca dziś w pierwszej kolejności Argon2id z parametrami m=19456 (19 MiB pamięci), t=2, p=1, a bcrypt tylko dla systemów starszego typu, z czynnikiem pracy co najmniej 10 i pamiętaniem o limicie 72 bajtów hasła.

Użycie SHA-256 do haseł jest błędem dokładnie z tego powodu: SHA jest za szybki. Użycie Argon2 jako klucza słownika też jest błędem – tylko śmieszniejszym w skutkach.

# Python
import hmac
from hashlib import sha256

def token_ok(podany: str, oczekiwany: str) -> bool:
    """Porównanie odporne na atak czasowy – zawsze ten sam czas, niezależnie od różnicy."""
    return hmac.compare_digest(sha256(podany.encode()).digest(),
                               sha256(oczekiwany.encode()).digest())

Zwykłe == na sekretach kończy porównanie na pierwszym różnym bajcie. Różnica czasu jest mikroskopijna, ale mierzalna – i wystarcza, żeby odgadywać token bajt po bajcie zamiast zgadywać całość. hmac.compare_digest (i jego odpowiedniki: hash_equals w PHP, MessageDigest.isEqual w Javie) porównuje zawsze całość.

Podsumowanie

Tablica mieszająca to najlepszy domyślny wybór, kiedy pytasz o konkretny klucz i nie obchodzi cię porządek. Przestaje nim być, gdy pytania robią się zakresowe – albo gdy klucze pochodzą od kogoś, kto czytał tę samą dokumentację co ty.

W następnej części schodzimy o poziom niżej: do wyszukiwania liniowego i binarnego, czyli dwóch pętli, które wyglądają na trywialne, a mimo to jedna z nich kryła w bibliotece standardowej Javy błąd przez dziewięć lat.