HashMap
Autor
Marcus HeldHi,
HashMap? Wie kann HashMap ein Thema für den Newsletter sein? Hold on!
Mir kommt das Thema in den Sinn, weil ich gestern für einen Kunden im Interview saß und mich relativ lange über die HashMap unterhalten habe. Und das Erlebnis war ein kleines Déjà-vu. Vor 2-3 Jahren war ich schwer mit Recruiting beschäftigt. Ich habe in dieser Zeit über 150 technische Interviews durchgeführt. Und aus der Zeit habe ich viel über unsere Branche gelernt. Allen voran, dass es uns an Seniorität fehlt und wir es nicht schaffen, die jungen Entwickler ausreichend zu entwickeln.
Und ich werde auch nicht müde das zu betonen.
Und wenn man sich über die HashMap unterhält, dann wird das deutlich.
Aber mal von Anfang an - falls du kein Entwickler bist und gar nicht weißt, wovon ich rede: Eine HashMap ist eine Map-Implementierung. Das ist eine Datenstruktur, die einen Wert zu einem Schlüssel speichert. Wenn ich also eine Map von übersetzten Wörtern haben möchte, dann kann ich sie z.B. mit einem Paar wie (Butterfly, Schmetterling) befüllen. Und wenn ich später die deutsche Übersetzung von “Butterfly” wissen möchte, dann kann ich die Map danach fragen.
Eine HashMap ist eine spezielle Implementierung, die intern die mathematischen Eigenschaften eines Hashes nutzt, um sehr effizient auf die Daten zuzugreifen. Mit dieser Implementierung ist es problemlos möglich, Maps mit Millionen Einträgen zu verwalten.
Schon diese Grundlage kennen viele Entwickler nicht. Aber es geht noch weiter. Damit eine HashMap richtig funktioniert, muss sie von jedem Objekt, das als Schlüssel benutzt wird, einen unveränderbaren Hash erzeugen können. Also müssen wir verstehen, was ein Hash ist. In Java hat die Klasse, von der alle Objekte erben (Object), eine Standardimplementierung von hashCode()
. Die Standardimplementierung nutzt die Speicheradresse des Objekts als Basis. Damit ist sichergestellt, dass sich der Hash eines Objekts zu seiner Lebenszeit nicht verändern kann.
Für die HashMap ist diese Implementierung aber nicht hilfreich. Ein Objekt, das semantisch gleich ist, bekommt so nämlich nicht automatisch den gleichen Hash. In den meisten Fällen möchte ich aber nicht die Objektreferenz quer durch meine Applikation schleifen, sondern das semantisch gleiche Objekt erzeugen und dann den dazugehörigen Wert aus der HashMap ziehen.
Ist also die Frage, wie implementiere ich hashCode()
korrekt. Aber ich möchte hier nicht ins Detail gehen - es gibt eine super Erklärung in Josh Blochs Klassiker “Effective Java” zu diesem Thema. Wenn du Entwickler bist und ich dich hier schon verloren habe, dann kauf dir das Buch jetzt sofort. Dir fehlen wichtige Grundlagen.
Denn es hört hier ja noch nicht auf. Wenn ich hashCode()
implementiert habe, dann muss ich noch verstehen, dass ein Hash eine mathematische Projektion ist. Das bedeutet, mehrdimensionale Daten werden auf einen einzelnen Wert reduziert. Diese Operation hat die Eigenschaft, dass Informationen verloren gehen. Daraus folgt, dass man aus einem Hash niemals das ursprüngliche Objekt rekonstruieren kann. Und daraus folgt auch, dass es Kollisionen geben kann. Es können also zwei unterschiedliche Objekte den gleichen Hash erzeugen.
Und genau wegen dieser Eigenschaft reicht es nicht, hashCode()
zu implementieren. Man braucht auch eine korrekte Implementierung von equals()
. Ansonsten kann die HashMap nicht feststellen, ob das Objekt wirklich das richtige Objekt ist.
Und equals()
ist auch nicht trivial zu implementieren. Die korrekte Implementierung von equals()
muss (mathematisch) reflexiv, symmetrisch, transitiv und konsistent sein. Dabei darf man natürlich nicht außer Acht lassen, Vererbung zu berücksichtigen.
Und wenn ich das jetzt richtig implementiert habe - dann klappt auch endlich meine HashMap.
Das klingt alles super kompliziert. Und für den Laien ist es das auch. Aber es sind Grundlagen für Softwareentwickler. Ich erwarte, dass Softwareentwickler diese fundamentalen Konzepte verstanden haben.
HashMap-Implementierungen gibt es in allen Sprachen. Überall ist das Konzept gleich. Und sie werden in allen möglichen Libraries benutzt.
Stattdessen erlebe ich, wie man mir von Teamvereinbarungen erzählt, in denen Teams sich gegenseitig verboten haben, HashMaps zu benutzen. “Weil sie nicht funktionieren”.
Die Implementierung von equals()
und hashCode()
wird mit Libraries wie Lombok oder mit Sprachen wie Kotlin trivial. Einfach eine value Klasse nutzen. Aber dann wundern sich die Entwickler, wieso sie komisches Verhalten in ihren Entitäten haben, wenn sie diese als Data-Class implementieren.
Darüber habe ich schon 2021 in meinem (k)lean Kotlin Vortrag gesprochen.
Es bleiben Grundlagen. Diese Verwirrung gäbe es nicht, wenn die Entwickler verstanden hätten, wie eine HashMap funktioniert.
Uns fehlen seniorige Entwickler, die den jungen Entwicklern diese Details erklären können.
Rule the Backend,
~ Marcus