Ob Sie einen Schlüssel in einem Python-dict mit zehn Einträgen suchen oder in einem mit zehn Millionen: Es dauert gleich lange. Das liegt nicht an einer besonders schnellen Sprache. Pythons dict, Javas HashMap und JavaScripts Map sind allesamt Hash-Tabellen, und das gesamte Design existiert, damit Suche, Einfügen und Löschen im Durchschnitt mit O(1) laufen. Die Big-O-Notation nennt diese Suche “konstante Zeit”. Hier ist der Mechanismus, der das verdient.

Wie eine Hash-Tabelle einen Schlüssel in einen Array-Index umwandelt

Eine Hash-Tabelle ist ein Array plus eine Funktion, die einen Schlüssel in eine Position in diesem Array umwandelt.

1

Bucket-Index = hash(Schlüssel) % Anzahl_der_Buckets

hash() nimmt einen Schlüssel beliebiger Größe (einen String, ein Tupel, ein Objekt) und gibt eine Ganzzahl zurück. Innerhalb eines Programmlaufs liefert derselbe Schlüssel immer dieselbe Ganzzahl, und eine gute Hashfunktion verteilt diese Zahlen fast gleichmäßig über ihren Ausgabebereich. Nehmen Sie die Ganzzahl modulo der Array-Länge, und Sie haben einen Slot. Dort speichern Sie Schlüssel und Wert. Eine spätere Suche berechnet denselben Hash erneut, landet auf demselben Slot und liest den Wert aus. Kein Scan, kein Vergleich mit jedem anderen Schlüssel.

Alles andere in einer echten Hash-Tabelle (Kollisionsbehandlung, Resizing, die genaue Sondierungsreihenfolge) dient dazu, diese Ein-Schritt-Suche funktionsfähig zu halten, während die Tabelle sich füllt.

Eine minimale Version, die Kollisionen ignoriert:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class TinyTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [None] * size

    def put(self, key, value):
        index = hash(key) % self.size
        self.buckets[index] = (key, value)

    def get(self, key):
        index = hash(key) % self.size
        if self.buckets[index] is None:
            raise KeyError(key)
        stored_key, value = self.buckets[index]
        if stored_key != key:
            raise KeyError(key)
        return value

1
2
3
4

>>> t = TinyTable()
>>> t.put("user:42", {"name": "Dana"})
>>> t.get("user:42")
{'name': 'Dana'}

Das bricht, sobald zwei verschiedene Schlüssel auf denselben Index hashen. hash("user:42") % 8 und hash("user:17") % 8 können beide 3 ergeben, und TinyTable hat nur Platz für einen davon: Der zweite put-Aufruf überschreibt den ersten stillschweigend. Das ist eine Kollision.

Wie Hash-Tabellen Kollisionen behandeln: Chaining vs. offene Adressierung

Es gibt zwei Standardwege, beide Schlüssel zu behalten, wenn sie im selben Slot landen.

Chaining macht aus jedem Bucket einen kleinen Container, meist eine verkettete Liste. Eine Kollision bedeutet, dass der Bucket zwei Einträge statt einen enthält, und die Suche läuft diese Liste durch, bis sie den passenden Schlüssel findet.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class ChainedTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def put(self, key, value):
        index = hash(key) % self.size
        bucket = self.buckets[index]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self.buckets[hash(key) % self.size]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

Javas HashMap ist eine Chaining-Tabelle. Jeder Bucket startet als verkettete Liste. Sammelt ein Bucket mindestens 8 Einträge und hat die Tabelle mindestens 64 Buckets, wandelt sich dieser Bucket in einen Rot-Schwarz-Baum um (TREEIFY_THRESHOLD und MIN_TREEIFY_CAPACITY im JDK-Quellcode), sodass ein O(n)-Scan im schlimmsten Fall eines überlasteten Buckets zu O(log n) wird. Er wird wieder zur Liste, wenn ein Resize ihn mit 6 oder weniger Einträgen zurücklässt.

Offene Adressierung behält jeden Eintrag direkt im Array, ohne Zusatzstruktur und ohne Zeiger. Bei einer Kollision sondiert sie: Sie probiert nach einer festen Regel einen anderen Slot, bis sie einen leeren findet. Das dict von CPython arbeitet so, und der Kommentar zur Suche in Objects/dictobject.c nennt den Grund: “Open addressing is preferred over chaining since the link overhead for chaining would be substantial.” CPython vermeidet auch reines lineares Sondieren, das stark klumpt, wenn Schlüssel in vorhersehbarer Reihenfolge eintreffen. Jeder Sondierungsschritt mischt mehr Bits des Hash in den nächsten Index, sodass zwei Schlüssel, die auf ihren niedrigen Bits kollidieren, sich nach ein paar Sondierungsschritten trennen.

Die beiden Strategien versagen unterschiedlich. Eine Chaining-Tabelle, die sich füllt, wird langsamer, und im schlimmsten Fall landet jeder Eintrag in einer einzigen langen Liste. Eine Tabelle mit offener Adressierung hat nirgendwo mehr Platz für einen Eintrag, wenn das Array voll ist, also muss sie sich vergrößern, bevor es dazu kommt.

Was der Load-Faktor ist und warum die Tabelle sich vergrößert, bevor sie voll ist

Der Load-Faktor ist die Anzahl der Einträge geteilt durch die Anzahl der Buckets. Beide Strategien beobachten ihn, um zu entscheiden, wann sie sich vergrößern, und Java und CPython wählen unterschiedliche Schwellenwerte.

Javas HashMap vergrößert sich, wenn die Anzahl der Einträge die Kapazität mal Load-Faktor überschreitet. Das Javadoc des parameterlosen Konstruktors nennt die Standardwerte: 16 Buckets, Load-Faktor 0,75, also löst der erste Resize beim 12. Eintrag aus. Ein Resize verdoppelt die Bucket-Anzahl ungefähr und hasht jeden vorhandenen Eintrag neu in das neue Array. Deshalb empfiehlt das Javadoc, die Map im Voraus mit HashMap.newHashMap(expectedSize) (Java 19+) zu dimensionieren, wenn Sie ungefähr wissen, wie viele Einträge sie halten wird: Sie sparen sich die wiederholten Rehashes.

CPythons dict vergrößert sich später und wächst schneller. Der USABLE_FRACTION-Kommentar im Quellcode besagt, dass die Tabelle sich vergrößert, sobald sie zu zwei Dritteln voll ist, und GROWTH_RATE dimensioniert die neue Tabelle auf etwa das Dreifache der aktuellen Zahl lebender Einträge, nicht auf eine einfache Verdopplung.

Keine der beiden Zahlen ist willkürlich. Ein Load-Faktor nahe 1 füllt das Array dicht, macht aber jede Operation langsamer, je voller die Buckets werden; ein Load-Faktor nahe 0 verschwendet Speicher auf Slots, die noch niemand nutzt. Beide Designs pendeln sich zwischen 0,66 und 0,75 ein, dort, wo zusätzlicher Speicher keine wesentlich kürzeren Sondierungen mehr erkauft.

Warum die Suche in einer Hash-Tabelle im Durchschnitt O(1) ist, nicht immer

Konstante Zeit gilt nur, solange Hashes die Schlüssel annähernd gleichmäßig über die Buckets verteilen. Zwei Dinge brechen das.

Eine schlechte oder vorhersehbare Hashfunktion. Wenn jeder eingefügte Schlüssel auf denselben Bucket hasht, degeneriert eine Chaining-Tabelle zu einer einzigen verketteten Liste mit O(n)-Suche — genau das, was die Struktur verhindern soll. Das passiert in der Produktion. Ein Server, der von Angreifern kontrollierte Eingaben (Formularfeldnamen, HTTP-Header, JSON-Schlüssel) mit einer vorhersehbaren Funktion hasht, ist anfällig für Angriffe über algorithmische Komplexität: Der Angreifer schickt Tausende Schlüssel, die absichtlich kollidieren, und erzwingt so bei jeder Anfrage das Worst-Case-Verhalten. Python randomisiert den Hash von str und bytes pro Prozess seit Version 3.3 (gesteuert über PYTHONHASHSEED) genau deshalb. Derselbe String hasht in zwei Interpreterläufen unterschiedlich, sodass niemand offline eine Kollisionsmenge vorausberechnen kann.

Einen Schlüssel nach dem Einfügen verändern. Der Bucket, in dem ein Schlüssel liegt, wurde anhand seines Hash gewählt, also geht die Tabelle davon aus, dass sich dieser Hash nie ändert. Python erzwingt das auf Typebene: Mutable Built-ins wie list und dict setzen __hash__ auf None, und einen davon als Schlüssel zu verwenden löst TypeError: unhashable type: 'list' aus, bevor der Fehler passieren kann. Tupel und Strings sind hashbar, weil sie unveränderlich sind. Für eine eigene Schlüsselklasse implementieren Sie __hash__ und __eq__ zusammen und stützen sie nur auf Felder, die sich nie ändern. Sonst “verschwindet” ein geänderter Schlüssel: Der Eintrag steckt noch in der Tabelle, in dem Bucket, auf den sein alter Hash zeigte, aber die Suche sucht woanders.

Wann Sie keine Hash-Tabelle verwenden sollten

Eine Hash-Tabelle beantwortet eine Frage schnell: Existiert dieser Schlüssel, und was ist sein Wert? Fast alles andere macht sie schlecht.

  • Bereichs- und Sortierabfragen. “Alle diesen Monat angelegten Benutzer” oder “der nächste Schlüssel nach diesem” brauchen eine sortierte Struktur. Eine Hash-Tabelle hat keine Ordnung. CPythons dict garantiert seit 3.7 die Einfügereihenfolge, aber das ist Iterationsreihenfolge, keine Sortierreihenfolge, und hilft nicht bei “alles zwischen X und Y”. Diese Abfrage erledigt ein B-Baum gut, weshalb die meisten Datenbanken standardmäßig B-Baum-Indizes statt Hash-Indizes verwenden. Wie Datenbankindizes funktionieren behandelt den Scan-vs-Seek-Kompromiss hinter diesem Standard.
  • Präfix- oder Fuzzy-Treffer. “Schlüssel, die mit user: beginnen” bedeutet, jeden Schlüssel zu prüfen. Ein Trie oder eine sortierte Struktur mit binärer Suche erledigt das direkt.
  • Kleine Integer-Schlüssel in engem Bereich. Ist der Schlüssel bereits ein Wochentag oder eine HTTP-Statusklasse, überspringen Sie die Hashfunktion und indizieren Sie direkt ein Array. Eine Schicht weniger, keine Kollisionen.

Ist eine Hash-Tabelle die richtige Struktur, schreiben Sie fast nie selbst eine. dict, HashMap, Map und std::unordered_map sind bereits optimiert und korrekt. Sie nutzen sie auch indirekt öfter, als Sie denken: Eine mit functools.lru_cache dekorierte Funktion, behandelt in Python-Decorators erklärt, baut aus den Argumenten des Aufrufs einen Schlüssel und sucht ihn in einem dict.

Die Entscheidung ist also kurz. Lautet die Operation “suche dies anhand des exakten Schlüssels”, nutzen Sie die eingebaute Hash-Tabelle und schreiben Sie keine eigene. Geht es um Reihenfolge, Bereiche oder Teiltreffer, wählen Sie von Anfang an eine sortierte Struktur oder einen Trie, denn keine Hashfunktion repariert eine Struktur, die die falsche Frage beantwortet.

Verwandte Artikel