Swipe um das Menü anzuzeigen

Schauen wir uns nun die Klasse an, 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 müssen Sie 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 folgendermaßen 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 Erzeugung dieser Zahl definiert wird. Erstellen wir eine Testklasse User und überschreiben die Hashcode-Methode für sie.

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 wollen wir herausfinden, 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 der Buckets in der HashMap ist. '&' ist eine bitweise AND-Operation, was auch Low-Level-Programmierung ist; auf die Details gehen wir hier nicht ein.

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.

Sehen wir uns eine Illustration dazu 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 mithilfe des neuen Werts von n in der Formel auf die neuen Buckets verteilt.

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

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 Hashcode haben?

War alles klar?

Danke für Ihr Feedback!

Abschnitt 1. Kapitel 14

Fragen Sie AI

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

Abschnitt 1. Kapitel 14

Arbeiten mit HashMap in Java

Hash-Code

HashMap

Kollision

Wie geht HashMap mit Kollisionen um?

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 Hashcode haben?

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