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 darauf 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 Funktion wird z.B. wie in unserem Fall der Wert des keys in einen Hashwert umgewandelt. Dieser lässt dich danach nicht wieder zurück umwandeln. Der Hashwert hat dabei immer die gleiche Länge, egal wie groß der Wert des keys vorher war. Außerdem sollte bei unterschiedlichen Werten des Key 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
Null Werte dürfen als key und value gesetzt werden	Null Werte dürfen nicht als key und value gesetzt werden

Wofür brauch man HashMaps

Was passier, wenn eine die Tabelle voll ist.

Ganz voll kann die Tabelle der HashMap nicht werden, außer man ändert den Loadfactor. 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 das kollidierten Werte in der Hashtabelle 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.