Internals van hashfuncties en botsingsafhandeling
Begrijp hoe Python objecten hasht, hoe open addressing en chaining botsingen oplossen en waarom O(1) in het gemiddelde geval kan verslechteren tot O(n).
Internals van hashfuncties en botsingsafhandeling is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat is een hashmap?
Een hashmap (woordenboek in Python) koppelt sleutels aan waarden met behulp van een hashfunctie die elke sleutel omzet in een gehele index in een onderliggende array. Een ideale hashfunctie verdeelt sleutels gelijkmatig over de array, waardoor zoeken, invoegen en verwijderen gemiddeld in O(1) kunnen gebeuren. De onderliggende array heet de hashtabel of bucketarray.
In Python is dict een sterk geoptimaliseerde hashmap. Als je de interne werking begrijpt, kun je beter redeneren over gedrag in het slechtste geval en geschikte sleutels kiezen.
# 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}Hashfuncties en de methode __hash__
Python roept __hash__(key) aan om een geheel getal uit de sleutel te berekenen en neemt daarna dat getal modulo de tabelgrootte om de bucketindex te vinden. Ingebouwde typen zoals int, str en tuple hebben snelle ingebouwde hashimplementaties. list en dict zijn niet hashbaar: ze zijn veranderlijk, en als je ze verandert, wordt elke opgeslagen hash ongeldig.
Een goede hashfunctie verdeelt sleutels gelijkmatig, is deterministisch en is snel te berekenen. De stringhash van Python wordt tussen uitvoeringen willekeurig gemaakt (een beveiligingsfunctie) — gebruik PYTHONHASHSEED=0 om dit uit te schakelen voor reproduceerbaarheid bij het testen.
# 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'Botsingen: wanneer twee sleutels naar dezelfde bucket hashen
Een botsing ontstaat wanneer twee verschillende sleutels dezelfde bucketindex opleveren. Botsingen zijn onvermijdelijk (het duivenhokprincipe: oneindig veel sleutels, maar eindig veel buckets). Twee standaardstrategieën om ze op te lossen zijn ketenvorming en open adressering. Python gebruikt een variant van open adressering met pseudowillekeurig peilen.
Bij ketenvorming wordt in elke bucket een gekoppelde lijst (of dynamische array) opgeslagen; alle sleutels die in die bucket botsen, vormen samen een keten. Bij open adressering wordt volgens een peilreeks gezocht naar de volgende lege bucket.
# 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 adressering: lineair peilen
Bij lineair peilen controleert de hashmap wanneer er op index i een botsing optreedt achtereenvolgens i+1, i+2, ... (met terugloop naar het begin) totdat er een lege plek is gevonden. Bij het zoeken moet dezelfde reeks worden doorlopen om de sleutel te vinden. Voor verwijderingen is een markering voor een verwijderd item nodig in plaats van de plek leeg te maken, zodat de peilketen niet wordt onderbroken.
Ophoping is het belangrijkste nadeel: zodra zich een groep gevulde plekken vormt, breiden toekomstige invoegingen in dat gebied de groep uit, waardoor de prestaties richting O(n) dalen.
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')) # 10Beladingsfactor en herschalen
De beladingsfactor is de verhouding tussen het aantal opgeslagen items en de totale capaciteit: α = n/m. Naarmate α toeneemt, stijgt de kans op botsingen en nemen de prestaties af. Python vergroot de capaciteit van dict (en verdubbelt die) wanneer de beladingsfactor ongeveer 2/3 overschrijdt. Bij het herschalen worden alle bestaande items opnieuw gehasht in de nieuwe, grotere tabel — een bewerking van O(n) die zelden plaatsvindt, waardoor de geamortiseerde kosten van invoegen O(1) blijven.
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_sizeGemiddelde O(1) tegenover O(n) in het slechtste geval
Met een goede hashfunctie zijn botsingen zeldzaam en blijft de verwachte ketenlengte constant, ongeacht n. Zo verlopen zoeken, invoegen en verwijderen gemiddeld in O(1). Een scenario in het slechtste geval — bijvoorbeeld opzettelijk samengestelde invoer die alle sleutels naar dezelfde bucket stuurt — maakt alle bewerkingen O(n). De willekeurige hashseed van Python beperkt deze aanval, maar neemt het theoretische slechtste geval niet weg.
Zeg bij een analyse tijdens een sollicitatiegesprek: "Gemiddeld O(1), in het slechtste geval O(n) door botsingen."
# 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 tegenover defaultdict tegenover Counter
Python biedt drie hashmapvarianten die je moet kennen. dict is de algemene hashmap; bij het opvragen van een ontbrekende sleutel wordt KeyError opgegooid. defaultdict(factory) geeft bij het opvragen van een ontbrekende sleutel een standaardwaarde terug (handig om lijsten te verzamelen of te tellen). Counter is een gespecialiseerde subklasse voor het tellen van hashbare objecten en ondersteunt ook rekenkundige bewerkingen tussen tellers.
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 subtractionHashmap tegenover hashset
Een hashset slaat alleen sleutels op (zonder bijbehorende waarden) en ondersteunt het controleren of een element aanwezig is, invoegen en verwijderen in O(1). Python's set is een hashset. Gebruik een set als je alleen hoeft te beantwoorden of een element bestaat, zonder bijbehorende gegevens op te slaan. Gebruik een dict als je waarden (tellingen, resultaten enzovoort) aan sleutels wilt koppelen.
# 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}Een hashmap vanaf nul implementeren (versie voor sollicitatiegesprekken)
Tijdens een sollicitatiegesprek kan je soms worden gevraagd om een eenvoudige hashmap te implementeren. De belangrijkste onderdelen zijn: een array met een vaste grootte en buckets (gebruik 16 of 1024), een lijst met paren (sleutel, waarde) in elke bucket voor ketenvorming, een hashfunctie (gebruik Python's ingebouwde hash % capacity) en herschalen wanneer de beladingsfactor groter wordt dan 0.7. Als je uit jezelf herschalen en de beladingsfactor noemt, toon je grondige kennis.
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 resizedWanneer hashmaps falen: niet-hashbare sleutels
Alleen hashbare objecten kunnen sleutels van een dictionary zijn. In Python is een object hashbaar als het een methode __hash__ en een methode __eq__ heeft en de hashwaarde tijdens zijn levensduur niet verandert. List-, set- en dict-objecten zijn veranderlijk en daarom niet hashbaar. Tuple- en frozenset-objecten zijn hashbare alternatieven voor lists en sets wanneer je ze als sleutels gebruikt.
Een veelgemaakte valkuil in sollicitatiegesprekken: voor het groeperen van anagrammen moet je een gesorteerde tuple gebruiken (geen gesorteerde list) als sleutel van de dict.
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']]Samenvatting: complexiteit van hashmaps
Hashmaps bieden gemiddeld O(1) voor invoegen, verwijderen en zoeken — de basis voor veel optimale oplossingen tijdens sollicitatiegesprekken. De belangrijkste aannames zijn: een goede hashfunctie verdeelt sleutels gelijkmatig, de beladingsfactor blijft begrensd (herschalen houdt dit zo) en sleutelobjecten zijn onveranderlijk en hashbaar. Als aan deze aannames wordt voldaan, zetten hashmaps lineaire doorzoekingen van O(n) om in zoekacties van O(1), waardoor oplossingen zoals Two-Sum in O(n) in plaats van O(n²) mogelijk worden.
Korte controle
Toets je begrip van de concepten uit de les van Data Structures & Algorithms — Coding Interview Prep.
Samenvatting van de les
In deze les heb je geleerd dat een hashmap sleutels met behulp van een hashfunctie aan bucketindices koppelt en bewerkingen gemiddeld in O(1) uitvoert, dat botsingen worden opgelost door ketenvorming (gekoppelde lijst per bucket) of open adressering (zoeken naar de volgende lege plek) en dat alleen onveranderlijke, hashbare objecten dictionary-sleutels kunnen zijn — gebruik tuples in plaats van lists wanneer je een sequentiesleutel nodig hebt. Hierna lossen we Two-Sum en de vele varianten ervan op die in sollicitatiegesprekken voorkomen.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Internals van hashfuncties en botsingsafhandeling” gratis?
Ja — de volledige tekst van “Internals van hashfuncties en botsingsafhandeling” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Internals van hashfuncties en botsingsafhandeling”?
Begrijp hoe Python objecten hasht, hoe open addressing en chaining botsingen oplossen en waarom O(1) in het gemiddelde geval kan verslechteren tot O(n). Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Internals van hashfuncties en botsingsafhandeling”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Internals van hashfuncties en botsingsafhandeling
- Two-sum en de vele varianten
- Frequenties tellen en groeperen
- Langste opeenvolgende reeks en LRU-cache