Haszowanie to jeden z najczęstszych wzorców na rozmowie technicznej. Większość zadań typu „znajdź duplikat", „dopasuj parę", „policz wystąpienia" czy „pogrupuj elementy" sprowadza się do hash setu lub hash mapy zamiast podwójnej pętli.
W tym artykule pokazuję praktyczne zastosowania hashowania jako narzędzia algorytmicznego: kiedy lookup w set lub dict wygrywa z liniowym skanem listy, jakie zadania klasyczne pasują do wzorca i gdzie haszowanie nie pomoże. Implementacje są w Pythonie, ale wzorzec jest language-agnostic — analogicznie zachowa się w Javie, Ruby czy JavaScript.
Pozostaję w obrębie struktur danych jako struktur algorytmicznych. Haszowanie kryptograficzne (SHA-256, password hashing) to inna domena i celowo jej tu nie poruszam.
Co haszowanie daje na rozmowie
Haszowanie jest wzorcem zmiany pytania z „czy element jest gdzieś w liście?" na „czy element jest w strukturze z szybkim lookupem?". To często redukuje koszt z liniowego skanowania do średniego O(1).
Intuicja: tablica hashująca to tablica „bucketów". Funkcja hash(klucz) % size zwraca indeks bucketu, gdzie wartość trafia. Lookup nie iteruje po wszystkich elementach — przechodzi prosto do właściwego bucketu, czasem przeskakując o kilka pozycji w razie kolizji.
hash table (size=8):
bucket 0 1 2 3 4 5 6 7
. . . ("foo") ("bar") . . .
↑ ↑
hash("foo") = 3 hash("bar") = 4
lookup "foo": hash("foo")=3 → bucket[3] zawiera "foo" → znaleziono w 1 kroku
lookup "xyz": hash("xyz")=2 → bucket[2] puste → nie ma w hash table
Na rozmowie technicznej ta intuicja jest ważniejsza niż sama składnia. Gdy widzisz powtarzające się wyszukiwanie, sprawdzanie obecności albo dopasowywanie par, hash set lub hash map zwykle są pierwszym kandydatem. Asymptotycznie różnica między lookup w liście a lookup w hash table jest dramatyczna — szczegóły w Big O w 10 minut.
numbers = [4, 9, 1, 7, 3]
lookup = set(numbers)
print(7 in numbers) # expected_output: True
print(7 in lookup) # expected_output: True
print(8 in lookup) # expected_output: False
set vs dict w Pythonie
set odpowiada na pytanie „czy ta wartość już wystąpiła?". dict odpowiada na pytanie „jaka informacja jest przypisana do tego klucza?". Obie struktury używają haszowania, ale modelują inne zamiary.
W praktyce set wybierasz dla obecności, unikalności i operacji zbiorowych (suma, część wspólna, różnica). dict wybierasz dla indeksów, liczników, grupowania, cache oraz mapowania wartości wejściowej na stan pomocniczy.
seen = set()
positions = {}
for index, value in enumerate(["a", "b", "a"]):
seen.add(value)
positions[value] = index
print("a" in seen) # expected_output: True
print(positions["a"]) # expected_output: 2
print(sorted(seen)) # expected_output: ['a', 'b']
Two Sum jako hash map one-pass
Two Sum to klasyczne pytanie: znajdź dwa indeksy w liście, dla których suma wartości równa się celowi. Dla każdego elementu liczysz complement = target - num i sprawdzasz, czy complement był już widziany w hash mapie. Jeśli tak, masz parę indeksów bez drugiej pętli.
Intuicja: brute force porównuje każdą parę i kosztuje O(n²) — szybko przegrywa na większych danych. Wersja one-pass działa w czasie O(n), używając O(n) dodatkowej pamięci na mapę wartości do indeksów. To podręcznikowy przykład wzorca „płać pamięcią za czas".
def two_sum(numbers, target):
seen = {}
for index, num in enumerate(numbers):
complement = target - num
if complement in seen:
return [seen[complement], index]
seen[num] = index
return []
print(two_sum([2, 7, 11, 15], 9)) # expected_output: [0, 1]
print(two_sum([3, 2, 4], 6)) # expected_output: [1, 2]
Trace dla two_sum([2, 7, 11, 15], 9):
Krok 1: index=0, num=2, complement=7, seen={} — brak → dodajemy seen={2: 0}.
Krok 2: index=1, num=7, complement=2, seen={2: 0} — znaleziono! → return [0, 1].
Klucz: w momencie znalezienia 7, wartość 2 już jest w mapie, bo dodaliśmy ją w poprzedniej iteracji. Sprawdzamy complement przed dodaniem bieżącej liczby, żeby uniknąć użycia tego samego indeksu dwa razy.
Wykrywanie duplikatów przez seen = set()
Wzorzec seen = set() polega na przejściu po danych i zapamiętywaniu wartości, które już wystąpiły. Pierwsze ponowne trafienie oznacza duplikat, bez sortowania i bez porównywania każdej pary.
Czas działania to O(n), a pamięć rośnie do rozmiaru zbioru unikalnych wartości. Wzorzec zostaje ten sam przy bardziej złożonych warunkach, np. „pierwszy znak, który się powtarza w stringu" albo „pierwsza powtórzona wartość w strumieniu".
def has_duplicate(values):
seen = set()
for value in values:
if value in seen:
return True
seen.add(value)
return False
print(has_duplicate([1, 2, 3, 2])) # expected_output: True
print(has_duplicate([1, 2, 3])) # expected_output: False
Anagram check przez frequency map
Dwa stringi są anagramami, jeśli mają identyczne liczności znaków. Frequency map przechowuje znak jako klucz i liczbę wystąpień jako wartość — porównanie map daje odpowiedź w czasie O(len(left) + len(right)), zwykle skraca się to do O(n).
Alternatywą jest sorted(s1) == sorted(s2), ale sortowanie kosztuje O(n log n). Frequency map jest lepszym wzorcem, gdy zadanie dotyczy liczności, a nie porządku znaków.
def build_counts(text):
counts = {}
for char in text:
counts[char] = counts.get(char, 0) + 1
return counts
def is_anagram(left, right):
return build_counts(left) == build_counts(right)
print(is_anagram("listen", "silent")) # expected_output: True
print(is_anagram("rat", "car")) # expected_output: False
Frequency count i top-K elementów
Liczenie częstotliwości to jeden z najczęstszych powodów użycia hash mapy. Klucz reprezentuje element, a wartość reprezentuje licznik, który aktualizujesz podczas pojedynczego przejścia po danych.
W Pythonie collections.Counter jest wyspecjalizowaną podklasą dict. Daje gotowe narzędzia do zliczania, a Counter("abc").most_common(2) zwraca top-K elementów według częstości. Przy remisach w Pythonie 3.7+ kolejność wynika z kolejności pierwszego napotkania elementów.
from collections import Counter
text = "interview"
counts = Counter(text)
top_two = counts.most_common(2)
print(top_two) # expected_output: [('i', 2), ('e', 2)]
print(counts["v"]) # expected_output: 1
print(Counter("abc").most_common(2)) # expected_output: [('a', 1), ('b', 1)]
Group by i grupowanie anagramów
Group by przez hash mapę polega na zbudowaniu klucza, który reprezentuje cechę grupującą, i dorzucaniu do listy pod tym kluczem. Wzorzec działa dla anagramów (klucz: posortowany string), bukietów liczb (klucz: parzystość), kategorii (klucz: typ).
Klucz musi być hashable, więc często jest tuple albo string. Wartość bywa listą, setem albo licznikiem, w zależności od tego, co później chcesz odczytać z grupy.
def group_anagrams(words):
groups = {}
for word in words:
key = "".join(sorted(word))
groups.setdefault(key, []).append(word)
return [sorted(values) for values in groups.values()]
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# expected_output: [['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]
Hashable vs unhashable
Klucz w dict lub element w set musi być hashable: jego __hash__ musi być zdefiniowany i stabilny w czasie życia obiektu. Wbudowane list, set i dict są niehashowalne, bo ich zawartość i równość mogą się zmieniać w czasie.
Intuicja: hash table polega na fakcie, że hash(key) zawsze zwraca tę samą wartość. Gdyby klucz był mutable i ktoś by go zmodyfikował już po wstawieniu, hash przesunąłby się do innego bucketu — i lookup nigdy by go nie znalazł.
tuple jest hashable, jeżeli wszystkie jej elementy są hashowalne — inaczej także traci tę własność. frozenset jest hashowalny tylko, gdy wszystkie jego elementy są hashowalne.
key_ok = ("user", 42)
hash(key_ok)
try:
hash(("user", [1, 2]))
except TypeError as error:
print(type(error).__name__) # expected_output: TypeError
print(isinstance(frozenset({1, 2}), frozenset)) # expected_output: True
Hash collision i koszt operacji
Hash collision występuje, gdy różne klucze trafiają do tej samej pozycji tablicy haszującej. Pythonowe słowniki używają open addressing z perturbacją, żeby efektywnie szukać kolejnego miejsca w tablicy, zamiast trzymać listę kolizji per bucket.
Średnie O(1) dla lookupu zakłada dobry rozkład hashy i kontrolowany poziom zapełnienia. W najgorszym przypadku, gdy wiele kluczy koliduje, operacje mogą zachowywać się jak O(n) — co jest podstawą ataków HashDoS. Klasyfikacja: średnio O(1), pesymistycznie O(n).
class BadKey:
def __init__(self, value):
self.value = value
def __hash__(self):
return 1
def __eq__(self, other):
if not isinstance(other, BadKey):
return NotImplemented
return self.value == other.value
items = {BadKey(i): i for i in range(3)}
print(items[BadKey(2)]) # expected_output: 2
Hash randomization i kolejność w Pythonie
Od Pythona 3.3 hash dla str i bytes jest randomizowany przy starcie procesu. PEP 456 ustandaryzował SipHash jako domyślny algorytm w CPythonie 3.4. Można to wyłączyć przez PYTHONHASHSEED=0, ale w testach zwykle pinujesz ziarno tylko, gdy musisz porównywać kolejność.
dict zachowuje insertion order od Pythona 3.7 — to gwarancja językowa. set nie daje takiej gwarancji, więc do testów używaj print(sorted(set_var)) zamiast bezpośredniego stringu.
values = {"plum", "apple", "pear"}
ordered = {"first": 1, "second": 2}
print(sorted(values)) # expected_output: ['apple', 'pear', 'plum']
print(list(ordered.keys())) # expected_output: ['first', 'second']
print("PYTHONHASHSEED" in "PYTHONHASHSEED=0") # expected_output: True
Idempotent set operations
Operacje zbiorowe są zwięzłym sposobem wyrażania logiki: a | b to suma, a & b część wspólna, a - b różnica, a a ^ b różnica symetryczna. Wynik nie zależy od duplikatów wejścia.
Idempotencja oznacza, że ponowne dodanie tego samego elementu nie zmienia zbioru. To jest użyteczne przy deduplikacji, uprawnieniach, tagach, filtrach i porównywaniu dwóch zestawów wartości.
left = {"read", "write", "read"}
right = {"write", "delete"}
union = left | right
intersection = left & right
difference = left - right
symmetric = left ^ right
print(sorted(union)) # expected_output: ['delete', 'read', 'write']
print(sorted(intersection)) # expected_output: ['write']
print(sorted(difference)) # expected_output: ['read']
print(sorted(symmetric)) # expected_output: ['delete', 'read']
Sygnały rozpoznawcze zadań na haszowanie
Zadanie pachnie hash setem/hash mapą, gdy widzisz w opisie te frazy. Sygnał → wzorzec:
"znajdź duplikat / pierwszy powtarzający się" → seen = set()
"znajdź parę o sumie X / two sum / pair sum" → hash map complement lookup
"czy są anagramami / permutation / mają te same → frequency map (Counter)
znaki"
"ile wystąpień / top-K / najczęstszy" → Counter.most_common(K)
"pogrupuj X po cesze Y" → dict[Y].append(X)
"czy widziałem już ten klucz/wartość" → set membership
"unikalne elementy / dedup" → set() albo dict.fromkeys()
"szybki lookup po dokładnym kluczu" → dict[key]
Sygnał odwrotny — kiedy hash NIE pasuje: „posortuj", „k-ty najmniejszy", „range query", „percentyl", „następny większy". Tu lepsze są drzewa BST, heap albo sorted array z bisect (porównanie strategii: Wyszukiwanie binarne).
Kiedy hash nie pasuje
Hash table jest świetny do lookupu po dokładnym kluczu, ale słaby, gdy potrzebujesz porządku, zapytań zakresowych albo percentyli. Sama tablica hashująca nie utrzymuje relacji porządku typu „mniejsze, większe, następne".
Konkretny anty-przykład: zadanie „znajdź wszystkie wartości w przedziale [low, high] w kolekcji 1 mln liczb". Naiwne podejście to wciśnięcie wartości do set i ręczne skanowanie po wszystkich kluczach — O(n) za każdy range query. Sortowanie + bisect_left / bisect_right daje O(log n) per query po jednorazowym koszcie sortowania O(n log n).
import bisect
scores = [10, 20, 30, 40, 50]
left = bisect.bisect_left(scores, 20)
right = bisect.bisect_right(scores, 40)
range_count = right - left
print(range_count) # expected_output: 3
print(scores[left:right]) # expected_output: [20, 30, 40]
Najczęstsze błędy
Traktowanie in list i in set jako równoważnych kosztowo. in list to O(n) (skan), in set średnio O(1). Przy 10⁶ lookupów na 10⁶-elementowej liście różnica to 10¹² vs 10⁶ operacji. Naprawa: zawsze gdy widzisz powtarzające się in collection, konwertuj kolekcję na set() raz przed pętlą.
W Two Sum: dodanie bieżącej liczby do mapy przed sprawdzeniem complementu. Algorytm użyje wtedy tego samego indeksu dwa razy. Wejście [3], target=6: complement=3, seen={3:0}, znajduje match z samym sobą → zwraca [0,0]. Naprawa: zawsze if complement in seen PRZED seen[num] = index.
Sprawdzanie anagramów tylko przez długość i zbiór znaków. "aab" i "abb" mają tę samą długość i ten sam zbiór {'a','b'}, ale nie są anagramami — różne liczności. Naprawa: porównuj Counter(left) == Counter(right) albo sorted(left) == sorted(right).
Mówienie że hash map zawsze ma O(1) bez doprecyzowania. Pesymistycznie O(n) przy złych kolizjach (HashDoS). Na rozmowie odpowiadaj „średnio O(1), pesymistycznie O(n)" — pokazuje świadomość pełnej charakterystyki.
Próba użycia listy jako klucza w dict. list jest mutable, więc niehashowalna — TypeError. Naprawa: konwertuj na tuple(values) przed użyciem jako klucz. Pamiętaj: tuple jest hashable tylko gdy wszystkie elementy są hashable.
FAQ
Czemu Python randomizuje hashe str i bytes?
Defensywa przed atakami HashDoS — atakujący znający algorytm hashowania mógłby spreparować requesty z kluczami kolidującymi do tego samego bucketu, redukując każdy lookup do O(n) i zatykając serwer. PEP 456 wprowadził SipHash z losowym ziarnem per proces, więc kolizje muszą być dobierane na żywo do konkretnej instancji.
Mogę zaimplementować własny __hash__? Co musi spełniać?
Tak. Trzy zasady: (1) jeśli a == b, to hash(a) == hash(b) (równość implikuje równy hash); (2) hash musi być stabilny w czasie życia obiektu; (3) używaj tylko pól użytych w __eq__. Najprostsza implementacja: return hash((self.field1, self.field2)) — zrzucasz tuple kluczowych pól do hash().
Co z dict, gdzie klucze to obiekty mutable wrappujące cache?
To czerwona flaga. Jeśli stan cache się zmienia, hash się zmienia, lookup nie znajdzie obiektu nawet jeśli to ten sam reference. Naprawa: rozdziel klucz (immutable identifier) od wartości (mutable cache). Albo użyj id(obj) jako klucza — wtedy klucz zachowuje stabilność, ale tracisz value equality.
Czemu set nie zachowuje insertion order, a dict tak?
To decyzja projektowa. dict order został zagwarantowany w Pythonie 3.7 jako konsekwencja optymalizacji pamięciowej w 3.6 (compact dict layout). set używa innej implementacji, gdzie kolejność iteracji jest pochodną hashy, więc randomizacja hashy str/bytes (PEP 456) zmienia ją między procesami. Do deterministycznej kolejności użyj sorted(set_var) albo dict.fromkeys(items).
Hash flooding attack — jak mocno to realne ryzyko?
Realne dla aplikacji parsujących user input do dict (web requesty z form-encoded body, JSON, GET params). Atak prosty: wysłać 10⁵ kluczy mających ten sam hash, każdy lookup staje się O(n), server haszowo busy. Po PEP 456 (Python 3.3+) ryzyko jest zminimalizowane przez randomizację, ale dobre frameworki (Django, FastAPI) i tak limitują liczbę pól per request.
Czy Counter jest szybszy niż ręczny dict z get?
Marginalnie, w zależności od inputu. Counter(iterable) jest zoptymalizowane na C-level w CPython, więc dla dużych kolekcji bywa 2-3× szybsze niż pętla z counts[key] = counts.get(key, 0) + 1. Dla małych kolekcji różnica jest niezauważalna. Główna wartość Counter to czytelność i most_common(K) w jednej linii — nie surowa wydajność.
Powiązane tematy
- Big O w 10 minut — Notacja Złożoności — kontekst dla
O(1) averageiO(n) worst case; tam są inne klasy złożoności i sygnały rozpoznawcze. - Drzewa Binarne — Wzorzec Rekurencyjny — alternatywa dla hash mapy gdy potrzebujesz porządku i range query; BST trzyma niezmiennik
lewy < root < prawy. - Wyszukiwanie Binarne —
bisectna sorted array jako trzecia opcja dla lookup;O(log n)po jednorazowym koszcie sortowania.
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący Two Sum, anagram, frequency count, hashable, hash collision i wybór struktury: https://odpytywarka.pl/q/Zp2wBx.
Masz własne notatki na rozmowę? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.
Źródła
- Python docs —
setidict— oficjalna dokumentacja struktur haszujących. - Python docs —
collections.Counter— frequency count i top-K elementów. - PEP 456 — Secure and interchangeable hash algorithm — SipHash i hash randomization w CPythonie.
- Wikipedia — Hash table — open addressing, kolizje, średnie i najgorsze przypadki.