Eine Hashmap bezeichnet in der Regel eine statische Datenstruktur in Form eines Feldes. Wollen wir dieses Feld dynamisch befüllen und zwar in einer Art, dass wir Daten später leicht wieder finden, dann müssen wir sie anhand eines Kriteriums sortieren. Bei einer binären Suche auf einem gewöhnlichen Array sortieren wir die Elemente der Größe nach aufsteigend oder absteigend und können in O(log n)-Schritten zu unserem gewünschten Wert kommen, indem wir das Array in Teilfelder zerlegen, jeweils indem wir das mittlere Feld vergleichen. Falls der Wert größer ist, steigend wir ins rechte Teilfeld ab, ansonsten ins linke, angenommen das Feld sei aufsteigend sortiert.

Das Problem bei einer solchen Struktur ist, was passiert bei folgendem Array, wenn wir den Wert 4 hinzufügen wollen?

Der Wert 4 müsste zwischen drei und fünf, was ein Verschieben der restlichen Werte nach sich ziehen würde. Das kann bei großen Feldern sehr lange dauern, weil O(n) Elemente verschoben werden müssen um einen Wert einzufügen. Es kann sinnvoller sein, eine Hashmap zu verwenden.

Eine Hashmap weist den Eingabewerten einen Platz anhand einer mathematischen Modulo-Operation zu. Modulo, was als Operation den ganzzahligen Rest mit einer Ganzzahl errechnet, garantiert, dass kein Wert über das Feld hinaus geschrieben werden kann.

Die Hashfunktion kann dabei beliebig komplex werden. Der Vorteil von Hashmaps ist, dass Werte im best-case innerhalb von O(1), im worst-case in O(n) eingefügt werden können. Nehmen wir ein leeres Array und befüllen es mithilfe der folgenden Hasfunktion: . Die Hashmap sei zehn Elemente lang. Wir fügen die Werte 41, 52, 115, 20 und 32 ein.

Beim Wert 32 fällt auf, dass die eigentliche Position bereits besetzt ist. Es gibt jetzt verschiedene Strategien um mit der Tatsache umzugehen. Einige Caches (das sind schnelle Zwischenspeicher im Prozessor) verwenden bspw. das Prinzip, dass die gespeicherten Daten dann entfernt werden und mit der neuen Cacheline überschrieben werden. Allerdings gehen dabei die vorher gespeicherten Informationen aus dem Cache verloren, d.h. müssten erneut aus dem im Vergleich recht langsamen Arbeitsspeicher nachgeladen werden. Wenn die Daten erneut schnell berechenbar sind, dann kann auch das Vorgehen verwendet werden um eine Auffindbarkeit in O(1) zu garantieren.

Sollen allerdings Daten gespeichert werden, d.h. es dürfen keine Daten verloren gehen, kann entweder am Ende des Feldes Platz reserviert werden um überschüssige Elemente aufzunehmen, oder beim Einfügen wird solange weiter gegangen, bis ein Platz gefunden wird, der noch frei ist. Gibt es einen solchen Platz nicht, muss die Einfügeoperation mit einem Fehler zurückkehren.

In der Praxis sind Hashfunktionen hinreichend komplex und beliebig rechenaufwändig. Für kleine Mengen an Werten lohnt es sich also kaum eine Hashmap einzuführen, sondern oftmals vielmehr eine binäre Suche oder eine verkettete Liste zu verwenden. O(1) als Such-Komplexität klingt zwar an sich sehr gut, allerdings gibt die konstante Laufzeit keine Aussage darüber ab, wie lang die konstante Laufzeit wirklich ist. Wenn einige tausend Zyklen damit verbraucht werden Index eines gesuchten Wertes zu berechnen, es aber nur einige hundert gebraucht hätte eine verkettete Liste zu durchsuchen, lohnt sich die Verwendung einer Liste.