Definition Hashmaps Was ist eine Hashmap?

Eine Hashmap ist eine Datentabelle mit einer speziellen Indexstruktur, die ein schnelles Auffinden von Datenobjekten erlaubt. Die Position eines Datenobjekts ist über eine Hashfunktion definiert. In der Hashmap sind die Daten als Schlüssel-Wert-Paare gespeichert. Über den Schlüssel sind die Werte wieder abrufbar. Der Zeitaufwand dafür bleibt konstant und ist unabhängig von der Tabellengröße.

Anbieter zum Thema

Fujitsu Technology Solutions GmbH

SEPPmail - Deutschland GmbH

Cohesity GmbH

Alternative Begriffe für Hashmap sind Hashtabelle, Hash Table oder Streuwerttabelle. Es handelt sich um eine besondere Form einer Datentabelle mit einer speziellen Indexstruktur. Mithilfe von Hashmaps lassen sich Datenobjekte in großen Datenmengen schnell suchen und finden. Eine mathematische Hashfunktion berechnet die Position des Datenobjekts in der Tabelle. Die Daten sind als Schlüssel-Wert-Paare gespeichert. Über den Schlüssel lassen sich die Werte und ihre Position identifizieren und wieder abrufen. Das Durchsuchen vieler Datenobjekte erübrigt sich. Die Besonderheit von Hashmaps ist, dass der Zeitaufwand für das Suchen und Finden im Vergleich zu anderen Indexstrukturen wie Baumstrukturen konstant bleibt und unabhängig von der Tabellengröße ist. Liefert die Hashfunktion keine eindeutigen Ergebnisse, kommt es zu sogenannten Kollisionen, die eine besondere Behandlung erfordern und die Performance der Tabelle negativ beeinträchtigen können. Erste Ideen und Konzepte für Hashmaps entstanden bereits in den 1950er-Jahren. Hashmaps kommen in vielen Bereichen und Anwendungen wie Programmiersprachen, Caches oder Datenbanken zum Einsatz.

Funktionsweise von Hashmaps

In einer Hashmap werden die Daten in einer speziellen Indexstruktur als Schlüssel-Wert-Paare gespeichert. Den Speicherort bestimmt nicht der Schlüssel, sondern der über ein mathematisches Hashverfahren aus dem Schlüssel errechnete Hashwert. Für das Datenobjekt legt dieser Hashwert den Speicherort, auch Bucket genannt, fest. Beim Suchen eines Datenobjekts wird wieder ein Hashwert aus dem Schlüssel berechnet, wodurch der Bucket auffindbar ist, indem das Schlüssel-Wert-Paar gespeichert ist. In einer idealen Hashmap ist jedem Datenobjekt genau ein Bucket zugeteilt. Ist das Hashverfahren nicht eindeutig und liefert für unterschiedliche Ausgangswerte (Schlüssel) gleiche Hashwerte, entstehen Kollisionen. In diesem Fall müssen mehrere Datenobjekte in einem Bucket gespeichert werden. Da Kollisionen eine besondere Behandlung erfordern und die Performance der Datentabelle negativ beeinflussen können, wird versucht, diese zu vermeiden. Je nach Art der Daten und der Anwendung existieren verschiedene Hashverfahren wie verkettetes Hashing, offenes Hashing oder geschlossenes Hashing.

Mögliche Anwendungen von Hashmaps

Hashmaps kommen in vielen verschiedenen Anwendungen zum Einsatz. Sie werden beispielsweise für Caches verwendet, sind Bestandteil der Funktionalität von Programmiersprachen wie C++, PHP oder Java oder bilden die Grundlage für assoziative Arrays, Symboltabellen oder die Indizierung von Datenbanken.

Die Vor- und Nachteile von Hashmaps

Die Vorteile einer Hashmap sind:

• kurze und konstante, von der Datenmenge einer Tabelle unabhängige Zugriffszeiten auf Datenobjekte

• für große Datenmengen und Datentabellen geeignete Indexstruktur

Als Nachteile von Hashmaps lassen sich aufführen:

• es können Kollisionen auftreten, die die Performance der Tabelle und das Zugriffszeitverhalten negativ beeinflussen

• die Datenpositionen sind von außen betrachtet zufällig und unabhängig von möglichen Beziehungen zwischen den Datenobjekten - die Daten scheinen willkürlich in der Tabelle verteilt

• die bei jeder Datenoperation auszuführende Hashfunktion verbraucht CPU-Leistung

(ID:47767660)