Hashcodes und Hashfunktionen

Kurz gesagt: Ein Hashcode ist eine Zahl, die hashCode() aus dem Schlüssel berechnet; HashMap wählt damit den Bucket, in dem es sucht, und findet 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 {
    int row;
    int number;

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

Map<Seat, String> bookings = new HashMap<>();
bookings.put(new Seat(5, 12), "Maria");

System.out.println(bookings.get(new Seat(5, 12)));
System.out.println(bookings.size());
bookings.put(new Seat(5, 12), "Jonas");
System.out.println(bookings.size());

Ausgabe

null
1
2

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

Die Idee

Hashcode: eine Zahl aus dem Schlüssel

Eine HashMap 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 Hashcode, und die Methode hashCode() gibt sie zurück. Jedes Objekt hat sie, denn sie steht in Object.

System.out.println("Maria".hashCode());
System.out.println("Maria".hashCode());
System.out.println("Marie".hashCode());
System.out.println("maria".hashCode());

Ausgabe

74113750
74113750
74113754
103666422

• Derselbe Text gibt dieselbe Zahl, jedes Mal und auf jedem Computer.
• Eine kleine Änderung gibt eine andere Zahl: „Maria“, „Marie“ und „maria“ sind drei verschiedene Hashcodes.
• Ein Hashcode ist schnell berechnet, egal wie viele Schlüssel in der Map sind.

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

Genauer, für Neugierige

• Für String ist die Formel in der Java-Dokumentation festgelegt: s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1], wobei s[i] der Code jedes Zeichens ist. Das Ergebnis ist ein int, deshalb wird es beim Überlauf negativ.

• 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. hashCode() ist für schnelles Suchen da und gibt keinen solchen Schutz.

Sieh es dir an

Die Buckets

Innen ist eine HashMap 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:

String[] keys = { "Laura", "Jonas", "Tom", "Finn" };
int buckets = 8;
for (String key : keys) {
    int hash = key.hashCode();
    int index = Math.floorMod(hash, buckets);
    System.out.println(key + " -> " + hash + " -> Bucket " + index);
}

Schritt für Schritt, in Worten

1. Vier Schlüssel und acht leere Buckets, nummeriert von 0 bis 7.
2. "Laura".hashCode() 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. equals mit "Jonas": nein. Mit "Finn": ja.

• put 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.
• Math.floorMod ist ein Rest der Division, der nie negativ ist. Ein Hashcode kann negativ sein, eine Bucket-Nummer nicht.
• „Jonas“ und „Finn“ sind in Bucket 3 gelandet. Das heißt Kollision. Darum geht es in der nächsten Karte.

Genauer, für Neugierige

• Die echte HashMap berechnet den Index etwas anders: (h ^ (h >>> 16)) & (n - 1). Die Anzahl der Buckets n ist immer eine Zweierpotenz, und & (n - 1) ist ein schneller Rest der Division durch n. Die Zahlen sind dort also andere, aber das Prinzip ist dasselbe.

Probier es aus

Welcher Bucket?

Der Hashcode eines Integer ist die Zahl selbst. Die Bestellnummern kommen in eine Map mit 4 Buckets.

Was gibt das Programm aus?

int[] orderIds = { 6, 10, 13, 21 };
for (int id : orderIds) {
    Integer key = id;
    System.out.println(id + " -> Bucket " + Math.floorMod(key.hashCode(), 4));
}

Antwort

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

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

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

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

Prüfen

Die Idee

Kollision: hashCode findet den Bucket, equals findet den Schlüssel

Verschiedene Schlüssel können denselben Hashcode haben. Die zwei bekanntesten Beispiele:

System.out.println("Aa".hashCode() + " " + "BB".hashCode());

Map<String, Integer> codes = new HashMap<>();
codes.put("Aa", 1);
codes.put("BB", 2);
System.out.println(codes.get("Aa") + " " + codes.get("BB"));

Ausgabe

2112 2112
1 2

Die beiden Schlüssel sind in einem Bucket, aber die Map verwechselt sie nicht. Der Bucket hält eine kleine verkettete Liste von Paaren. get geht sie entlang und vergleicht mit equals, bis es den Schlüssel findet.

Die zwei Schritte arbeiten also so:

1. hashCode() sagt, in welchem Bucket gesucht wird.
2. equals() sagt, welcher der Schlüssel im Bucket der gesuchte ist.

Jetzt ist klar, was mit dem Theaterplatz passiert ist. Seat überschreibt keine der beiden Methoden, also nutzt es die Versionen aus Object. Dort ist equals dasselbe wie ==, und hashCode ist meist für jedes Objekt anders. Die beiden Objekte new Seat(5, 12) sind zwei verschiedene Objekte, also auch zwei verschiedene Schlüssel.

Die Idee

Der Vertrag: equals und hashCode zusammen

Seat muss sagen, wann zwei Plätze derselbe Platz sind, und gleichen Plätzen denselben Hashcode geben:

class Seat {
    int row;
    int number;

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

    @Override
    public boolean equals(Object other) {
        if (!(other instanceof Seat)) {
            return false;
        }
        Seat s = (Seat) other;
        return row == s.row && number == s.number;
    }

    @Override
    public int hashCode() {
        return 31 * row + number;
    }
}

Mit demselben Code in main wie in der ersten Karte:

Map<Seat, String> bookings = new HashMap<>();
bookings.put(new Seat(5, 12), "Maria");

System.out.println(bookings.get(new Seat(5, 12)));
System.out.println(bookings.size());
bookings.put(new Seat(5, 12), "Jonas");
System.out.println(bookings.size());

Ausgabe

Maria
1
1

Die Regeln, die Java erwartet:

• Wenn a.equals(b), dann a.hashCode() == b.hashCode(). Immer.
• Wenn die Hashcodes gleich sind, können die Objekte verschieden sein. Das ist eine Kollision.
• Wenn du equals überschreibst, überschreib auch hashCode, mit denselben Feldern.

Genauer, für Neugierige

• Warum 31? Es ist eine ungerade Primzahl, und sie mischt gut. Die Multiplikation mit 31 macht den Hash von der Reihenfolge abhängig: Platz 5/12 und Platz 12/5 haben verschiedene Hashcodes. Mit row + number würden beide im selben Bucket landen.
• Statt der Formel kannst du Objects.hash aus java.util.Objects schreiben. Es berechnet dasselbe aus den Feldern, die du ihm gibst:

@Override
public int hashCode() {
    return Objects.hash(row, number);
}

• equals bekommt ein Object, deshalb prüft es zuerst mit instanceof, ob das andere überhaupt ein Seat ist, und wandelt es dann um. Das ist der Downcast aus dem Modul „Vererbung und Polymorphie“.

Probier es aus

Finde den Fehler

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

Set<Product> catalog = new HashSet<>();
catalog.add(new Product("A-100", 25.0));
// Der Preis ist gesunken, aber es ist dasselbe Produkt.
System.out.println(catalog.contains(new Product("A-100", 19.9)));

Ausgabe

false

In welcher Zeile der Klasse steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1class Product {2 String code;3 double price;45 Product(String code, double price) {6 this.code = code;7 this.price = price;8 }910 @Override11 public boolean equals(Object other) {12 if (!(other instanceof Product)) {13 return false;14 }15 return code.equals(((Product) other).code);16 }1718 @Override19 public int hashCode() {20 return Objects.hash(code, price);21 }22}

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

• Am Anfang gibt es 16 Buckets.
• Gibt es mehr Paare als 75 % der Anzahl der Buckets, legt sie doppelt so viele Buckets an und verteilt alle Schlüssel neu. Die Bucket-Nummer hängt von der Anzahl der Buckets ab, deshalb wird jeder Schlüssel neu berechnet.
• Deshalb sind put und get im Durchschnitt schnell, aber ab und zu dauert ein put länger.

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

Seat seat = new Seat(5, 12);
Set<Seat> sold = new HashSet<>();
sold.add(seat);

seat.number = 13;
System.out.println(sold.contains(seat));
System.out.println(sold.contains(new Seat(5, 12)));
System.out.println(sold.size());

Ausgabe

false
false
1

Der Platz wurde in den Bucket für 5/12 gelegt. Dann wurde seine Nummer 13, und der Hashcode hat sich geändert. contains(seat) sucht im Bucket für 5/13 und findet ihn nicht. contains(new Seat(5, 12)) sucht im richtigen Bucket, aber das Objekt dort ist nicht mehr gleich 5/12. Das Element ist im Set (die Größe ist 1), aber es kann nicht gefunden werden. Deshalb ist es eine gute Idee, dass die Felder eines Schlüssels final sind.

Genauer, für Neugierige

• Diese 75 % heißen Ladefaktor (load factor), und du kannst ihn im Konstruktor setzen: new HashMap<>(64, 0.75f). Weißt du, wie viele Schlüssel es geben wird, gib die Anfangszahl der Buckets an, dann muss die Map unterwegs nicht wachsen.
• Ab Java 8 wird ein Bucket mit mehr als 8 Paaren (TREEIFY_THRESHOLD) von einer Liste zu einem balancierten Baum, wenn es mindestens 64 Buckets gibt. Bleiben nach einem Neuverteilen 6 oder weniger Paare in so einem Bucket (UNTREEIFY_THRESHOLD), wird der Baum wieder zur Liste. So braucht eine Suche bei vielen Kollisionen in einem Bucket mit n Paaren etwa log n Vergleiche statt n.

Übung

Eigene Hashcodes

Löse die Aufgaben in deinem Editor.

1. Ein Hashcode für eine Person. Eine Klasse Person mit Vorname, Nachname und Alter. Überschreib equals und hashCode. Nimm für hashCode das Rezept: Beginne bei 17, und für jedes Feld result = 31 * result + der Hash des Feldes. Für ein int-Feld ist der Hash die Zahl selbst. Leg Jonas Weber mit 30 zweimal an und einmal mit 31. Gib die Hashcodes aus und wie viele verschiedene Personen in einem HashSet bleiben.

Ausgabe

-1469209977
-1469209977
-1469209976
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? Halte sie in einem HashSet<Point>. Mit dieser Klasse sagt das Programm 9, es sollte aber 7 sagen. Repariere es:

class Point {
    int x;
    int y;

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

Ausgabe

Schritte: 8
Verschiedene Zellen: 7

3. Ein Hash einer Datei. Eine Methode hashFileContent(String filePath) liest die Datei und gibt den Hashcode ihres Inhalts als hexadezimalen Text zurück: Integer.toHexString(content.hashCode()). 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, dass die Dateien sicher verschieden sind. Gleiche Hashes heißen „fast sicher gleich“: Bei einem int ist eine Kollision möglich, deshalb nimmt man für eine echte Prüfung SHA-256.

Ausgabe

a.txt: ad5bbcd3
b.txt: ad5bbcd3
c.txt: ad69d454
a und b: gleich
a und c: verschieden

Weitere Aufgaben

• Eine eigene Hashtabelle. Eine Fortsetzung der Benutzertabelle aus der letzten Lektion, diesmal ohne HashMap. Leg ein Array aus 8 Buckets an, jeder eine ArrayList aus Paaren von Benutzername und E-Mail. Die Hashfunktion ist die Summe der Zeichencodes im Namen. Schreib add, get und eine Methode, die ausgibt, wie viele Paare in jedem Bucket sind.
• Eine ID aus einer E-Mail. generateUserId(String email) gibt "U" + Integer.toHexString(email.toLowerCase().hashCode()) 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 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 equals und hashCode mit Objects.hash und prüfe die Kartons 30×20×10 und 10×20×30 in einem HashSet.

Test

Teste dich

1. Was macht eine HashMap mit dem Hashcode eines Schlüssels?

Sie vergleicht ihn mit allen anderen HashcodesSie speichert ihn statt des SchlüsselsSie berechnet daraus die Nummer des Buckets, in dem sie sucht

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

Der zweite löscht den erstenHashMap wirft eine ExceptionBeide liegen in einem Bucket, und equals unterscheidet sie

3. a.equals(b) ist true. Was muss für ihre Hashcodes gelten?

Sie müssen verschieden seinNichtsa.hashCode() == b.hashCode(), immer

4. Du nimmst deine eigene Klasse Seat als Schlüssel, ohne equals und hashCode zu überschreiben. Was gibt get(new Seat(5, 12)) zurück?

null: Das neue Objekt ist ein anderes Objekt, und equals und hashCode aus Object schauen nicht auf die FelderDen Wert, der mit put(new Seat(5, 12), …) hineingelegt wurdeEs wirft eine Exception

5. Welches Feld darf sicher in den hashCode eines Schlüssels eingehen?

Ein Feld, das sich nicht ändert (final) und das auch equals vergleichtEine Zufallszahl, die im Konstruktor gewählt wirdEin Feld, das sich ändert, während das Objekt in einem HashSet liegt

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Dateien · Listen · Stack, Queue und verkettete Liste · HashMap und HashSet
• Geht weiter in: record, switch und Muster · Hashtabelle · Passwörter · Abhängigkeiten: fremder Code, den dein Code ausführt
• Aufgaben zum Thema: Collections