Werfen wir nun einen genaueren Blick auf die Klasse, die das Map-Interface implementiert — HashMap.

Diese Klasse wird häufig verwendet, wenn von Maps die Rede ist. Sie haben bereits die Möglichkeit gehabt, mit dieser Klasse zu arbeiten und ihre Methoden zu untersuchen. Aber lassen Sie uns herausfinden, wie diese Klasse tatsächlich funktioniert.

Zunächst ist es wichtig zu verstehen, was ein Hash-Code ist, da dieser intern in einer HashMap verwendet wird.

Hash-Code

Jedes Objekt besitzt einen eigenen Hash-Code, der mit der Methode Object der Klasse hashCode() abgerufen werden kann. Sehen wir uns ein Beispiel an:

Main.java


              123456789
            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Wie Sie sehen können, hat das String-Objekt mit den Daten "Hello World!" einen Hash-Code von "-969099747". Die Methode, die bestimmt, welcher Hash-Code genau in der String-Klasse überschrieben wird, sieht wie folgt aus:

Main.java


              1234567
            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

Das String-Objekt wird mit der Methode getBytes() in ein Byte-Array zerlegt, woraufhin jedes Byte verarbeitet und zum Hashcode hinzugefügt wird. Auf diese Weise wird der Hashcode maximal eindeutig, was dem Programm hilft, dieses Objekt zu identifizieren.

Für Objekte von benutzerdefinierten Klassen kann der Hashcode ebenfalls überschrieben werden, indem eine eindeutige Methode zur Ermittlung dieser Zahl definiert wird. Erstellen wir eine Testklasse User und überschreiben die Hashcode-Methode dafür.

Main.java


              12345678910111213141516171819202122232425262728293031
            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

In der Klasse User gibt es 2 Attribute, die ich in der Methode hashCode() verwendet habe. Ich habe zufällige Operationen in der Methode hashCode() gewählt, um eine maximal zufällige Zahl zu erhalten, die für jedes User-Objekt eindeutig ist.

Genau das ist der Hashcode. Nun sehen wir uns an, wie er in einer HashMap verwendet wird.

HashMap

Ein HashMap kann als Array von Buckets visualisiert werden. Ein Bucket ist eine Liste, in der ein Element gespeichert wird. Zu Beginn verfügt die HashMap über 16 Buckets, was der DEFAULT_INITIAL_CAPACITY entspricht.

Wenn Sie ein Element mit der Methode HashMap in die put() einfügen, muss die HashMap bestimmen, in welchen spezifischen Bucket dieses Element gelegt werden soll. Dies geschieht mit einer einfachen Formel: keyValue.hashCode() & (n - 1), wobei n die Größe des Arrays von Buckets in der HashMap ist. '&' ist eine bitweise AND-Operation, die ebenfalls zur Low-Level-Programmierung gehört, auf deren Details wir hier nicht eingehen.

Es ist wichtig zu verstehen, dass die HashMap den Hash-Code des Schlüssels verwendet, um den passenden Bucket dafür zu finden. Daher ist es entscheidend, einen möglichst einzigartigen Hash-Code zu erstellen, um Kollisionen zu vermeiden.

Kollision

Egal wie einzigartig ein Hash-Code ist, es kann dennoch vorkommen, dass die HashMap für zwei Elemente denselben Bucket berechnet. In solchen Fällen tritt eine Kollision auf. Einfach ausgedrückt ist eine Kollision eine Situation, in der zwei oder mehr Elemente im selben Bucket landen. Sie werden dort als SinglyLinkedList gespeichert, die Sie zuvor implementiert haben.

Schauen wir uns eine Illustration an:

Kollisionen sind ungünstig, da sie die Optimierung beeinträchtigen. Wenn Sie sich diese Tabelle ansehen, werden Sie feststellen, dass im besten Fall die HashMap eine konstante algorithmische Komplexität aufweist, während sie im schlechtesten Fall linear ist. Diese lineare algorithmische Komplexität entsteht durch erhebliche Kollisionen. Daher empfehlen Programmierer, Schlüssel mit möglichst einzigartigen Hash-Codes zu verwenden, um Kollisionen zu vermeiden.

Wie geht HashMap mit Kollisionen um?

HashMap behandelt Kollisionen ebenfalls durch das ständige Vergrößern des Bucket-Arrays. Wenn die Anzahl der Elemente 75 % der Größe des Bucket-Arrays erreicht, löst HashMap eine Vergrößerung aus, indem die Größe des Bucket-Arrays verdoppelt wird. Anschließend werden die Elemente mit dem neuen Wert von n in der Formel auf die neuen Buckets verteilt.

Daher ist HashMap eine hochoptimierte Datenstruktur und wird häufig als primäre Implementierung des Map-Interfaces verwendet.

Warum ist dieses Wissen wichtig?

Dies ist eine theoretische Grundlage der Programmierung auf niedriger Ebene, die wichtig ist, weil bei der Arbeit mit großen Datenmengen Datenstrukturen die Leistung einer Anwendung erheblich beeinflussen können. Dies geschieht, wenn diese Datenstrukturen falsch verwendet werden.

Eine falsche Verwendung von Datenstrukturen tritt auf, weil Programmierer nicht verstehen, wie diese Datenstrukturen funktionieren. Schließlich möchten Sie doch ein guter Programmierer werden, oder?

Außerdem werden Fragen zu Datenstrukturen häufig in Vorstellungsgesprächen gestellt.

Wenn Sie tiefer in die Funktionsweise von HashMap eintauchen möchten, können Sie die Java-Dokumentation in IntelliJ IDEA konsultieren.

In IntelliJ IDEA mit gedrückter Ctrl-Taste (Windows/Linux) oder Command-Taste (macOS) auf den Klassennamen klicken, um zur Definition zu gelangen und alle verfügbaren Methoden anzuzeigen.

1. Welche der folgenden Implementierungen verwendet eine Hashtabelle zur Speicherung von Schlüssel-Wert-Paaren?

2. Was passiert in einer `HashMap`, wenn zwei Schlüssel denselben Hash-Code haben?

War alles klar?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 2

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Swipe um das Menü anzuzeigen

Werfen wir nun einen genaueren Blick auf die Klasse, die das Map-Interface implementiert — HashMap.

Zunächst ist es wichtig zu verstehen, was ein Hash-Code ist, da dieser intern in einer HashMap verwendet wird.

Hash-Code

Jedes Objekt besitzt einen eigenen Hash-Code, der mit der Methode Object der Klasse hashCode() abgerufen werden kann. Sehen wir uns ein Beispiel an:

Main.java


              123456789
            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Main.java


              1234567
            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

Main.java


              12345678910111213141516171819202122232425262728293031
            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

Genau das ist der Hashcode. Nun sehen wir uns an, wie er in einer HashMap verwendet wird.

HashMap

Kollision

Schauen wir uns eine Illustration an:

Wie geht HashMap mit Kollisionen um?

Daher ist HashMap eine hochoptimierte Datenstruktur und wird häufig als primäre Implementierung des Map-Interfaces verwendet.

Warum ist dieses Wissen wichtig?

Außerdem werden Fragen zu Datenstrukturen häufig in Vorstellungsgesprächen gestellt.

Wenn Sie tiefer in die Funktionsweise von HashMap eintauchen möchten, können Sie die Java-Dokumentation in IntelliJ IDEA konsultieren.

1. Welche der folgenden Implementierungen verwendet eine Hashtabelle zur Speicherung von Schlüssel-Wert-Paaren?

2. Was passiert in einer `HashMap`, wenn zwei Schlüssel denselben Hash-Code haben?

War alles klar?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 2

Arbeiten mit HashMap in Java

Hash-Code

HashMap

Kollision

Wie geht HashMap mit Kollisionen um?

Warum ist dieses Wissen wichtig?

1. Welche der folgenden Implementierungen verwendet eine Hashtabelle zur Speicherung von Schlüssel-Wert-Paaren?

2. Was passiert in einer `HashMap`, wenn zwei Schlüssel denselben Hash-Code haben?

Arbeiten mit HashMap in Java

Hash-Code

HashMap

Kollision

Wie geht HashMap mit Kollisionen um?

Warum ist dieses Wissen wichtig?

1. Welche der folgenden Implementierungen verwendet eine Hashtabelle zur Speicherung von Schlüssel-Wert-Paaren?

2. Was passiert in einer `HashMap`, wenn zwei Schlüssel denselben Hash-Code haben?

Arbeiten mit HashMap in Java

Hash-Code

HashMap

Kollision

Wie geht HashMap mit Kollisionen um?

Warum ist dieses Wissen wichtig?

1. Welche der folgenden Implementierungen verwendet eine Hashtabelle zur Speicherung von Schlüssel-Wert-Paaren?

2. Was passiert in einer HashMap, wenn zwei Schlüssel denselben Hash-Code haben?

Arbeiten mit HashMap in Java

Hash-Code

HashMap

Kollision

Wie geht HashMap mit Kollisionen um?

Warum ist dieses Wissen wichtig?

1. Welche der folgenden Implementierungen verwendet eine Hashtabelle zur Speicherung von Schlüssel-Wert-Paaren?

2. Was passiert in einer HashMap, wenn zwei Schlüssel denselben Hash-Code haben?

2. Was passiert in einer `HashMap`, wenn zwei Schlüssel denselben Hash-Code haben?

2. Was passiert in einer `HashMap`, wenn zwei Schlüssel denselben Hash-Code haben?