Hashtabellen

Ist 47 in einer Tabelle mit 7 Buckets gespeichert, geht der Computer direkt zu Bucket 47 mod 7 = 5, statt die ganze Tabelle zu durchsuchen.

Aus einem Schlüssel eine Position machen

Bisher hieß einen Wert finden: suchen, bis zu n Schritte in einem unsortierten Array oder einer verketteten Liste. Arrays erreichen aber jede Position in einem Schritt. Was, wenn der Schlüssel selbst die Position verriete? Wären deine Schlüssel kleine ganze Zahlen, etwa Schülernummern von 0 bis 99, könntest du ein Array mit 100 Zellen führen und Schüler k in Zelle k speichern. Die MIT-Unterlagen nennen das ein Direktzugriffs-Array (direct access array). Es scheitert, wenn die möglichen Schlüssel riesig sind, wie Telefonnummern oder Wörter, weil man sich nicht für jeden möglichen Schlüssel eine Zelle leisten kann.

Eine Hashfunktion löst das, indem sie jeden Schlüssel in einen kleinen Bereich von Positionen presst, 0 bis m − 1. Eine einfache für ganze Zahlen ist h(k) = k mod m, der Rest beim Teilen durch m. Das Array mit m Zellen ist die Hashtabelle, und ihre Zellen heißen oft Buckets (Behälter). Um 47 mit m = 7 zu speichern, rechne 47 mod 7 = 5 und leg den Wert in Bucket 5. Um 47 später zu finden, rechne dasselbe und schau nur in Bucket 5.

Kollisionen und Verkettung

Es gibt ein Problem. Bei 7 Buckets und mehr als 7 möglichen Schlüsseln müssen sich manche Schlüssel einen Bucket teilen: 12, 33 und 47 haben alle den Rest 5. Das nennt man Kollision, und die MIT-Unterlagen weisen darauf hin, dass sie sich nach dem Schubfachprinzip nicht vermeiden lässt. Das übliche Mittel ist Verkettung (Chaining): Jeder Bucket hält eine kleine Liste, eine Kette, mit allen Schlüsseln, die dort gelandet sind. 47 zu finden, kostet dann 1 Schritt für den Hash plus einen Vergleich für jeden geprüften Schlüssel in Kette 5. Stehen 12 und 33 davor, sind das 1 + 3 = 4 Schritte.

Wie lang sind die Ketten? Verteilen sich die Schlüssel gleichmäßig, enthält jede Kette etwa n/m Schlüssel, eine Zahl, die man Belegungsfaktor (load factor) nennt. Hält man m ungefähr so groß wie n, bleiben die Ketten kurz, und Finden, Einfügen und Löschen kosten im Mittel eine konstante Zahl von Schritten. Die Gefahr ist eine schlechte Verteilung. Landet jeder Schlüssel im selben Bucket, enthält eine Kette alle n Schlüssel, und die Tabelle ist nicht besser als eine verkettete Liste. Stell im Labor 7 Buckets ein und füg 14, 21 und 28 ein: Alle landen in Bucket 0.

Hashtabellen in JavaScript

Eine Hashtabelle schreibst du selten selbst, weil JavaScript Map und Set hat. Die ECMAScript-Spezifikation sagt, sie müssten „entweder mit Hashtabellen oder mit anderen Mechanismen umgesetzt werden, die im Mittel Zugriffszeiten bieten, die sublinear in der Zahl der Elemente sind“. Mit anderen Worten: map.get(key) und set.has(x) müssen schneller sein, als die ganze Sammlung zu durchsuchen. MDN ergänzt, dass eine Map die Schlüssel in Einfügereihenfolge hält und, anders als ein normales Objekt, keine Standardschlüssel enthält, die mit deinen kollidieren könnten.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, ohne die Liste zu durchsuchen
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true