Interna von Hash-Funktionen und Kollisionsbehandlung
Verstehen Sie, wie Python Objekte hasht, wie Open Addressing und Verkettung Kollisionen auflösen und warum O(1) im Durchschnitt auf O(n) anwachsen kann.
Interna von Hash-Funktionen und Kollisionsbehandlung ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was ist eine Hash-Map?
Eine Hash-Map (Dictionary in Python) ordnet Schlüssel mithilfe einer Hash-Funktion Werten zu. Diese Funktion wandelt jeden Schlüssel in einen ganzzahligen Index eines zugrunde liegenden Arrays um. Eine ideale Hash-Funktion verteilt die Schlüssel gleichmäßig über das Array und ermöglicht dadurch durchschnittliche Zugriffs-, Einfüge- und Löschoperationen mit O(1). Das zugrunde liegende Array wird Hashtabelle oder Bucket-Array genannt.
In Python ist dict eine hochoptimierte Hash-Map. Wenn Sie ihre Interna verstehen, können Sie das Verhalten im Worst Case besser einschätzen und geeignete Schlüssel auswählen.
# 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}Hash-Funktionen und die __hash__-Methode
Python ruft __hash__(key) auf, um aus dem Schlüssel eine Ganzzahl zu berechnen. Anschließend wird diese Ganzzahl modulo der Tabellengröße genommen, um den Bucket-Index zu bestimmen. Integrierte Typen wie int, str und tuple verfügen über schnelle integrierte Hash-Implementierungen. list und dict sind nicht hashbar, da sie veränderlich sind und eine Änderung ihren gespeicherten Hash-Wert ungültig machen würde.
Eine gute Hash-Funktion verteilt Schlüssel gleichmäßig, ist deterministisch und lässt sich schnell berechnen. Der String-Hash von Python wird über verschiedene Programmläufe hinweg randomisiert (eine Sicherheitsfunktion) – verwenden Sie PYTHONHASHSEED=0, um dies für reproduzierbare Tests zu deaktivieren.
# 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'Kollisionen: Wenn zwei Schlüssel auf denselben Bucket abgebildet werden
Eine Kollision tritt auf, wenn zwei verschiedene Schlüssel denselben Bucket-Index erzeugen. Kollisionen sind unvermeidlich (Schubfachprinzip: unendlich viele Schlüssel, aber endlich viele Buckets). Zwei gängige Strategien zur Auflösung sind Chaining und Open Addressing. Python verwendet eine Variante von Open Addressing mit pseudozufälligem Sondieren.
Beim Chaining wird in jedem Bucket eine verkettete Liste (oder ein dynamisches Array) gespeichert; alle Schlüssel, die auf diesen Bucket abgebildet werden, bilden eine Kette. Open Addressing sucht entsprechend einer Sondierungsfolge nach dem nächsten freien 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 Addressing: Lineares Sondieren
Beim linearen Sondieren prüft die Map bei einer Kollision an Index i die Positionen i+1, i+2, ... (mit Umlauf zum Anfang), bis ein freier Slot gefunden wird. Bei der Suche muss dieselbe Folge sondiert werden, um den Schlüssel zu finden. Zum Löschen ist eine „Tombstone“-Markierung erforderlich, statt den Slot zu leeren, damit die Sondierungskette nicht unterbrochen wird.
Die größte Schwachstelle ist die Clusterbildung: Sobald sich ein Cluster belegter Slots bildet, erweitern künftige Einfügungen in diesem Bereich den Cluster, wodurch die Leistung gegen O(n) sinkt.
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')) # 10Load Factor und Resizing
Der Load Factor ist das Verhältnis der gespeicherten Einträge zur Gesamtkapazität: α = n/m. Mit steigendem α nimmt die Kollisionswahrscheinlichkeit zu und die Leistung ab. Das dict von Python führt ein Resizing durch (die Kapazität wird verdoppelt), wenn der Load Factor etwa 2/3 überschreitet. Beim Resizing werden alle vorhandenen Einträge in die neue, größere Tabelle rehashed – eine O(n)-Operation, die nur selten erfolgt und dadurch die amortisierten Kosten einer Einfügung bei O(1) hält.
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_sizeDurchschnittliches O(1) gegenüber Worst-Case-O(n)
Bei einer guten Hash-Funktion sind Kollisionen selten, und die erwartete Kettenlänge bleibt unabhängig von n konstant. Suchen, Einfügen und Löschen haben im Durchschnitt daher O(1). Ein Worst-Case-Szenario – beispielsweise eine absichtlich manipulierte Eingabe, die alle Schlüssel demselben Bucket zuordnet – verschlechtert jedoch alle Operationen auf O(n). Der randomisierte Hash-Seed von Python wirkt diesem Angriff entgegen, beseitigt den theoretischen Worst Case aber nicht.
In einer Interviewanalyse sollten Sie sagen: „Durchschnittlich O(1), im Worst Case aufgrund von Kollisionen O(n).“
# 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 gegenüber defaultdict und Counter
Python bietet drei wissenswerte Varianten von Hash-Maps. dict ist die allgemeine Map; beim Zugriff auf einen fehlenden Schlüssel wird KeyError ausgelöst. defaultdict(factory) gibt beim Zugriff auf einen fehlenden Schlüssel einen Standardwert zurück (nützlich zum Sammeln von Listen oder zum Zählen). Counter ist eine spezialisierte Unterklasse zum Zählen hashbarer Objekte und unterstützt außerdem Rechenoperationen zwischen Countern.
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 gegenüber Hash-Set
Ein Hash-Set speichert nur Schlüssel, keine zugehörigen Werte, und unterstützt das Testen auf Mitgliedschaft, Einfügen und Löschen mit O(1). Pythons set ist ein Hash-Set. Verwenden Sie ein Set, wenn Sie nur die Frage „Ist dieses Element vorhanden?“ beantworten müssen, ohne zugehörige Daten zu speichern. Verwenden Sie ein dict, wenn Sie Werten (z. B. Zählungen oder Ergebnissen) Schlüssel zuordnen müssen.
# 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}Eine Hash-Map von Grund auf implementieren (Interviewversion)
Interviewer bitten Sie manchmal, eine einfache Hash-Map zu implementieren. Die wichtigsten Bestandteile sind: ein Array fester Größe mit Buckets (verwenden Sie 16 oder 1024), eine Liste aus (key, value)-Paaren in jedem Bucket für Chaining, eine Hash-Funktion (verwenden Sie Pythons integriertes hash % capacity) sowie ein Resizing, sobald der Load Factor 0.7 überschreitet. Wenn Sie Resizing und Load Factor von sich aus erwähnen, zeigen Sie ein vertieftes Verständnis.
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 resizedWenn Hash-Maps scheitern: Nicht hashbare Schlüssel
Nur hashbare Objekte können als Dictionary-Schlüssel verwendet werden. In Python ist ein Objekt hashbar, wenn es über eine __hash__-Methode und eine __eq__-Methode verfügt und sich sein Hash-Wert während seiner Lebensdauer nicht ändert. Listen, Sets und dicts sind veränderlich und daher nicht hashbar. Tuples und frozensets sind hashbare Alternativen zu Listen und Sets, wenn sie als Schlüssel verwendet werden.
Eine häufige Interviewfalle: Zum Gruppieren von Anagrammen müssen Sie ein sortiertes Tuple (keine sortierte Liste) als dict-Schlüssel verwenden.
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']]Zusammenfassung: Komplexität von Hash-Maps
Hash-Maps bieten durchschnittlich O(1) für Einfügen, Löschen und Suchen – die Grundlage vieler optimaler Interviewlösungen. Die entscheidenden Annahmen sind: Eine gute Hash-Funktion verteilt Schlüssel gleichmäßig, der Load Factor bleibt begrenzt (Resizing stellt dies sicher), und Schlüsselobjekte sind unveränderlich und hashbar. Wenn diese Annahmen erfüllt sind, wandeln Hash-Maps lineare Durchläufe mit O(n) in Zugriffe mit O(1) um und ermöglichen Lösungen wie Two-Sum in O(n) statt O(n²).
Kurztest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Eine Hash-Map ordnet Schlüssel mithilfe einer Hash-Funktion Bucket-Indizes zu und erzielt durchschnittlich Operationen mit O(1), Kollisionen werden durch Chaining (eine verkettete Liste pro Bucket) oder Open Addressing (Sondieren nach dem nächsten freien Slot) aufgelöst und nur unveränderliche, hashbare Objekte können Dictionary-Schlüssel sein – verwenden Sie Tuples statt Listen, wenn ein Schlüssel aus einer Sequenz benötigt wird. Als Nächstes lösen wir Two-Sum und seine zahlreichen Interviewvarianten.
Häufig gestellte Fragen
Ist die Lektion „Interna von Hash-Funktionen und Kollisionsbehandlung“ kostenlos?
Ja — der vollständige Text von „Interna von Hash-Funktionen und Kollisionsbehandlung“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Interna von Hash-Funktionen und Kollisionsbehandlung“?
Verstehen Sie, wie Python Objekte hasht, wie Open Addressing und Verkettung Kollisionen auflösen und warum O(1) im Durchschnitt auf O(n) anwachsen kann. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Interna von Hash-Funktionen und Kollisionsbehandlung“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Interna von Hash-Funktionen und Kollisionsbehandlung
- Two-Sum und seine vielen Varianten
- Häufigkeiten zählen und gruppieren
- Längste aufeinanderfolgende Sequenz und LRU-Cache