Zwei verschiedene Schlüssel können in denselben Bucket gehasht werden — eine Kollision. Hash-Tabellen bleiben im Durchschnitt O(1), indem sie Kollisionen lösen und die Größe anpassen, bevor Buckets zu voll werden, gesteuert durch den Auslastungsfaktor.
Separate chaining: each bucket holds a list
[3] -> ("cat",9) -> ("rat",2) # both hashed to 3
Open addressing: probe to the next free slot
hash=3 taken -> try 4 -> try 5 ... (linear probing)
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
-> allocate a bigger array (usually 2x)
-> REHASH every existing key into new buckets
# Conceptual resize
def _resize(self):
old = self.buckets
self.buckets = [None] * (len(old) * 2)
for entry in all_entries(old):
self._insert(entry.key, entry.value) # rehash into new array
| Operation | Durchschnitt | Worst Case |
|---|---|---|
| Suche / Einfügen / Löschen | O(1) | O(n) |
| einzelne Größenanpassung | — | O(n) |
| Einfügen (amortisiert, mit Größenanpassung) | O(1) | — |
Eine Größenanpassung ist O(n), tritt aber selten auf, sodass sie sich zu O(1) pro Einfügung amortisiert.
Diese Implementierungsdetails erklären, warum Hash-Maps im Durchschnitt schnell sind, aber auf O(n) ansteigen können — entscheidend für leistungsempfindlichen Code und Abwehr gegen adversarielle Input-Attacken (Hash-Flooding).
Das Verständnis des Auslastungsfaktors erklärt auch die von echten Bibliotheken bereitgestellten Speicher-/Geschwindigkeits-Tuning-Knöpfe.