Zum Inhalt
wannacode

Hashtabelle

Kurz gesagt: Eine Hashtabelle (Dictionary in C#) 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.

var cache = new PriceTable(key => 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.

int[] keys = { 1007, 2043, 3010, 4051 };
int buckets = 8;
foreach (int key in keys)
{
    int hash = key.GetHashCode();
    int index = (hash % buckets + buckets) % buckets;
    Console.WriteLine(key + " -> " + hash + " -> Bucket " + index);
}
Schritt für Schritt, in Worten
  1. Vier Schlüssel (Bestellnummern) und acht leere Buckets, nummeriert von 0 bis 7.
  2. 1007.GetHashCode() ist die Zahl selbst, 1007. Der Rest bei der Division durch 8 ist 7: Das ist der Bucket.
  3. 2043 ergibt Bucket 3.
  4. 3010 ergibt Bucket 2.
  5. 4051 landet auch in Bucket 3: eine Kollision. Die beiden Schlüssel sind in einem Bucket: 4051 hängt wie in einer Kette hinter 2043.
  6. Suche nach 4051: dieselbe Zahl, derselbe Bucket 3. Equals 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:

static int SkuHash(string key)
{
    int h = 0;
    foreach (char c in key)
    {
        h = 31 * h + c;
    }
    return h & 0x7fffffff;
}

Ein Paar ist ein Knoten mit einem Schlüssel, einem Preis und einem Pfeil auf den nächsten in der Kette:

class Entry
{
    public readonly string Key;
    public double Price;
    public Entry? Next;


    public Entry(string key, double price, Entry? next)
    {
        Key = key;
        Price = price;
        Next = next;
    }
}

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

class PriceTable
{
    private readonly Func<string, int> hash;
    private Entry?[] buckets = new Entry?[4];
    private int size = 0;
    public long Compares { get; private set; }


    public PriceTable(Func<string, int> hash)
    {
        this.hash = hash;
    }


    public int Capacity => buckets.Length;


    private int Index(string key) => hash(key) % buckets.Length;


    public void Put(string key, double price)
    {
        int i = Index(key);
        for (var e = buckets[i]; e != null; e = e.Next)
        {
            Compares++;
            if (e.Key == key)
            {
                e.Price = price;
                return;
            }
        }
        buckets[i] = new Entry(key, price, buckets[i]);
        size++;
        if (size > buckets.Length * 3 / 4) Resize();
    }


    private void Resize()
    {
        var fresh = new Entry?[buckets.Length * 2];
        foreach (var head in buckets)
        {
            for (var e = head; e != null; e = e.Next)
            {
                int i = hash(e.Key) % fresh.Length;
                fresh[i] = new Entry(e.Key, e.Price, fresh[i]);
            }
        }
        buckets = fresh;
    }


    public double? Get(string key)
    {
        int i = Index(key);
        for (var e = buckets[i]; e != null; e = e.Next)
        {
            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:

private int Index(string key) => hash(key) % ;

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.

private int Index(string key) => hash(key) % buckets.Length;


public void Put(string key, double price)
{
    int i = Index(key);
    for (var e = buckets[i]; e != null; e = e.Next)
    {
        Compares++;
        if (e.Key == key)
        {
            e.Price = price;
            return;
        }
    }
    buckets[i] = new Entry(key, price, buckets[i]);
    size++;
    if (size > buckets.Length * 3 / 4) Resize();
}


private void Resize()
{
    var fresh = new Entry?[buckets.Length * 2];
    foreach (var head in buckets)
    {
        for (var e = head; e != null; e = e.Next)
        {
            int i = hash(e.Key) % fresh.Length;
            fresh[i] = new Entry(e.Key, e.Price, fresh[i]);
        }
    }
    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.
var 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.WriteLine("---");
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:

var cache = new PriceTable(SkuHash);
var caps = new List<int>();
for (int n = 2001; n <= 2007; n++)
{
    cache.Put($"SKU-{n}", 10);
    caps.Add(cache.Capacity);
}
Console.WriteLine(string.Join(" ", caps));
Antwort

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.

static long Compares(PriceTable cache, int n)
{
    for (int i = 0; i < n; i++) cache.Put($"SKU-{10000 + i}", 1 + i);
    for (int i = 0; i < n; i++) cache.Get($"SKU-{10000 + i}");
    return cache.Compares;
}
Console.WriteLine($"erster Buchstabe: {Compares(new PriceTable(key => key[0]), 1000)}");
Console.WriteLine($"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²)
Algorithmusn = 10n = 1.000n = 100.000
Hash der ganzen Artikelnummer102.593211.990
Hash des ersten Buchstabens1001.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“:

private void Resize()
{
    var fresh = new Entry?[buckets.Length * 2];
    foreach (var head in buckets)
    {
        for (var e = head; e != null; e = e.Next)
        {
            int i = hash(e.Key) % buckets.Length;
            fresh[i] = new Entry(e.Key, e.Price, fresh[i]);
        }
    }
    buckets = fresh;
}
var 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);
Console.WriteLine($"SKU-1003: {cache.Get("SKU-1003")?.ToString() ?? "keiner"}");
Console.WriteLine($"SKU-1001: {cache.Get("SKU-1001")?.ToString() ?? "keiner"}");
Console.WriteLine($"SKU-1007: {cache.Get("SKU-1007")?.ToString() ?? "keiner"}");
Console.WriteLine($"SKU-1005: {cache.Get("SKU-1005")?.ToString() ?? "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.

Ü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?
2. Warum wird beim Wachsen der Tabelle jeder Schlüssel neu berechnet, statt die Buckets einfach zu kopieren?
3. Die Hashfunktion gibt den ersten Buchstaben der SKU zurück, und jede SKU beginnt mit „S“. Was kostet get bei n Produkten?
4. Was stimmt für das dict in Python?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·