Hashtabelle

Code in:JavaC#PythonJavaScript

Kurz gesagt: Eine Hashtabelle (Map in JavaScript) speichert Schlüssel-Wert-Paare in Buckets: Der Hash des Schlüssels sagt, in welchem Bucket das Paar liegt, 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.

const cache = new PriceTable((key) => key.charCodeAt(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.

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}

const keys = ["Laura", "Jonas", "Tom", "Finn"];
const buckets = 8;
for (const key of keys) {
  const hash = hashOf(key);
  const index = ((hash % buckets) + buckets) % buckets;
  console.log(`${key} -> ${hash} -> Bucket ${index}`);
}

Schritt für Schritt, in Worten

1. Vier Schlüssel und acht leere Buckets, nummeriert von 0 bis 7.
2. hashOf("Laura") ist 73193391. Der Rest bei der Division durch 8 ist 7: Das ist der Bucket.
3. "Jonas" ergibt 71756187, Bucket 3.
4. "Tom" ergibt 84274, Bucket 2.
5. "Finn" landet auch in Bucket 3: eine Kollision. Die beiden Schlüssel sind in einem Bucket: "Finn" hängt wie in einer Kette hinter "Jonas".
6. Suche nach "Finn": dieselbe Zahl, derselbe Bucket 3. === mit "Jonas": nein. Mit "Finn": 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:

function skuHash(key) {
  let h = 0;
  for (let i = 0; i < key.length; i++) {
    h = (Math.imul(31, h) + key.charCodeAt(i)) | 0;
  }
  return h & 0x7fffffff;
}

Math.imul multipliziert wie 32-Bit-Ganzzahlen, und | 0 bringt das Ergebnis zurück auf 32 Bit. 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 {
  constructor(key, price, next) {
    this.key = key;
    this.price = price;
    this.next = next;
  }
}

Die Tabelle bekommt ihre Hashfunktion von außen, damit du zwei davon vergleichen kannst. compares zählt die Schlüsselvergleiche:

class PriceTable {
  constructor(hash) {
    this.hash = hash;
    this.buckets = new Array(4).fill(null);
    this.size = 0;
    this.compares = 0;
  }

  index(key) {
    return this.hash(key) % this.buckets.length;
  }

  put(key, price) {
    const i = this.index(key);
    for (let e = this.buckets[i]; e !== null; e = e.next) {
      this.compares++;
      if (e.key === key) {
        e.price = price;
        return;
      }
    }
    this.buckets[i] = new Entry(key, price, this.buckets[i]);
    this.size++;
    const limit = Math.floor((this.buckets.length * 3) / 4);
    if (this.size > limit) this.resize();
  }

  resize() {
    const fresh = new Array(this.buckets.length * 2).fill(null);
    for (const head of this.buckets) {
      for (let e = head; e !== null; e = e.next) {
        const i = this.hash(e.key) % fresh.length;
        fresh[i] = new Entry(e.key, e.price, fresh[i]);
      }
    }
    this.buckets = fresh;
  }

  get(key) {
    const i = this.index(key);
    for (let e = this.buckets[i]; e !== null; e = e.next) {
      this.compares++;
      if (e.key === key) return e.price;
    }
    return null;
  }
}

• put lä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.
• get läuft dieselbe Kette entlang und hält am Schlüssel an.

Probier es aus

Ergänze

Die Bucket-Nummer:

return this.hash(key) % ;

Prüfen

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.

index(key) {
  return this.hash(key) % this.buckets.length;
}

put(key, price) {
  const i = this.index(key);
  for (let e = this.buckets[i]; e !== null; e = e.next) {
    this.compares++;
    if (e.key === key) {
      e.price = price;
      return;
    }
  }
  this.buckets[i] = new Entry(key, price, this.buckets[i]);
  this.size++;
  const limit = Math.floor((this.buckets.length * 3) / 4);
  if (this.size > limit) this.resize();
}

resize() {
  const fresh = new Array(this.buckets.length * 2).fill(null);
  for (const head of this.buckets) {
    for (let e = head; e !== null; e = e.next) {
      const i = this.hash(e.key) % fresh.length;
      fresh[i] = new Entry(e.key, e.price, fresh[i]);
    }
  }
  this.buckets = fresh;
}

Schritt für Schritt, in Worten

1. Ein Preis-Cache mit 4 Buckets. Der Bucket eines Schlüssels ist sein Hash % 4.
2. SKU-1003: 1091696434 % 4 = 2. SKU-1001: % 4 = 0. Leere Buckets: keine Vergleiche.
3. 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.
4. 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.
5. resize macht 8 Buckets. Jeder Schlüssel wird mit % 8 neu berechnet: Er bleibt bei seiner Nummer oder wandert um 4 nach oben.
6. Die neue Tabelle: Jede Kette hat ein Paar, darum macht ein get einen Vergleich. Das Vergrößern kostet n, kommt aber selten vor.

const cache = new PriceTable(skuHash);
cache.put("SKU-1003", 24.9);
cache.put("SKU-1001", 12.5);
cache.put("SKU-1007", 8.99);
cache.printBuckets();
console.log("---");
cache.put("SKU-1005", 45.5);
cache.printBuckets();

Ausgabe

0: SKU-1001
1:
2: SKU-1007 SKU-1003
3:
---
0: SKU-1001
1:
2: SKU-1003
3:
4: SKU-1005
5:
6: SKU-1007
7:

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:

const cache = new PriceTable(skuHash);
const caps = [];
for (let n = 2001; n <= 2007; n++) {
  cache.put(`SKU-${n}`, 10);
  caps.push(cache.buckets.length);
}
console.log(caps.join(" "));

Antwort

4 4 4 8 8 8 16

4 4 4 4 8 8 8

4 8 16 16 16 16 16

Prüfen

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.

function compares(cache, n) {
  for (let i = 0; i < n; i++) cache.put(`SKU-${10000 + i}`, 1 + i);
  for (let i = 0; i < n; i++) cache.get(`SKU-${10000 + i}`);
  return cache.compares;
}

console.log(`erster Buchstabe: ${compares(new PriceTable((key) => key.charCodeAt(0)), 1000)}`);
console.log(`ganze SKU: ${compares(new PriceTable(skuHash), 1000)}`);

Ausgabe

erster Buchstabe: 1000000
ganze SKU: 2593

Lass 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

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

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: _buckets hält die Nummer des ersten Paares, und die Paare in _entries haben einen next-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 sich dict die 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“:

resize() {
  const fresh = new Array(this.buckets.length * 2).fill(null);
  for (const head of this.buckets) {
    for (let e = head; e !== null; e = e.next) {
      const i = this.hash(e.key) % this.buckets.length;
      fresh[i] = new Entry(e.key, e.price, fresh[i]);
    }
  }
  this.buckets = fresh;
}

const cache = new PriceTable(skuHash);
cache.put("SKU-1003", 24.9);
cache.put("SKU-1001", 12.5);
cache.put("SKU-1007", 8.99);
cache.put("SKU-1005", 45.5);
const p1003 = cache.get("SKU-1003");
console.log(`SKU-1003: ${p1003 ?? "keiner"}`);
const p1001 = cache.get("SKU-1001");
console.log(`SKU-1001: ${p1001 ?? "keiner"}`);
const p1007 = cache.get("SKU-1007");
console.log(`SKU-1007: ${p1007 ?? "keiner"}`);
const p1005 = cache.get("SKU-1005");
console.log(`SKU-1005: ${p1005 ?? "keiner"}`);

Ausgabe

SKU-1003: 24.9
SKU-1001: 12.5
SKU-1007: keiner
SKU-1005: keiner

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1resize() {2 const fresh = new Array(this.buckets.length * 2).fill(null);3 for (const head of this.buckets) {4 for (let e = head; e !== null; e = e.next) {5 const i = this.hash(e.key) % this.buckets.length;6 fresh[i] = new Entry(e.key, e.price, fresh[i]);7 }8 }9 this.buckets = fresh;10}

Prüfen

Ü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:

Ausgabe

SKU-1001: 10.5
SKU-1005: 11.5
SKU-1009: keiner
SKU-1012: 13.5
Produkte: 3

Weitere Aufgaben

• Linear Probing. Schreibe eine ProbeTable ohne 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

Teste dich

1. Die Tabelle hat 8 Buckets. Ein Schlüssel hat den Hash 1091696436. In welchem Bucket liegt er?

Bucket 4Bucket 6Bucket 0

2. Warum wird beim Wachsen der Tabelle jeder Schlüssel neu berechnet, statt die Buckets einfach zu kopieren?

Weil sich der Hash des Schlüssels ändertEr wird nicht neu berechnet: Die Buckets werden kopiertWeil die Bucket-Nummer Hash % Anzahl der Buckets ist und sich die Anzahl der Buckets geändert hat

3. Die Hashfunktion gibt den ersten Buchstaben der SKU zurück, und jede SKU beginnt mit „S“. Was kostet get bei n Produkten?

O(log n)O(n): Alle liegen im selben Bucket, und get läuft die ganze Kette entlangO(1): Es ist ja eine Hashtabelle

4. Was stimmt für das dict in Python?

Es sortiert die Schlüssel alphabetischEs hält Kollisionen in Ketten wie HashMapEs sucht einen anderen freien Platz im selben Array (offene Adressierung) und merkt sich die Reihenfolge des Einfügens

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Amortisierte Komplexität · Das dynamische Array von innen · Verkettete Liste · Stapel und Warteschlange
• Geht weiter in: Binärer Suchbaum · Zwei Zeiger · Gleitendes Fenster · Präfixsummen
• Aufgaben zum Thema: Datenstrukturen