Ich glaube, dass es hilfreicher ist, wenn ich HashMaps auf Englisch erkläre.

Was ist eine HashMap?

Eine HashMap ist eine Datenstruktur, die bestimmte Schlüssel auf bestimmte Werte abbilden kann. Die Schlüssel und Werte können alles Mögliche sein. Wenn ich zum Beispiel ein Spiel entwickle, könnte ich jeden Benutzernamen mit einer Freundesliste verknüpfen, die durch eine Liste von Strings repräsentiert wird.

Warum eine HashMap verwenden?

HashMaps sind viel schneller beim Abrufen von Daten als Arrays und verbundene Listen. Ein sortiertes Array kann einen bestimmten Wert in O(log n) mit binärer Suche finden. Eine HashMap kann jedoch in O(1) prüfen, ob sie einen bestimmten Schlüssel enthält. Alle Schlüssel müssen eindeutig sein.

Wie funktionieren HashMaps?

HashMaps verwenden im Hintergrund ein Array. Jedes Element im Array ist eine andere Datenstruktur (normalerweise eine verknüpfte Liste oder ein binärer Suchbaum). Die HashMap verwendet eine Funktion für den Schlüssel, um zu bestimmen, wo der Wert des Schlüssels im Array platziert werden soll. Wenn meine HashMap zum Beispiel Strings akzeptiert, können mögliche Hash-Funktionen sein:

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

Der zurückgegebene Wert bestimmt den Index, mit dem der Wert in das Array kommt.

Aber warte, es gibt ein Problem!

Es ist möglich, dass der zurückgegebene Wert außerhalb der Grenzen des Arrays liegt. Daher sollten wir den zurückgegebenen Wert um die Länge des Arrays modifizieren.

return Math.abs(number%hashMapArray.length);

Kollisionen:

Ist es nicht möglich, dass die Hash-Funktion durch mehrere Schlüssel denselben Index erzeugt? Ja. Wenn wir zum Beispiel die oben gezeigte erste Hash-Funktion in einer Hash-Map von Strings verwenden… werden zwei Strings, die mit demselben Buchstaben beginnen, denselben Array-Index erhalten.

Das nennt man Kollision.

Wie gehen wir mit Kollisionen um?

Eine Technik zur Behandlung von Kollisionen heißt Verkettung. Da jedes Element im Array eine verknüpfte Liste (oder eine ähnliche Datenstruktur) ist, werden mehrere Schlüssel, die denselben Hash-Wert haben, in dieselbe verknüpfte Liste oder denselben „Bucket“ gelegt. Anschließend kann die Hash-Map Werte abrufen, indem sie den Hash-Code mit der Hash-Funktion berechnet und die jeweilige verknüpfte Liste daraufhin durchsucht, ob sie einen Wert mit demselben Schlüssel enthält.

Eine gute Hash-Funktion muss geschrieben werden, um Kollisionen zu vermeiden.

Vorteile der Verkettung:

-Array kann nicht überlaufen

-Daten können leicht entfernt werden

Nachteile der Verkettung:

-Kann Leistungseinbußen erleiden, wenn die Buckets sehr lange verkettete Listen enthalten.

Die Gesamtzahl der Einträge im Verhältnis zur Anzahl der Buckets wird als Lastfaktor bezeichnet. Wenn der Auslastungsfaktor zu niedrig ist, wird viel Platz verschwendet. Ist der Auslastungsfaktor zu hoch, geht der Vorteil des Hashings verloren. Ein guter Kompromiss für den Lastfaktor ist .75

.