Wewnętrzne działanie funkcji haszującej i obsługa kolizji
Zrozumieją Państwo, jak Python haszuje obiekty, jak adresowanie otwarte i łańcuchowanie rozwiązują kolizje oraz dlaczego średnia złożoność O(1) może spaść do O(n).
Wewnętrzne działanie funkcji haszującej i obsługa kolizji to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Czym jest mapa haszująca?
Mapa haszująca (słownik w Pythonie) mapuje klucze na wartości za pomocą funkcji skrótu, która przekształca dowolny klucz w całkowity indeks bazowej tablicy. Idealna funkcja skrótu równomiernie rozkłada klucze w tablicy, umożliwiając wyszukiwanie, wstawianie i usuwanie ze średnią złożonością O(1). Bazowa tablica nazywa się tablicą haszującą lub tablicą kubełków.
W Pythonie dict to wysoce zoptymalizowana mapa haszująca. Zrozumienie jej implementacji wewnętrznej pomaga analizować zachowanie w najgorszym przypadku i wybierać odpowiednie klucze.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Funkcje skrótu i metoda __hash__
Python wywołuje __hash__(key), aby obliczyć na podstawie klucza liczbę całkowitą, a następnie oblicza resztę z dzielenia tej liczby przez rozmiar tablicy, aby ustalić indeks kubełka. Typy wbudowane, takie jak int, str i tuple, mają szybkie, wbudowane implementacje funkcji skrótu. list i dict nie są haszowalne, ponieważ są mutowalne, a ich modyfikacja unieważniłaby zapisany skrót.
Dobra funkcja skrótu równomiernie rozkłada klucze, jest deterministyczna i szybko się oblicza. Python losowo ustala wartości skrótów napisów między uruchomieniami (jest to funkcja bezpieczeństwa) — aby wyłączyć to zachowanie na potrzeby powtarzalnych testów, należy użyć PYTHONHASHSEED=0.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Kolizje: gdy dwa klucze trafiają do tego samego kubełka
Kolizja występuje, gdy dwa różne klucze dają ten sam indeks kubełka. Kolizje są nieuniknione (zasada szufladkowa: nieskończenie wiele kluczy i skończona liczba kubełków). Dwie standardowe strategie rozwiązywania kolizji to łańcuchowanie i adresowanie otwarte. Python używa wariantu adresowania otwartego z pseudolosowym sondowaniem.
W przypadku łańcuchowania w każdym kubełku przechowuje się listę wiązaną (lub dynamiczną tablicę); wszystkie klucze kolidujące w tym kubełku tworzą łańcuch. W adresowaniu otwartym wyszukuje się kolejny pusty kubełek zgodnie z sekwencją sondowania.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NoneAdresowanie otwarte: sondowanie liniowe
W przypadku sondowania liniowego, gdy w indeksie i wystąpi kolizja, mapa sprawdza i+1, i+2, ... (z zawijaniem do początku), aż znajdzie pustą komórkę. Wyszukiwanie musi przebiegać według tej samej sekwencji, aby znaleźć klucz. Usuwanie wymaga użycia znacznika „tombstone” zamiast wyczyszczenia komórki, aby nie przerwać łańcucha sondowania.
Główną wadą jest klastrowanie: gdy utworzy się klaster zajętych komórek, kolejne wstawienia w tym obszarze go powiększają, pogarszając wydajność aż do O(n).
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Współczynnik wypełnienia i zmiana rozmiaru
Współczynnik wypełnienia to stosunek liczby przechowywanych wpisów do całkowitej pojemności: α = n/m. Wraz ze wzrostem α rośnie prawdopodobieństwo kolizji i pogarsza się wydajność. dict w Pythonie zmienia rozmiar (podwaja pojemność), gdy współczynnik wypełnienia przekroczy około 2/3. Zmiana rozmiaru powoduje ponowne haszowanie wszystkich istniejących wpisów w nowej, większej tablicy — jest to operacja O(n), która zachodzi rzadko, dzięki czemu zamortyzowany koszt wstawiania wynosi O(1).
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeŚrednie O(1) a najgorsze O(n)
Przy dobrej funkcji skrótu kolizje są rzadkie, a oczekiwana długość łańcucha jest stała niezależnie od n. Wyszukiwanie, wstawianie i usuwanie w średnim przypadku mają zatem złożoność O(1). Jednak najgorszy przypadek — na przykład celowo spreparowane dane wejściowe, które kierują wszystkie klucze do tego samego kubełka — powoduje pogorszenie wszystkich operacji do O(n). Losowe ziarno funkcji skrótu w Pythonie ogranicza skutki tego ataku, ale nie eliminuje teoretycznie najgorszego przypadku.
W analizie podczas rozmowy rekrutacyjnej należy powiedzieć: „O(1) średnio, O(n) w najgorszym przypadku z powodu kolizji”.
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pyPython: dict, defaultdict i Counter
Python udostępnia trzy warianty map haszujących, które warto znać. dict to mapa ogólnego przeznaczenia; odwołanie do nieistniejącego klucza powoduje zgłoszenie KeyError. defaultdict(factory) zwraca wartość domyślną przy odwołaniu do nieistniejącego klucza, co jest przydatne podczas zbierania elementów do list lub zliczania. Counter to wyspecjalizowana podklasa służąca do zliczania obiektów haszowalnych; obsługuje także operacje arytmetyczne między licznikami.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionMapa haszująca a zbiór haszujący
Zbiór haszujący przechowuje wyłącznie klucze (bez powiązanych wartości), zapewniając sprawdzanie obecności, wstawianie i usuwanie w O(1). Pythonowy set jest zbiorem haszującym. Zbioru należy użyć, gdy trzeba jedynie odpowiedzieć na pytanie „czy ten element istnieje?”, bez przechowywania powiązanych danych. Słownika należy użyć, gdy wartości (np. liczniki lub wyniki) trzeba powiązać z kluczami.
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Implementowanie mapy haszującej od podstaw (wersja rekrutacyjna)
Podczas rozmowy rekrutacyjnej czasami pojawia się zadanie zaimplementowania podstawowej mapy haszującej. Jej najważniejsze elementy to: tablica kubełków o stałym rozmiarze (należy użyć 16 lub 1024), lista par (key, value) w każdym kubełku do obsługi łańcuchowania, funkcja skrótu (należy użyć wbudowanej funkcji Pythona w postaci hash % capacity) oraz zmiana rozmiaru po przekroczeniu współczynnika wypełnienia równego 0.7. Samodzielne wspomnienie o zmianie rozmiaru i współczynniku wypełnienia pokazuje szeroką wiedzę.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedKiedy mapy haszujące zawodzą: niehaszowalne klucze
Tylko obiekty haszowalne mogą być kluczami słownika. W Pythonie obiekt jest haszowalny, jeśli ma metodę __hash__ i metodę __eq__, a jego wartość skrótu nie zmienia się w trakcie jego istnienia. Listy, zbiory i słowniki są mutowalne, a zatem nie są haszowalne. Krotki i frozensety są haszowalnymi alternatywami dla list i zbiorów, gdy mają służyć jako klucze.
Częsta pułapka na rozmowach rekrutacyjnych: grupowanie anagramów wymaga użycia posortowanej krotki (a nie posortowanej listy) jako klucza słownika.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Podsumowanie: złożoność map haszujących
Mapy haszujące zapewniają średnią złożoność O(1) wstawiania, usuwania i wyszukiwania — stanowią podstawę wielu optymalnych rozwiązań zadań rekrutacyjnych. Najważniejsze założenia to: dobra funkcja skrótu równomiernie rozkłada klucze, współczynnik wypełnienia pozostaje ograniczony (zmiana rozmiaru pomaga to utrzymać), a obiekty używane jako klucze są niezmienne i haszowalne. Gdy te założenia są spełnione, mapy haszujące zamieniają liniowe przeszukiwanie O(n) na wyszukiwanie w O(1), umożliwiając rozwiązania takie jak two-sum w O(n) zamiast O(n²).
Szybki test
Proszę sprawdzić swoją wiedzę na temat zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji omówiono: mapa haszująca mapuje klucze na indeksy kubełków za pomocą funkcji skrótu i zapewnia operacje o średniej złożoności O(1), kolizje rozwiązuje się przez łańcuchowanie (lista wiązana dla każdego kubełka) lub adresowanie otwarte (sondowanie w poszukiwaniu kolejnej pustej komórki) oraz kluczami słownika mogą być tylko niezmienne, haszowalne obiekty — gdy potrzebny jest klucz będący sekwencją, należy użyć krotek zamiast list. W dalszej części rozwiązują Państwo problem two-sum i jego liczne warianty rekrutacyjne.
Często zadawane pytania
Czy lekcja „Wewnętrzne działanie funkcji haszującej i obsługa kolizji” jest bezpłatna?
Tak — pełny tekst „Wewnętrzne działanie funkcji haszującej i obsługa kolizji” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Wewnętrzne działanie funkcji haszującej i obsługa kolizji”?
Zrozumieją Państwo, jak Python haszuje obiekty, jak adresowanie otwarte i łańcuchowanie rozwiązują kolizje oraz dlaczego średnia złożoność O(1) może spaść do O(n). Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Wewnętrzne działanie funkcji haszującej i obsługa kolizji”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Wewnętrzne działanie funkcji haszującej i obsługa kolizji
- Two-Sum i jego liczne warianty
- Zliczanie częstotliwości i grupowanie
- Najdłuższy spójny ciąg i pamięć podręczna LRU