Hashcodes und Hashfunktionen

Kurz gesagt: Ein Hashcode ist eine Zahl, die aus dem Schlüssel berechnet wird; Map und Set wählen damit den Bucket, in dem sie suchen, und finden so einen Schlüssel auch unter einer Million schnell.

Problem

Der Platz wurde zweimal verkauft

Die Theaterkasse hält die verkauften Plätze in einer Map: Platz → Name des Zuschauers. Ein Platz ist eine Klasse mit Reihe und Nummer:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }
}

const bookings = new Map();
bookings.set(new Seat(5, 12), "Maria");

console.log(bookings.get(new Seat(5, 12)));
console.log(bookings.size);
bookings.set(new Seat(5, 12), "Jonas");
console.log(bookings.size);

Ausgabe

undefined
1
2

Maria hat Platz 5/12 gekauft, aber get mit demselben Platz liefert undefined. Dann kauft Jonas denselben Platz, und die Map hat jetzt zwei Schlüssel 5/12. Warum?

Die Idee

Hash: eine Zahl aus dem Schlüssel

Eine Map vergleicht den Schlüssel nicht mit allen anderen. Sie berechnet aus dem Schlüssel eine ganze Zahl und weiß daraus, wo sie suchen muss. Diese Zahl heißt Hash (Hashcode). JavaScript zeigt sie nicht: Die Engine berechnet sie, und es gibt keine Funktion, die sie zurückgibt. Damit du siehst, wie es funktioniert, hier eine Hashfunktion für Text. Die Formel ist dieselbe wie in Java:

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

console.log(hashOf("Maria"));
console.log(hashOf("Maria"));
console.log(hashOf("Marie"));
console.log(hashOf("maria"));

Ausgabe

74113750
74113750
74113754
103666422

• Derselbe Text gibt dieselbe Zahl, jedes Mal.
• Eine kleine Änderung gibt eine andere Zahl: „Maria“, „Marie“ und „maria“ sind drei verschiedene Hashes.
• Ein Hash ist schnell berechnet, egal wie viele Schlüssel in der Map sind.
• charCodeAt(i) ist der Code des Zeichens. | 0 hält das Ergebnis als ganze 32-Bit-Zahl, wie int in Java. Wird es zu groß, läuft es über und kann negativ werden.

Eine Map nutzt ihre eigene Hashfunktion, nicht diese. Aber die Idee ist dieselbe.

Die Methode, die die Zahl macht, heißt Hashfunktion.

Genauer, für Neugierige

• Die Formel ist s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1], wobei s[i] der Code jedes Zeichens ist. Die Schleife berechnet sie, indem sie bei jedem Schritt mit 31 multipliziert und den nächsten Code addiert.

• Kryptografische Hashfunktionen wie SHA-256 sind etwas anderes. Sie geben ein langes Ergebnis, und es ist praktisch unmöglich, zwei Texte mit demselben Hash zu finden. Deshalb prüft man mit ihnen, ob eine Datei nicht verändert wurde, und speichert damit Passwörter. hashOf() ist für schnelles Suchen da und gibt keinen solchen Schutz.

Sieh es dir an

Die Buckets

Innen ist eine Map ein Array von Buckets. Die Nummer des Buckets für einen Schlüssel ist der Rest des Hashs bei der Division durch die Anzahl der Buckets. Der Hash kommt hier aus hashOf, weil der, den eine Map nutzt, nicht sichtbar ist:

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.

• set berechnet den Bucket und legt das Paar dort ab. get berechnet denselben Bucket und sucht nur darin. Deshalb ist es auch mit einer Million Schlüssel schnell.
• % kann in JavaScript wie in Java eine negative Zahl geben: -7 % 8 ist -7. Deshalb steht da ((hash % buckets) + buckets) % buckets: So ist der Rest nie negativ. Eine Bucket-Nummer kann nicht negativ sein.
• „Jonas“ und „Finn“ sind in Bucket 3 gelandet. Das heißt Kollision. Darum geht es in der nächsten Karte.

Genauer, für Neugierige

• Wie genau eine Map den Bucket berechnet, hängt von der Engine ab (V8 in Chrome und Node, eine andere in Firefox). Der Sprachstandard sagt nur, dass die Suche im Durchschnitt schneller sein muss als ein Durchlaufen von allem.

console.log(-7 % 8, ((-7 % 8) + 8) % 8);

Ausgabe

-7 1

Probier es aus

Welcher Bucket?

In einer eigenen Hashtabelle ist der Hash einer ganzen Zahl meist die Zahl selbst. Die Bestellnummern kommen in eine Map mit 4 Buckets.

Was gibt das Programm aus?

const orderIds = [6, 10, 13, 21];
for (const id of orderIds) {
  console.log(`${id} -> Bucket ${id % 4}`);
}

Antwort

6 -> Bucket 1
10 -> Bucket 2
13 -> Bucket 3
21 -> Bucket 4

6 -> Bucket 6
10 -> Bucket 10
13 -> Bucket 13
21 -> Bucket 21

6 -> Bucket 2
10 -> Bucket 0
13 -> Bucket 1
21 -> Bucket 3

6 -> Bucket 2
10 -> Bucket 2
13 -> Bucket 1
21 -> Bucket 1

Prüfen

Die Idee

Kollision: Der Hash findet den Bucket, der Vergleich findet den Schlüssel

Verschiedene Schlüssel können denselben Hash haben. Mit hashOf ist, wie bei hashCode in Java, das bekannteste Beispiel:

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

console.log(hashOf("Aa"), hashOf("BB"));

const codes = new Map();
codes.set("Aa", 1);
codes.set("BB", 2);
console.log(codes.get("Aa"), codes.get("BB"));

Ausgabe

2112 2112
1 2

Eine Map behält beide Schlüssel und verwechselt sie nicht. Sie hat ihre eigene Hashfunktion, mit der die Kollisionen bei anderen Schlüsseln passieren, aber sie ist darauf vorbereitet. Ein Bucket hält mehrere Paare, und get vergleicht den Schlüssel mit jedem davon, bis es den gesuchten findet.

Die zwei Schritte arbeiten also so:

1. Der Hash sagt, in welchem Bucket gesucht wird.
2. Der Vergleich sagt, welcher der Schlüssel im Bucket der gesuchte ist.

Jetzt ist klar, was mit dem Theaterplatz passiert ist. Eine Map vergleicht Schlüssel fast wie ===: Text und Zahlen nach Wert, aber Objekte nach Referenz. Die beiden Objekte new Seat(5, 12) sind zwei verschiedene Objekte, also auch zwei verschiedene Schlüssel. Ein Schlüssel, der dasselbe Objekt ist, wird gefunden:

const seat = new Seat(5, 12);
const bookings = new Map();
bookings.set(seat, "Maria");
console.log(bookings.get(seat));

Ausgabe

Maria

Die Idee

Kein equals und hashCode: ein Schlüssel aus Text

In Java und Python sagt die Klasse, wann zwei Objekte gleich sind (equals, __eq__) und was ihr Hash ist (hashCode, __hash__). In JavaScript geht das nicht. Map und Set vergleichen Objekte nach Referenz und rufen deine Methoden nicht auf. Selbst wenn du equals schreibst, schaut die Map nicht darauf:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }

  equals(other) {
    return other instanceof Seat && this.row === other.row && this.number === other.number;
  }
}

const bookings = new Map();
bookings.set(new Seat(5, 12), "Maria");

console.log(bookings.get(new Seat(5, 12)));
console.log(bookings.size);
bookings.set(new Seat(5, 12), "Jonas");
console.log(bookings.size);

Ausgabe

undefined
1
2

Die übliche Lösung ist, den Schlüssel zu Text zu machen, gebaut aus den Feldern, die sagen, welcher Platz es ist. Text wird nach Wert verglichen:

class Seat {
  constructor(row, number) {
    this.row = row;
    this.number = number;
  }

  key() {
    return `${this.row}/${this.number}`;
  }
}

const bookings = new Map();
bookings.set(new Seat(5, 12).key(), "Maria");

console.log(bookings.get(new Seat(5, 12).key()));
console.log(bookings.size);
bookings.set(new Seat(5, 12).key(), "Jonas");
console.log(bookings.size);

Ausgabe

Maria
1
1

Die Regeln für einen Textschlüssel sind dieselben wie der Vertrag in Java:

• Zwei Objekte, die derselbe Platz sind, geben denselben Schlüssel. Immer.
• Zwei verschiedene Objekte geben verschiedene Schlüssel. Dafür ist der Schrägstrich zwischen den Feldern da.
• In den Schlüssel kommen nur die Felder, die zwei Objekte zu demselben machen.

Genauer, für Neugierige

• Ohne Trennzeichen geraten die Schlüssel durcheinander: Platz 51/2 und Platz 5/12 geben beide „512“.

console.log(`${51}${2}`, `${5}${12}`, `${51}/${2}` === `${5}/${12}`);

Ausgabe

512 512 false

• Brauchst du auch das Objekt selbst, leg es als Wert hinein: bookings.set(seat.key(), { seat, name: "Maria" }).

Probier es aus

Finde den Fehler

Der Katalog hält die Produkte in einer Map mit einem Textschlüssel. Zwei Produkte mit demselben Code sind dasselbe Produkt, auch wenn sich der Preis geändert hat. Aber has mit dem neuen Preis gibt false zurück:

const catalog = new Map();
const old = new Product("A-100", 25.0);
catalog.set(old.key(), old);
// Der Preis ist gesunken, aber es ist dasselbe Produkt.
console.log(catalog.has(new Product("A-100", 19.9).key()));

Ausgabe

false

In welcher Zeile der Klasse steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1class Product {2 constructor(code, price) {3 this.code = code;4 this.price = price;5 }67 key() {8 return `${this.code}/${this.price}`;9 }10}

Prüfen

Die Idee

Die Buckets füllen sich

Bei vielen Paaren werden die Buckets lang, und die Suche wird langsamer. Deshalb wächst eine Map:

• Innen muss auch eine Map mehr Buckets anlegen, wenn sie sich füllt, und die Schlüssel neu verteilen, um schnell zu bleiben.
• Wann genau und um wie viel, hängt von der Engine ab, und das Programm kann es nicht sehen.
• Deshalb sind set und get im Durchschnitt schnell, aber ab und zu dauert ein set länger.

Es gibt auch eine Falle. Ein Schlüssel darf sich nicht ändern, während er in einer Map oder einem Set liegt:

const seat = new Seat(5, 12);
const sold = new Set();
sold.add(seat.key());

seat.number = 13;
console.log(sold.has(seat.key()));
console.log(sold.has(new Seat(5, 12).key()));
console.log(sold.size);

Ausgabe

false
true
1

Hier ist die Falle eine andere. Das Set hält den Text „5/12“, und der ändert sich nicht mit dem Objekt mit. Nach seat.number = 13 ist der Schlüssel von seat „5/13“ und wird nicht gefunden, während „5/12“ noch im Set ist, für einen Platz, der niemandem mehr verkauft ist. Ein Textschlüssel ist eine Momentaufnahme des Objekts im Augenblick von add. Deshalb ist es eine gute Idee, dass sich die Felder, aus denen der Schlüssel gebaut wird, nicht ändern.

Genauer, für Neugierige

• Ein Schlüssel, der das Objekt selbst ist, verliert das Objekt nicht, wenn es sich ändert: Die Map findet es nach Referenz. Aber dann ist new Seat(5, 12) ein anderer Schlüssel. Die Wahl ist zwischen „dasselbe Objekt“ und „dieselben Werte“.

Übung

Eigene Schlüssel

Löse die Aufgaben in deinem Editor.

1. Ein Schlüssel für eine Person. Eine Klasse Person mit Vorname, Nachname und Alter und einer Methode key(), die aus den drei Feldern einen Textschlüssel macht. Leg Jonas Weber mit 30 zweimal an und einmal mit 31. Gib die Schlüssel aus und wie viele verschiedene Personen in einer Map mit key() als Schlüssel bleiben.

Ausgabe

Jonas/Weber/30
Jonas/Weber/30
Jonas/Weber/31
Verschiedene Personen: 2

2. Der Roboter im Lager. Der Roboter startet in Zelle (0, 0) und macht die Schritte NNEESWWN: N ist nach oben (y + 1), S nach unten, E nach rechts (x + 1), W nach links. Wie viele verschiedene Zellen hat er besucht, die Startzelle mitgezählt? Legst du Objekte dieser Klasse in ein Set, sagt das Programm 9, es sollte aber 7 sagen. Repariere es:

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

Ausgabe

Schritte: 8
Verschiedene Zellen: 7

3. Ein Hash einer Datei. Eine Funktion hashFileContent(filePath) liest die Datei und gibt den Hash ihres Inhalts als hexadezimalen Text zurück. Nimm SHA-256 aus dem eingebauten Modul node:crypto: createHash("sha256").update(content).digest("hex"). Schreib drei Berichte: a.txt und b.txt mit „Bericht für Oktober: 1250 €“ und c.txt mit „Bericht für Oktober: 1260 €“. Vergleiche ihre Hashes. Verschiedene Hashes heißen verschiedene Dateien, und gleiche SHA-256-Hashes heißen in der Praxis gleiche Dateien.

Ausgabe

a.txt: db6cf1fbd452ee116b95c9ed5d604e3b2b93d34a0e660991e991e1d84f43898f
b.txt: db6cf1fbd452ee116b95c9ed5d604e3b2b93d34a0e660991e991e1d84f43898f
c.txt: 7fad428479b6c5af07d54dcdf9665ded486847b65ef67aec7681a24e450d4902
a und b: gleich
a und c: verschieden

Weitere Aufgaben

• Eine eigene Hashtabelle. Eine Fortsetzung der Benutzertabelle aus der letzten Lektion, diesmal ohne Map. Leg ein Array aus 8 Buckets an, jeder ein Array aus Paaren von Benutzername und E-Mail. Die Hashfunktion ist die Summe der Zeichencodes im Namen (charCodeAt). Schreib add, get und eine Methode, die ausgibt, wie viele Paare in jedem Bucket sind.
• Eine ID aus einer E-Mail. generateUserId(email) gibt "U" und die ersten 8 Zeichen des SHA-256 der kleingeschriebenen E-Mail zurück. Ist die ID für Jonas@Example.com und jonas@example.com dieselbe? Können zwei verschiedene E-Mails dieselbe ID bekommen? Wie würdest du es herausfinden?
• Kollisionen zählen. Berechne den Bucket der Schlüssel user1 … user1000 mit hashOf aus der Lektion bei 16, 64 und 1024 Buckets und zähle, wie viele Schlüssel in einem Bucket landen, in dem schon ein Schlüssel ist.
• Der Schuhkarton. Eine Klasse Box mit Breite, Höhe und Tiefe. Zwei Kartons sind gleich, wenn ihre Maße gleich sind, in derselben Reihenfolge. Schreib key() und prüfe die Kartons 30×20×10 und 10×20×30 in einem Set.

Test

Teste dich

1. Warum ist get bei einer Map auch mit einer Million Schlüssel schnell?

Eine Map ist eine Hashtabelle: Aus dem Schlüssel berechnet sie, in welchem Bucket sie suchtEine Map hält die Schlüssel sortiert und sucht durch HalbierenEine Map läuft sehr schnell über die Schlüssel

2. Zwei verschiedene Schlüssel haben denselben Hash. Was passiert?

Die Map wirft einen FehlerDer zweite löscht den erstenBeide liegen in einem Bucket, und der Vergleich der Schlüssel unterscheidet sie

3. Der Schlüssel ist ein Objekt: bookings.set(new Seat(5, 12), "Maria"). Was gibt bookings.get(new Seat(5, 12)) zurück?

"Maria"undefined: Eine Map vergleicht Objekte nach Referenz, und das ist ein anderes ObjektEs wirft einen Fehler

4. Du gibst Seat eine Methode equals(other), die Reihe und Nummer vergleicht. Nutzt die Map sie?

Nur wenn auch das Set sie hatNein: Map und Set rufen deine Methoden nicht auf, und man kann ihnen keinen anderen Vergleich gebenJa, eine Map ruft equals auf, wenn es da ist

5. Der Schlüssel des Platzes ist der Text ${row}/${number}. Wozu braucht man den Schrägstrich?

Ohne ihn geben Platz 51/2 und Platz 5/12 denselben Schlüssel, "512"Für eine schnellere SucheEine Map nimmt keinen Text ohne Sonderzeichen an

6. Das key() eines Produkts ist ${code}/${price}, und das Produkt ist zu einem anderen Preis dasselbe. Was ist falsch?

NichtsDer Preis sollte zuerst kommenIm Schlüssel steckt ein Feld, das nicht sagt, welches Produkt es ist: Mit neuem Preis ist der Schlüssel anders, und das Produkt wird nicht gefunden

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Dateien · Arrays: push, splice und sort · Stack, Queue und verkettete Liste · Map und Set
• Geht weiter in: Daten, switch und Destrukturierung · Hashtabelle · Passwörter · Abhängigkeiten: fremder Code, den dein Code ausführt
• Aufgaben zum Thema: Collections