HashMap - eine der am häufigsten verwendeten Datenstrukturen in der Programmiersprache Java. Es ist eine Implementierung eines assoziativen Arrays, das auf dem Prinzip einer Hashtabelle basiert. Im Wesentlichen handelt es sich um eine Sammlung, mit der Sie Schlüssel-Wert-Paare speichern können, bei denen jeder Schlüssel eindeutig ist.
Die Grundidee hinter der Verwendung von hashmap besteht darin, schnell auf Elemente nach Schlüssel zuzugreifen. Anstatt die gesamte Sammlung auf der Suche nach dem gewünschten Element zu durchsuchen, verwendet hashmap eine Hash-Funktion, um das Backet zu finden, in dem es sich befinden soll. Die Hash-Funktion nimmt einen Schlüssel als Eingabe an und gibt den Index des Arrays zurück, in dem dieser Schlüssel gespeichert werden soll.
Wenn Sie Elemente in eine hashmap einfügen, erhält jedes Element seinen eindeutigen Hash-Code. Wenn zwei Elemente die gleichen Schlüssel haben, sind die Hashcodes für sie ebenfalls gleich. Aber was ist, wenn für zwei Elemente mit unterschiedlichen Schlüsseln der gleiche Hash-Code erhalten wird? Dies wird als Kollision bezeichnet. In diesem Fall verwendet die HashMap eine andere Datenstruktur, eine verknüpfte Liste, um alle Elemente mit denselben Hashcodes in einem einzigen Bucket zu speichern. Dank verknüpfter Listen kann hashmap mehrere Elemente mit denselben Hashcodes speichern und den gewünschten Schlüssel schnell finden.
Die HashMap-Klasse stellt Methoden zum Hinzufügen, Entfernen und Suchen von Elementen bereit. Es bietet auch eine Reihe von Methoden für die Interaktion mit Daten, z. B. das Abrufen der Sammlungsgröße und das Überprüfen des Vorhandenseins eines Elements. Außerdem ist eine HashMap eine Kombination aus Array und einer verknüpften Liste, die es ermöglicht, Elemente in konstanter Zeit hinzuzufügen, zu löschen und zu finden.
Die Funktionsweise von Hashmap in Java
Wenn ein Element zur hashmap hinzugefügt wird, wird es in eine der Zellen des inneren Arrays eingefügt. Der Hash-Algorithmus berechnet den Hash-Code des Schlüssels und wandelt ihn in den Zellenindex um. Wenn bereits ein Element in dieser Zelle vorhanden ist, verwendet die hashmap eine Verkettungsmethode, bei der das hinzuzufügende Element der verknüpften Liste mit anderen Elementen hinzugefügt wird. Wenn keine Elemente in einer Zelle vorhanden sind, wird das Element direkt zur Zelle hinzugefügt.
Bei der Suche nach einem Element in einer Hashmap berechnet der Hashing-Algorithmus den Hash-Code des Schlüssels und verwendet ihn, um den Index der Zelle zu bestimmen. Anschließend wird in der Themenliste nach Elementen gesucht. Wenn kein Element gefunden wird, wird null zurückgegeben.
- Schnell hinzufügen und nach Elementen suchen.
- Flexibilität bei der Verwendung verschiedener Schlüsseltypen.
- Fähigkeit, große Datenmengen zu speichern.
- Mögliche Kollision bei Verwendung desselben Hash-Codes.
- Unerwünschte Verwendung großer Speichermengen.
Die Größe des internen Hashmap-Arrays kann sich dynamisch ändern, abhängig von der Anzahl der Elemente und dem Ausfüllungsanteil. Dies ermöglicht eine hohe Effizienz beim Hinzufügen und Suchen von Elementen.
Hashmap in Java ist ein leistungsfähiges Werkzeug, das weit verbreitet ist, um verschiedene Aufgaben zu lösen, die einen schnellen und effizienten Datenzugriff erfordern. Es ist wichtig, seine Merkmale zu berücksichtigen und eine geeignete Implementierung für eine bestimmte Aufgabe zu wählen.
Funktionsprinzip von hashmap
Wenn ein Element zur HashMap hinzugefügt wird, berechnet es den Hash-Code des Schlüssels und bestimmt den Index der Hashtabelle, in der der Wert gespeichert werden soll. Wenn bereits ein anderer Wert in diesem Index vorhanden ist, tritt eine Kollision auf und die Elemente werden in die Themenliste eingefügt. Bei Kollisionen werden Elemente am Anfang der Liste hinzugefügt, sodass mehrere Werte mit demselben Hashcode in einer HashMap gespeichert werden können.
Wenn Sie den Wert nach einem Schlüssel abrufen, berechnet HashMap zuerst den Hash-Code des Schlüssels und findet den entsprechenden Index in der Hashtabelle. Es überprüft dann die Werte in der Liste, die diesem Index zugeordnet ist, und gibt den Wert zurück, der dem Schlüssel entspricht.
Um sicherzustellen, dass die Werte schnell abgerufen werden, verwenden Hash-Maps in Java Instanzen von Schlüsselklassen, die die Methoden hashCode() und equals() korrekt implementieren müssen. Dadurch kann HashMap Hashcodes effizient berechnen und Schlüssel vergleichen, wenn sie nach Werten suchen.
Hashing von Schlüsseln in einer hashmap
Wenn Sie ein Element in eine HashMap einfügen, wird zuerst der Hash-Code des Schlüssels mithilfe der hashCode() -Methode ausgewertet. Dieser Hash-Code wird dann mit einer Hashfunktion konvertiert, um den tatsächlichen Index des inneren Arrays zu erhalten, in dem der Wert gespeichert wird.
Der Hashing-Prozess beschleunigt die Zugriffszeit für Elemente erheblich, da Sie die Position, an der sie gespeichert werden sollen, schnell berechnen können. Es kann jedoch eine Situation geben, in der zwei verschiedene Schlüssel denselben Hash-Code haben können, was als Kollision bezeichnet wird. In diesem Fall werden die Elemente mit Kollision in einem einzigen Bucket (Bleistift, Eimer) gespeichert, der Teil des internen Arrays der HashMap ist.
Wenn ein Element in einer HashMap nach seinem Schlüssel gesucht wird, berechnet es zuerst den Hash-Code des Schlüssels und findet den Bucket-Index, in dem sich das Element befinden soll. Es geht dann durch diesen Bucket und vergleicht die Schlüssel der Elemente mit der equals() -Methode, bis ein Element mit dem entsprechenden Schlüssel gefunden wird oder das Ende des Bucket erreicht ist.
Eine gute Hash-Funktion sollte die Schlüssel gleichmäßig über den gesamten Bereich der Hash-Codes verteilen, um die Anzahl der Kollisionen zu reduzieren. Wenn die Hash-Funktion die Schlüssel nicht gut verteilt, kann dies zu einer Verschlechterung der HashMap-Leistung und zu einer längeren Laufzeit für das Hinzufügen, Suchen oder Löschen von Elementen führen.
Kollisionen und Problemlösung
Wenn eine Kollision auftritt, sucht die Hashmap nach der nächsten leeren Zelle im Array, um das Element zu speichern. Dieser Ansatz kann zu Leistungsproblemen führen, insbesondere bei einer großen Anzahl von Elementen und einer engen Auffüllung des Arrays.
Um Probleme mit Kollisionen zu lösen, verwendet Java die Verkettungsmethode (engl. chaining). Anstatt Elemente in einem Array zu speichern, enthält jede Zelle im Array eine zusammenhängende Liste von Elementen mit denselben Hashes. Dadurch können Sie viele Elemente effizient mit demselben Hash-Code speichern.
Wenn ein neues Element hinzugefügt wird, prüft die Hashmap zuerst, ob bereits ein Element mit demselben Schlüssel vorhanden ist. Falls vorhanden, wird es am Ende der verknüpften Liste hinzugefügt. Wenn nicht, wird ein neues Element erstellt und der verknüpften Liste der entsprechenden Zelle hinzugefügt.
Wenn Sie nach einem Element mit einem bestimmten Schlüssel suchen, berechnet die Hashmap zuerst den Hash-Code des Schlüssels und findet die entsprechende Arrayzelle. Anschließend wird in der verknüpften Zellenliste nach dem gewünschten Element gesucht.
Die Kettenmethode löst das Problem von Kollisionen, aber bei schlecht entworfenen Hash-Funktionen oder einer falschen Array-Größe können Kollisionen dennoch auftreten und die Leistung von Hashmap beeinträchtigen. Daher ist es wichtig, die richtigen Hash-Funktionen und Array-Größen auszuwählen und die Möglichkeit zu berücksichtigen, die Größe des Arrays bei Bedarf zu erhöhen.
- Kann Elemente schnell und effizient anhand eines Schlüssels finden, wenn es wenige Kollisionen gibt und die Liste der Elemente in der Zelle klein ist
- Ermöglicht das Hinzufügen und Entfernen von Elementen, ohne die gesamte Struktur neu zu erstellen
- Bei Kollisionen kann es notwendig sein, nach einem Element in einer verknüpften Liste zu suchen, was zusätzliche Zeit in Anspruch nimmt
- Die falsche Wahl einer Hash-Funktion oder Array-Größe kann sich negativ auf die Leistung auswirken
