HashMap Learning Text (Deutsch)

HashMap

Was sind HashMaps?

Eine HashMap bildet ein key (Schlüssel) auf einen value (Wert) ab und speichert dieses Wertepaar in einer hash table. Dabei wird der key gehasht und der hash code wird als Index benutzt, um zu referenzieren, wo der value in der Tabelle gespeichert wird. Außerdem müssen key und value nicht vom gleichen Datentyp sein, z.B. kann der key den Datentyp String besitzen und der value den Datentyp Integer.

Was ist Hashing?

Hashing ist eine kryptografische Funktion, die sogenannte Hashfunktion, die nur in eine Richtung funktioniert. Durch eine mathematische Hash Funktion wird in unserem Fall der Wert des keys in einen Hashwert umgewandelt. Dieser lässt sich danach nicht wieder in den Ursprungswert umwandeln. Die Hashwerte haben dabei immer die gleiche Länge, egal wie groß der Wert des keys vorher war. Außerdem sollte bei unterschiedlichen Werten des Keys auch immer ein unterschiedlicher Hashwert rauskommen und bei gleichen Werten ein gleicher Hashwert.

Wo ist der unterschied zwischen HashMap und Hashtable?

HashMap	Hashtable
Nicht Thread sicher	Thread sicher
Bessere Performance	Langsamere Performance
Null Werte dürfen als key und value gesetzt werden	Null Werte dürfen nicht als key und value gesetzt werden

Wofür braucht man HashMaps?

Was passiert, wenn eine die Tabelle voll ist.

Ganz voll kann die Tabelle der HashMap nicht werden, wenn der Loadfactor richtig setzt ist (default 0.75) . Denn der Loadfactor gibt an wie voll die Tabelle werden kann, bevor die Tabelle automatisch erweitert wird. Dann wird die hash table neu gehasht, d. h. die interne Datenstruktur wird neu gebildet. Die Neubildung soll die Tabelle ungefähr verdoppeln.

Was passiert, wenn zwei Werte im gleichen Index gespeichert werden sollen

Wenn das passiert kommt es zu einer Kollision. Als nächster muss diese Kollison aufgelöst werden. Zum Auflösen gibt es zwei verschiedene Strategien Separate Chaining und Open Addressing

Separate Chaining

Bei Separate Chaining werden die kollidierten Objekte verkettet durch eine verkettete Liste.

Open Addressing

Open Addressing bezeichnet das Verfahren indem bei einer Kollision die Werte an freie Stellen verschoben werden. Dabei unterscheidet man zwischen linear probing, quadratic probing und double Hashing.

Linear Probing

Hierbei wird in einem konstanten Intervall nach einer freien Stelle gesucht. Meistens nimmt man für die Intervall größe 1.

Quadratic probing

Das Intervall wird nach jedem erfolglosen Suchschritt quadriert.

Double Hashing

Eine weitere Hashfunktion liefert das Intervall.