Hashcodes und Hashfunktionen

Kurz gesagt: Ein Hashcode ist eine Zahl, die GetHashCode() aus dem Schlüssel berechnet; Dictionary 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
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }
}

Dictionary<Seat, string> bookings = new Dictionary<Seat, string>();
bookings[new Seat(5, 12)] = "Maria";

Console.WriteLine(bookings.ContainsKey(new Seat(5, 12)));
Console.WriteLine(bookings.Count);
bookings[new Seat(5, 12)] = "Jonas";
Console.WriteLine(bookings.Count);

Ausgabe

False
1
2

Maria hat Platz 5/12 gekauft, aber ContainsKey mit demselben Platz sagt False. 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

Ein Dictionary vergleicht den Schlüssel nicht mit allen anderen. Es berechnet aus dem Schlüssel eine ganze Zahl und weiß daraus, wo es suchen muss. Diese Zahl heißt Hashcode, und die Methode GetHashCode() gibt sie zurück. Jedes Objekt hat sie, denn sie steht in object.

Console.WriteLine("Maria".GetHashCode() == "Maria".GetHashCode());
Console.WriteLine("Maria".GetHashCode() == "Marie".GetHashCode());
Console.WriteLine("Maria".GetHashCode() == "maria".GetHashCode());
Console.WriteLine(1004.GetHashCode());

Ausgabe

True
False
False
1004

• Innerhalb eines Laufs gibt derselbe Text dieselbe Zahl.
• Eine kleine Änderung gibt eine andere Zahl: „Maria“, „Marie“ und „maria“ sind drei verschiedene Hashcodes.
• Der Hashcode eines int ist die Zahl selbst.
• Ein Hashcode ist schnell berechnet, egal wie viele Schlüssel im Dictionary sind.

Die Zahl selbst wird für Text hier absichtlich nicht ausgegeben. .NET berechnet den Hashcode eines string bei jedem Lauf des Programms anders, du würdest also eine andere bekommen. Die Vergleiche kommen jedes Mal gleich heraus.

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

Genauer, für Neugierige

• Warum ändert sich der Hashcode von Text? Wäre er im Voraus bekannt, könnte jemand einem Server Tausende Schlüssel mit demselben Hashcode schicken und das Dictionary langsam machen. Deshalb wählt .NET bei jedem Lauf einen zufälligen Startpunkt für die Berechnung. Der Hashcode von Text wird nicht in eine Datei oder Datenbank geschrieben und nicht an ein anderes Programm geschickt: Dort ist er anders.

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

Sieh es dir an

Die Buckets

Innen ist ein Dictionary 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 Hashcode von Text ändert sich bei jedem Lauf, deshalb sind die Schlüssel hier Bestellnummern: Bei ihnen ist der Hashcode die Zahl selbst:

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.

• Das Schreiben bookings[key] = … berechnet den Bucket und legt das Paar dort ab. Die Suche (ContainsKey, TryGetValue, [key]) berechnet denselben Bucket und sucht nur darin. Deshalb ist sie auch mit einer Million Schlüssel schnell.
• % kann in C# wie in Java eine negative Zahl geben: -7 % 8 ist -7. Deshalb steht da (hash % buckets + buckets) % buckets: So ist der Rest nie negativ. Ein Hashcode kann negativ sein, eine Bucket-Nummer nicht.
• 2043 und 4051 sind in Bucket 3 gelandet. Das heißt Kollision. Darum geht es in der nächsten Karte.

Genauer, für Neugierige

• Das echte Dictionary macht aus dem Hashcode eine vorzeichenlose Zahl (uint), die nie negativ ist, und nimmt den Rest der Division durch die Anzahl der Buckets. Diese Zahl ist eine Primzahl (3, 7, 17, 37…), die Zahlen sind dort also andere, aber das Prinzip ist dasselbe.

Console.WriteLine(-7 % 8 + " " + (-7 % 8 + 8) % 8);

Ausgabe

-7 1

Probier es aus

Welcher Bucket?

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

Was gibt das Programm aus?

int[] orderIds = { 6, 10, 13, 21 };
foreach (int id in orderIds)
{
    Console.WriteLine(id + " -> Bucket " + id.GetHashCode() % 4);
}

Antwort

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

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

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

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

Prüfen

Die Idee

Kollision: GetHashCode findet den Bucket, Equals findet den Schlüssel

Verschiedene Schlüssel können denselben Hashcode haben. Der Hashcode eines long ist das exklusive „Oder“ (XOR) seiner oberen und unteren Hälfte, jede mit 32 Bit. In -1 sind alle Bits 1, die beiden Hälften heben sich auf, und es bleibt 0, genau wie für 0 selbst:

Console.WriteLine(0L.GetHashCode() + " " + (-1L).GetHashCode());

Dictionary<long, string> codes = new Dictionary<long, string>();
codes[0L] = "Null";
codes[-1L] = "Minus eins";
Console.WriteLine(codes[0L] + " " + codes[-1L]);

Ausgabe

0 0
Null Minus eins

Die beiden Schlüssel sind in einem Bucket, aber das Dictionary verwechselt sie nicht. Der Bucket hält eine Kette von Paaren. Die Suche geht sie entlang und vergleicht mit Equals, bis sie den Schlüssel findet.

Die zwei Schritte arbeiten also so:

1. GetHashCode() 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 vergleicht Equals Referenzen, und GetHashCode 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 GetHashCode zusammen

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

class Seat
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public override bool Equals(object other)
    {
        if (other is not Seat s)
        {
            return false;
        }
        return Row == s.Row && Number == s.Number;
    }

    public override int GetHashCode()
    {
        return 31 * Row + Number;
    }
}

Mit demselben Code in Main wie in der ersten Karte:

Dictionary<Seat, string> bookings = new Dictionary<Seat, string>();
bookings[new Seat(5, 12)] = "Maria";

Console.WriteLine(bookings.ContainsKey(new Seat(5, 12)));
Console.WriteLine(bookings.Count);
bookings[new Seat(5, 12)] = "Jonas";
Console.WriteLine(bookings.Count);

Ausgabe

True
1
1

Die Regeln, die C# erwartet:

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

Überschreibst du nur Equals, warnt dich der Compiler, aber das Programm kompiliert:

class Seat
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public override bool Equals(object other)
    {
        if (other is not Seat s)
        {
            return false;
        }
        return Row == s.Row && Number == s.Number;
    }
}

Warnung

warning CS0659: 'Seat' overrides Object.Equals(object o) but does not override Object.GetHashCode()

Mit diesem Seat gibt das erste Programm wieder False, 1 und 2 aus: Der Platz ist zweimal verkauft. Die Warnung hält den Compiler nicht an, also lies sie.

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 HashCode.Combine schreiben. Es berechnet einen Hashcode aus den Werten, die du ihm gibst:

public override int GetHashCode()
{
    return HashCode.Combine(Row, Number);
}

• Die Zahl aus HashCode.Combine ändert sich ebenfalls bei jedem Lauf, wie der Hashcode von Text. Für das Dictionary spielt das keine Rolle: Innerhalb eines Laufs haben gleiche Plätze gleiche Hashcodes.
• Equals bekommt ein object, deshalb prüft es zuerst, ob das andere überhaupt ein Seat ist. other is not Seat s ist die Typprüfung aus dem Modul „Vererbung und Polymorphie“: Ist das andere ein Seat, dann ist s dieses Objekt, schon vom Typ Seat. Deshalb ist new Seat(5, 12).Equals("5/12") gleich False.
• In C# hat eine Klasse, die ein Schlüssel wird, meist auch IEquatable<Seat>: eine Methode Equals(Seat other), ohne Umwandlung aus object. Dictionary und HashSet rufen sie auf, wenn sie da ist, und Equals(object) ruft sie nur auf. Die Eigenschaften sind hier nur lesbar. Warum, siehst du in der Karte „Die Buckets füllen sich“:

class Seat : IEquatable<Seat>
{
    public int Row { get; }
    public int Number { get; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public bool Equals(Seat other)
    {
        return other is not null && Row == other.Row && Number == other.Number;
    }

    public override bool Equals(object other)
    {
        return Equals(other as Seat);
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(Row, Number);
    }
}

• Im Modul „Modernes C#“ lernst du record kennen. Mit einer Zeile, record Seat(int Row, int Number);, sind Equals und GetHashCode aus den Eigenschaften fertig, und das erste Programm gibt True, 1 und 1 aus.

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:

HashSet<Product> catalog = new HashSet<Product>();
catalog.Add(new Product("A-100", 25.0));
// Der Preis ist gesunken, aber es ist dasselbe Produkt.
Console.WriteLine(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 Product2{3 public string Code { get; set; }4 public double Price { get; set; }56 public Product(string code, double price)7 {8 Code = code;9 Price = price;10 }1112 public override bool Equals(object other)13 {14 return other is Product p && Code == p.Code;15 }1617 public override int GetHashCode()18 {19 return HashCode.Combine(Code, Price);20 }21}

Prüfen

Die Idee

Die Buckets füllen sich

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

• Am Anfang gibt es keine Buckets. Das erste Hinzufügen legt 3 an.
• Wenn sich die Plätze füllen, legt es mindestens doppelt so viele Buckets an (wieder eine Primzahl) und verteilt alle Schlüssel neu. Die Bucket-Nummer hängt von der Anzahl der Buckets ab, deshalb wird jeder Schlüssel neu berechnet. Hier siehst du, wann es wächst:

Dictionary<string, int> prices = new Dictionary<string, int>();
int capacity = prices.EnsureCapacity(0);
for (int i = 1; i <= 20; i++)
{
    prices["Produkt " + i] = i;
    if (prices.EnsureCapacity(0) != capacity)
    {
        capacity = prices.EnsureCapacity(0);
        Console.WriteLine("Wächst bei Paar " + i + ": " + capacity + " Plätze");
    }
}

Ausgabe

Wächst bei Paar 1: 3 Plätze
Wächst bei Paar 4: 7 Plätze
Wächst bei Paar 8: 17 Plätze
Wächst bei Paar 18: 37 Plätze

• EnsureCapacity(0) gibt zurück, wie viele Plätze das Dictionary hat, ohne etwas zu ändern. Hier dient es nur dazu, zu sehen, wann sich die Tabelle ändert. In einem Dictionary gibt es so viele Plätze wie Buckets.
• Deshalb sind Hinzufügen und Suchen im Durchschnitt schnell, aber ab und zu dauert ein Hinzufügen 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);
HashSet<Seat> sold = new HashSet<Seat>();
sold.Add(seat);

seat.Number = 13;
Console.WriteLine(sold.Contains(seat));
Console.WriteLine(sold.Contains(new Seat(5, 12)));
Console.WriteLine(sold.Count);

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 Eigenschaften eines Schlüssels nur lesbar sind: public int Number { get; }.

Genauer, für Neugierige

• Wie viele Plätze es am Anfang gibt, kannst du im Konstruktor setzen: new Dictionary<string, int>(64). Das Dictionary nimmt eine Primzahl, die nicht kleiner ist (hier 71), und muss mit 64 Schlüsseln unterwegs nicht wachsen. Wann es wächst (wenn sich die Plätze füllen), lässt sich nicht einstellen.
• In .NET ist ein Bucket immer eine Kette: Einen Baum wie in Java gibt es nicht. Gegen viele absichtliche Kollisionen mit Text schützt es, dass der Hashcode von Text bei jedem Lauf anders ist.

Dictionary<string, int> prices = new Dictionary<string, int>(64);
Console.WriteLine(prices.EnsureCapacity(0));
for (int i = 1; i <= 64; i++)
{
    prices["Produkt " + i] = i;
}
Console.WriteLine(prices.EnsureCapacity(0));

Ausgabe

71
71

Ü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 GetHashCode. Nimm für GetHashCode 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 aus, ob die Hashcodes der ersten beiden gleich sind, ob die Hashcodes der ersten und der dritten gleich sind, und wie viele verschiedene Personen in einem HashSet bleiben. Gib die Hashcodes selbst nicht aus: Bei Text ändern sie sich bei jedem Lauf.

Ausgabe

True
False
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
{
    public int X { get; set; }
    public int Y { get; set; }

    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }
}

Ausgabe

Schritte: 8
Verschiedene Zellen: 7

3. Ein Hash einer Datei. Eine Methode HashFileContent(string filePath) liest die Datei und gibt den Hash ihres Inhalts als hexadezimalen Text zurück. GetHashCode() taugt hier nicht: Beim nächsten Lauf hätte dieselbe Datei einen anderen Hashcode. Nimm SHA-256 aus System.Security.Cryptography: Convert.ToHexStringLower(SHA256.HashData(Encoding.UTF8.GetBytes(content))) (Encoding steht in System.Text). Eine Datei schreibst du mit File.WriteAllText(path, text) und liest sie mit File.ReadAllText(path) (in System.IO). 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 Dictionary. Leg ein Array aus 8 Buckets an, jeder eine List 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" 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? Warum taugt GetHashCode() hier nicht? 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 GetHashCode() bei 16, 64 und 1024 Buckets und zähle, wie viele Schlüssel in einem Bucket landen, in dem schon ein Schlüssel ist. Starte das Programm zweimal: Die Zahl ändert sich ein wenig, weil sich der Hashcode von Text ändert.
• 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 GetHashCode mit HashCode.Combine und prüfe die Kartons 30×20×10 und 10×20×30 in einem HashSet.

Test

Teste dich

1. Was macht ein Dictionary mit dem Hashcode eines Schlüssels?

Es berechnet daraus die Nummer des Buckets, in dem es suchtEs speichert ihn statt des SchlüsselsEs vergleicht ihn mit allen anderen Hashcodes

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

Der zweite löscht den erstenDas Dictionary 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.GetHashCode() == b.GetHashCode(), immer

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

True, wenn vorher ein Schlüssel new Seat(5, 12) hineingelegt wurdeEs wirft eine KeyNotFoundExceptionFalse: Das neue Objekt ist ein anderes Objekt, und Equals und GetHashCode aus object schauen nicht auf die Eigenschaften

5. Du überschreibst in Seat Equals, aber nicht GetHashCode. Was passiert?

Das Dictionary berechnet den Hashcode selbst aus EqualsEs kompiliert mit der Warnung CS0659, und das Dictionary findet den Platz trotzdem nichtDas Programm kompiliert nicht

6. Welche Eigenschaft darf sicher in den GetHashCode eines Schlüssels eingehen?

Eine Eigenschaft, die sich nicht ändert (nur get) und die auch Equals vergleichtEine Eigenschaft, die sich ändert, während das Objekt in einem HashSet liegtEine Zufallszahl, die im Konstruktor gewählt wird

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: try, catch und finally · Listen · Stack, Queue und verkettete Liste · Dictionary 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