Hashfunktioners interna delar och kollisionshantering
Förstå hur Python hashar objekt, hur open addressing och chaining löser kollisioner och varför O(1) i genomsnitt kan försämras till O(n).
Hashfunktioners interna delar och kollisionshantering är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad är en hash map?
En hash map (ordbok i Python) mappar nycklar till värden med hjälp av en hashfunktion som omvandlar varje nyckel till ett heltalsindex i en underliggande array. En ideal hashfunktion fördelar nycklar jämnt över arrayen, vilket möjliggör uppslagning, insättning och borttagning i O(1) i genomsnitt. Den underliggande arrayen kallas hash-tabell eller bucket-array.
I Python är dict en starkt optimerad hash map. Genom att förstå hur den fungerar internt kan ni resonera om beteendet i värsta fall och välja lämpliga nycklar.
# 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}Hashfunktioner och metoden __hash__
Python anropar __hash__(key) för att beräkna ett heltal från nyckeln och tar sedan heltalet modulo tabellstorleken för att hitta bucketens index. Inbyggda typer som int, str och tuple har snabba inbyggda hashimplementationer. list och dict är inte hashbara (de är muterbara, och om de ändras skulle lagrade hashvärden bli ogiltiga).
En bra hashfunktion fördelar nycklar jämnt, är deterministisk och är snabb att beräkna. Pythons hashning av strängar randomiseras mellan körningar (en säkerhetsfunktion) — använd PYTHONHASHSEED=0 för att stänga av detta och få reproducerbara tester.
# 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'Kollisioner: När två nycklar ger samma bucket-index
En kollision uppstår när två olika nycklar ger samma bucket-index. Kollisioner är oundvikliga (duvslagsprincipen: oändligt många nycklar, men ändligt många buckets). Två standardstrategier för att lösa detta är chaining och open addressing. Python använder en variant av open addressing med pseudorandomiserad probering.
Chaining lagrar en länkad lista (eller dynamisk array) i varje bucket; alla nycklar som kolliderar i den bucketen bildar en kedja. Open addressing letar efter nästa tomma bucket enligt en probsekvens.
# 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')) # NoneOpen addressing: Linjär probing
Vid linjär probing kontrollerar hash map:en i+1, i+2, ... (med omslag till början) när en kollision uppstår vid index i, tills en tom plats hittas. Vid uppslagning måste samma sekvens genomsökas för att hitta nyckeln. Borttagningar kräver en markör av typen ”tombstone” i stället för att platsen töms, så att probkedjan inte bryts.
Klustring är den främsta nackdelen: när ett kluster av fyllda platser har bildats utökar framtida insättningar i det området klustret, vilket försämrar prestandan mot 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')) # 10Belastningsgrad och omdimensionering
Belastningsgraden är förhållandet mellan antalet lagrade poster och den totala kapaciteten: α = n/m. När α ökar blir kollisioner mer sannolika och prestandan försämras. Pythons dict ändrar storlek (fördubblar kapaciteten) när belastningsgraden överstiger ungefär 2/3. Omdimensionering innebär att alla befintliga poster hashas om i den nya, större tabellen — en O(n)-operation som sker sällan och därför håller den amortiserade kostnaden för insättning vid 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_sizeGenomsnittlig O(1) jämfört med O(n) i värsta fall
Med en bra hashfunktion är kollisioner sällsynta och den förväntade kedjelängden är konstant oavsett n. Uppslagning, insättning och borttagning har därför O(1) i genomsnitt. Ett värsta fall — till exempel illvilligt konstruerade indata som mappar alla nycklar till samma bucket — försämrar alla operationer till O(n). Pythons randomiserade hashfrö motverkar denna attack, men eliminerar inte det värsta fallet teoretiskt sett.
Säg i intervjuanalyser: ”O(1) i genomsnitt, O(n) i värsta fall på grund av kollisioner.”
# 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 jämfört med defaultdict och Counter
Python tillhandahåller tre hash map-varianter som är värda att känna till. dict är den allmänna hash map-typen; åtkomst till en saknad nyckel utlöser KeyError. defaultdict(factory) returnerar ett standardvärde vid åtkomst till en saknad nyckel (praktiskt när ni samlar listor eller räknar). Counter är en specialiserad subklass för att räkna hashbara objekt och stöder även aritmetiska operationer mellan räknare.
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 subtractionHash map jämfört med hash set
En hash set lagrar endast nycklar (inga tillhörande värden) och stöder medlemskapstest, insättning och borttagning i O(1). Pythons set är ett hash set. Använd ett set när ni bara behöver avgöra om ett element finns, utan att lagra tillhörande data. Använd en dict när ni behöver koppla värden (antal, resultat och så vidare) till nycklar.
# 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}Implementera en hash map från grunden (intervjuversion)
Ibland ber intervjuare er att implementera en grundläggande hash map. De viktigaste komponenterna är: en array med buckets av fast storlek (använd 16 eller 1024), där varje bucket är en lista med par av typen (key, value) för chaining, en hashfunktion (använd Pythons inbyggda hash % capacity) samt omdimensionering när belastningsgraden överstiger 0.7. Att självmant nämna omdimensionering och belastningsgrad visar djupa kunskaper.
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 resizedNär hash maps inte fungerar: icke-hashbara nycklar
Endast hashbara objekt kan användas som dictionary-nycklar. I Python är ett objekt hashbart om det har en __hash__-metod och en __eq__-metod, och om dess hashvärde inte ändras under objektets livstid. Listor, mängder och dict-objekt är muterbara och därför inte hashbara. Tuples och frozensets är hashbara alternativ till listor och mängder när de används som nycklar.
En vanlig intervjufälla: när ni grupperar anagram måste ni använda en sorterad tuple (inte en sorterad lista) som dict-nyckel.
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']]Sammanfattning: Hash map-komplexitet
Hash maps ger O(1) i genomsnitt för insättning, borttagning och uppslagning — grunden för många optimala intervjulösningar. De viktigaste antagandena är att en bra hashfunktion fördelar nycklar jämnt, att belastningsgraden hålls begränsad (vilket omdimensionering säkerställer) och att nyckelobjekten är oföränderliga och hashbara. När dessa antaganden gäller omvandlar hash maps linjära genomsökningar i O(n) till uppslagningar i O(1), vilket möjliggör lösningar som two-sum i O(n) i stället för O(n²).
Snabb kontroll
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen lärde ni er: en hash map mappar nycklar till bucket-index med hjälp av en hashfunktion och uppnår O(1) i genomsnitt för sina operationer, kollisioner löses med chaining (en länkad lista per bucket) eller open addressing (probering efter nästa tomma plats), och endast oföränderliga, hashbara objekt kan användas som dictionary-nycklar — använd tuples i stället för listor när ni behöver en sekvens som nyckel. Härnäst löser vi two-sum och dess många intervjuvarianter.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Hashfunktioners interna delar och kollisionshantering” gratis?
Ja – hela texten till ”Hashfunktioners interna delar och kollisionshantering” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Hashfunktioners interna delar och kollisionshantering”?
Förstå hur Python hashar objekt, hur open addressing och chaining löser kollisioner och varför O(1) i genomsnitt kan försämras till O(n). Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Hashfunktioners interna delar och kollisionshantering”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Hashfunktioners interna delar och kollisionshantering
- Two-sum och dess många varianter
- Frekvensräkning och gruppering
- Längsta följden av på varandra följande tal och LRU-cache