Hashtabelle
Kurz gesagt: Eine Hashtabelle (dict in Python) findet einen Schlüssel über seinen Hash: Der Hash sagt, an welcher Stelle der Tabelle man nachsieht, darum sind Suchen und Einfügen im Durchschnitt O(1).
Problem
Der Preis-Cache wird langsam
Die Produktseite liest den Preis aus einem Cache: einer Tabelle SKU → Preis, die das Programm im Speicher hält. Jemand hat eine eigene PriceTable geschrieben, mit einer Hashfunktion, die „schnell“ sein soll: nur der erste Buchstabe der SKU.
cache = PriceTable(lambda key: ord(key[0]))Mit 20 Produkten im Test fliegt alles. Mit dem echten Katalog kriecht die Seite, und der Profiler zeigt auf get. Bei 1000 Produkten, jedes einmal geschrieben und einmal gelesen, macht die Tabelle 1.000.000 Schlüsselvergleiche: tausend pro Produkt. Eine Hashtabelle sollte einen oder zwei machen.
Jede SKU beginnt mit „S“. Was passiert da drinnen?
Die Idee
Buckets, Hash und Bucket-Nummer
In der Lektion „Hashcodes und Hashfunktionen“ hast du die Tabelle von außen gesehen. Von innen besteht sie aus drei Dingen:
- einem Array von Buckets;
- einer Hashfunktion, die den Schlüssel in eine ganze Zahl verwandelt;
- der Bucket-Nummer = Hash % Anzahl der Buckets. So hat jeder Schlüssel genau einen Platz, an dem du ihn suchst.
Zwei Schlüssel mit derselben Bucket-Nummer sind eine Kollision. Hier leben Kollisionen in einer Kette: Jeder Bucket ist der Anfang einer verketteten Liste aus Schlüssel-Wert-Paaren.
keys = [1007, 2043, 3010, 4051]buckets = 8for key in keys: h = hash(key) index = h % buckets print(f"{key} -> {h} -> Bucket {index}")Schritt für Schritt, in Worten
- Vier Schlüssel (Bestellnummern) und acht leere Buckets, nummeriert von 0 bis 7.
- hash(1007) ist die Zahl selbst, 1007. Der Rest bei der Division durch 8 ist 7: Das ist der Bucket.
- 2043 ergibt Bucket 3.
- 3010 ergibt Bucket 2.
- 4051 landet auch in Bucket 3: eine Kollision. Hier ist sie als Kette gezeichnet, wie in Java. Ein dict in CPython sucht stattdessen einen anderen freien Platz.
- Suche nach 4051: dieselbe Zahl, derselbe Bucket 3. == mit 2043: nein. Mit 4051: ja.
get berechnet den Bucket und läuft nur seine Kette entlang. Sind die Ketten kurz, ist das O(1), egal wie viele Schlüssel es gibt.
Sieh es dir an
Deine eigene Tabelle
Die Hashfunktion für eine SKU ist dieselbe wie das hashCode eines Strings in Java: 31 · h + char für jedes Zeichen. Am Ende wird das Vorzeichen abgeschnitten, damit die Zahl nicht negativ ist:
def sku_hash(key): h = 0 for c in key: h = (31 * h + ord(c)) & 0xFFFFFFFF return h & 0x7FFFFFFF& 0xFFFFFFFF sie bei jedem Schritt in 32 Bit, so wie der Überlauf in Java. So ist der Hash derselbe wie in den anderen Sprachen.Ein Paar ist ein Knoten mit einem Schlüssel, einem Preis und einem Pfeil auf den nächsten in der Kette:
class Entry: def __init__(self, key, price, next_entry): self.key = key self.price = price self.next = next_entryDie Tabelle bekommt ihre Hashfunktion von außen, damit du zwei davon vergleichen kannst. compares zählt die Schlüsselvergleiche:
class PriceTable: def __init__(self, hash_fn): self.hash = hash_fn self.buckets = [None] * 4 self.size = 0 self.compares = 0
def index(self, key): return self.hash(key) % len(self.buckets)
def put(self, key, price): i = self.index(key) e = self.buckets[i] while e is not None: self.compares += 1 if e.key == key: e.price = price return e = e.next self.buckets[i] = Entry(key, price, self.buckets[i]) self.size += 1 if self.size > len(self.buckets) * 3 // 4: self.resize()
def resize(self): fresh = [None] * (len(self.buckets) * 2) for head in self.buckets: e = head while e is not None: i = self.hash(e.key) % len(fresh) fresh[i] = Entry(e.key, e.price, fresh[i]) e = e.next self.buckets = fresh
def get(self, key): e = self.buckets[self.index(key)] while e is not None: self.compares += 1 if e.key == key: return e.price e = e.next return Noneputläuft die Kette des Buckets entlang. Ist der Schlüssel dort, ändert es den Preis. Wenn nicht, setzt es ein neues Paar an den Anfang der Kette: Dafür braucht es keinen Durchlauf.getläuft dieselbe Kette entlang und hält am Schlüssel an.
Probier es aus
Ergänze
Die Bucket-Nummer:
return self.hash(key) % Du teilst durch die Anzahl der Buckets. Der Rest liegt zwischen 0 und Anzahl der Buckets − 1, genau die Indizes des Arrays.
Die Idee
Ladefaktor und Wachsen
Je mehr Paare, desto länger die Ketten. Das Verhältnis Paare / Buckets heißt Ladefaktor. Hier macht die Tabelle doppelt so viele Buckets, sobald er über 3/4 steigt.
Die Buckets werden nicht eins zu eins kopiert. Die Bucket-Nummer ist Hash % Anzahl der Buckets, und diese Anzahl hat sich geändert. Darum läuft resize über jedes Paar und berechnet seinen Bucket neu: Das ist Rehashing. Beim Verdoppeln von 4 auf 8 geht ein Schlüssel aus Bucket b nach b oder nach b + 4, und die Ketten teilen sich.
def index(self, key): return self.hash(key) % len(self.buckets)
def put(self, key, price): i = self.index(key) e = self.buckets[i] while e is not None: self.compares += 1 if e.key == key: e.price = price return e = e.next self.buckets[i] = Entry(key, price, self.buckets[i]) self.size += 1 if self.size > len(self.buckets) * 3 // 4: self.resize()
def resize(self): fresh = [None] * (len(self.buckets) * 2) for head in self.buckets: e = head while e is not None: i = self.hash(e.key) % len(fresh) fresh[i] = Entry(e.key, e.price, fresh[i]) e = e.next self.buckets = freshSchritt für Schritt, in Worten
- Ein Preis-Cache mit 4 Buckets. Der Bucket eines Schlüssels ist sein Hash % 4.
- SKU-1003: 1091696434 % 4 = 2. SKU-1001: % 4 = 0. Leere Buckets: keine Vergleiche.
- SKU-1007 landet ebenfalls in Bucket 2: eine Kollision. put vergleicht ihn mit SKU-1003 (nicht derselbe Schlüssel) und setzt ihn an den Anfang der Kette.
- SKU-1005 kommt zu SKU-1001 in Bucket 0. Jetzt sind es 4 Paare, mehr als 3/4 von 4 Buckets: Die Ketten werden länger.
- resize macht 8 Buckets. Jeder Schlüssel wird mit % 8 neu berechnet: Er bleibt bei seiner Nummer oder wandert um 4 nach oben.
- Die neue Tabelle: Jede Kette hat ein Paar, darum macht ein get einen Vergleich. Das Vergrößern kostet n, kommt aber selten vor.
cache = PriceTable(sku_hash)cache.put("SKU-1003", 24.9)cache.put("SKU-1001", 12.5)cache.put("SKU-1007", 8.99)cache.print_buckets()print("---")cache.put("SKU-1005", 45.5)cache.print_buckets()0: SKU-10011:2: SKU-1007 SKU-10033:---0: SKU-10011:2: SKU-10033:4: SKU-10055:6: SKU-10077:Das Wachsen kostet so viel wie die Anzahl der Paare. Es passiert aber selten: bei 4, 8, 16… Paaren, wie das Wachsen des Arrays in Amortisierte Komplexität. Im Durchschnitt bleibt put O(1).
Probier es aus
Wie viele Buckets?
Die Tabelle beginnt mit 4 Buckets. Sieben Produkte kommen nacheinander hinein:
cache = PriceTable(sku_hash)caps = []for n in range(2001, 2008): cache.put(f"SKU-{n}", 10) caps.append(len(cache.buckets))print(" ".join(str(c) for c in caps))Die Grenze liegt bei 3/4 der Buckets. Bei 4 Buckets sind das 3: Das vierte Produkt geht darüber, und es werden 8 Buckets. Bei 8 liegt die Grenze bei 6: Das siebte geht darüber, und es werden 16.
Die Idee
Ein schlechter Hash: Die Tabelle wird zur Liste
Zurück zum Cache. Der Hash „erster Buchstabe“ ergibt für jede SKU 83 (der Code von „S“). 83 % 4, 83 % 8, 83 % 1024: Bei jeder Anzahl von Buckets ist die Nummer dieselbe. Alle Paare liegen in einer Kette, und die Tabelle ist eine verkettete Liste, in der jedes put und jedes get alle durchläuft.
Wachsen hilft nicht: Es teilt Ketten nur, wenn die Schlüssel verschiedene Hashes haben. Eine Hashfunktion muss vom ganzen Schlüssel abhängen und nahe Schlüssel (SKU-10000, SKU-10001) weit auseinander streuen.
def compares(cache, n): for i in range(n): cache.put(f"SKU-{10000 + i}", 1 + i) for i in range(n): cache.get(f"SKU-{10000 + i}") return cache.comparesprint(f"erster Buchstabe: {compares(PriceTable(lambda key: ord(key[0])), 1000)}")print(f"ganze SKU: {compares(PriceTable(sku_hash), 1000)}")erster Buchstabe: 1000000ganze SKU: 2593Lass beide Tabellen im Browser laufen:
- Hash der ganzen Artikelnummer
O(n) - Hash des ersten Buchstabens
O(n²)
| Algorithmus | n = 10 | n = 1.000 | n = 100.000 |
|---|---|---|---|
| Hash der ganzen Artikelnummer | 10 | 2.593 | 211.990 |
| Hash des ersten Buchstabens | 100 | 1.000.000 | ≈ 10.000.000.000 |
Bei 1000 Produkten macht der faule Hash 1.000.000 Vergleiche, und der Hash der ganzen SKU macht 2593: unter drei pro Produkt. Der faule ist O(n) pro Operation und O(n²) insgesamt: n Produkte, jedes einmal geschrieben und einmal gelesen, machen genau n² Vergleiche.
Genauer, für Neugierige
Offene Adressierung (Linear Probing). Statt Ketten liegt jedes Paar im Array selbst. Ist der Platz Hash % n belegt, probierst du den nächsten, dann den übernächsten, bis du einen freien Platz oder den Schlüssel findest. get folgt demselben Weg und hält an einem leeren Platz an. Der Vorteil: Alles liegt in einem Array, und der Prozessor liest es der Reihe nach. Die Nachteile: Belegte Plätze sammeln sich zu Haufen, und jeder Haufen wächst immer schneller, darum muss die Tabelle leerer bleiben (sie wächst schon bei etwa der Hälfte oder bei 2/3). Beim Löschen darf man den Platz nicht einfach leeren, denn das würde den Weg zu den Schlüsseln danach abschneiden: Es bleibt eine Markierung „gelöscht“.
Was die Sprachen tun:
- Java
HashMap: Ketten. Die Anzahl der Buckets ist eine Zweierpotenz (zuerst 16), der Ladefaktor ist 0,75. In den Hash werden die hohen Bits gemischt (h ^ (h >>> 16)), denn bei einer Maske mit Zweierpotenz würden sonst nur die niedrigen Bits zählen. Eine Kette mit mehr als 8 Paaren wird zu einem Rot-Schwarz-Baum, wenn es mindestens 64 Buckets gibt (sonst wächst zuerst die Tabelle). So ist die Suche auch bei vielen Kollisionen O(log n) und nicht O(n). - C#
Dictionary<TKey, TValue>: ebenfalls Ketten, aber in Arrays:_bucketshält die Nummer des ersten Paares, und die Paare in_entrieshaben einennext-Index. Die Anzahl der Buckets ist eine Primzahl (3, 7, 17, 37, 89…), und die Tabelle wächst, wenn das Array der Paare voll ist. Einen Baum wie in Java gibt es nicht. Gegen absichtliche Kollisionen hilft, dass sich Hashes von Text bei jedem Start unterscheiden. - Python
dict: offene Adressierung, aber nicht mit Linear Probing: Der nächste Platz wird nach einer Formel berechnet, in die auch die hohen Bits des Hashes eingehen. Die Tabelle ist eine Zweierpotenz und wächst, sobald sie zu mehr als 2/3 voll ist. Die Paare liegen in einem eigenen dichten Array in der Reihenfolge des Einfügens, und die Tabelle hält nur Indizes darauf. Darum merkt sichdictdie Reihenfolge des Einfügens (garantiert seit Python 3.7). - JavaScript
Map: Die Spezifikation verlangt Iteration in der Reihenfolge des Einfügens und Suchen, die im Durchschnitt besser als linear sind, sagt aber nicht, wie. V8 nutzt eine geordnete Hashtabelle: Buckets mit Ketten, und die Paare liegen in einem Array in der Reihenfolge des Einfügens. Einen eigenen Hash für Objekte gibt JavaScript nicht her: Ein Objekt als Schlüssel wird per Referenz verglichen.
Probier es aus
Finde den Fehler
Jemand hat resize umgeschrieben. Die vier Produkte kommen hinein, aber zwei davon sind später „weg“:
def resize(self): fresh = [None] * (len(self.buckets) * 2) for head in self.buckets: e = head while e is not None: i = self.hash(e.key) % len(self.buckets) fresh[i] = Entry(e.key, e.price, fresh[i]) e = e.next self.buckets = freshcache = PriceTable(sku_hash)cache.put("SKU-1003", 24.9)cache.put("SKU-1001", 12.5)cache.put("SKU-1007", 8.99)cache.put("SKU-1005", 45.5)p = cache.get("SKU-1003")print(f"SKU-1003: {'keiner' if p is None else p}")p = cache.get("SKU-1001")print(f"SKU-1001: {'keiner' if p is None else p}")p = cache.get("SKU-1007")print(f"SKU-1007: {'keiner' if p is None else p}")p = cache.get("SKU-1005")print(f"SKU-1005: {'keiner' if p is None else p}")SKU-1003: 24.9SKU-1001: 12.5SKU-1007: keinerSKU-1005: keinerIn welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Der Bucket wird mit der alten Anzahl von Buckets (4) berechnet, und get sucht später mit der neuen (8). Ein Schlüssel mit Hash % 8 = 4 liegt in Bucket 0, wird aber in Bucket 4 gesucht, und der ist leer. Der neue Bucket muss mit der Länge des neuen Arrays berechnet werden: % len(fresh).
Übung
Ein Produkt wird nicht mehr verkauft
Löse diese Aufgabe in deinem eigenen Editor.
Löschen aus dem Cache. Füge der PriceTable eine Methode remove(key) hinzu, die das Paar entfernt und zurückgibt, ob es eines gab. Achtung: Das Paar kann das erste in der Kette sein (dann zeigt der Bucket auf das nächste) oder in der Mitte (dann zeigt das vorherige Paar auf das nächste). Lege SKU-1001, SKU-1005, SKU-1009 und SKU-1012 mit den Preisen 10,5, 11,5, 12,5 und 13,5 € an; nach dem Wachsen auf 8 Buckets liegen drei davon in Bucket 0, und SKU-1009 liegt mitten in der Kette. Entferne SKU-1009 und lies alle vier:
SKU-1001: 10.5SKU-1005: 11.5SKU-1009: keinerSKU-1012: 13.5Produkte: 3Weitere Aufgaben
- Linear Probing. Schreibe eine
ProbeTableohne Ketten: Ist ein Platz belegt, probiere den nächsten. Wachse, wenn die Tabelle halb voll ist. Wie viele Vergleiche macht sie bei 1000 SKUs? - Schrumpfen. Nach einem Ausverkauf bleiben dem Cache 10 Produkte und 4096 Buckets. Wann würdest du die Tabelle verkleinern?
- Ein besserer fauler Hash. Der Hash „Summe der Zeichencodes“ sieht den ganzen Schlüssel an. Probiere ihn mit SKU-10000 bis SKU-10999. Warum gibt es trotzdem viele Kollisionen? (Hinweis: SKU-10019 und SKU-10091.)
Test