THashMap - einfache Hashmap-Implementation

[alzaimar]

In meiner Implementierung verwende ich ELF-Hashing. Vorher hatte ich (wegen Faulheit) ein CRC-32 Hash eingebaut (lag bei mir rum), der aber ineffizient ist. Mit ELF habe ich die besten Erfahrungen gemacht. Ich hatte einige Funktionen ergoogelt, verschiedene Hashmaps gebastelt und den schnellsten Kandidaten benutzt.

Meine Implementierung (bei der Du dich ggf gerne bedienen kannst) verwendet eine Prim-Mapgröße und verdoppelt die Größe auf die nächsthöhere Primzahl, wenn der Füllstand 80% beträgt. Damit habe ich für meinen Anwendungsfall (Codegenerator und Compiler) ausreichend gute Ergebnisse erzielt. Einige Geeks schwören auf eine Vergrößerung um 1,67 (goldener Schnitt), oder haben sogar 'magische Map-Größen' ermittelt. Das ist imho Quatsch, denn es hat bei mir keine Verbesserung gebracht: Eher das Gegenteil. Einzig die Wahl der nächsten Mapgröße (eine Primzahl) scheint Einfluss auf die Performance zu haben: Es gibt im Zusammenspiel mit der Hashfunktion bestimmte Mapgrößen, die bezüglich der Kollisionsanzahl deutlich schlechter sind, als die nächsthöhere/niedrigere. Ich habe jedoch keine Möglichkeit gefunden, dies zu optimieren. Ergo ist es 'Pech', wenn bei bestimmten Schlüsseln und Mapgrößen die Performance um z.T. mehr als 10% einbricht: Ein Beinbruch ist es jedoch nicht, denn schnell genug sind die Dinger allemal.

Wenn deine Hashmap beliebige Strings als Schlüssel akzeptiert (die also keine besonderen Syntax genügen), kann es eine optimale Hashfunktion nicht geben. CRC32/ADLER wird Schlüssel der Form 'S1','S2' etc. vermutlich am besten hashen, weil sie genau dafür konzipiert wurden: Die Hashwerte ähnlicher Informationen weit zu streuen. Wie sich diese Verfahren bei zufälligen Strings verhalten, ist aber nicht vorhersehbar. Insofern habe ich mich auf schnelle und im Compilerbau übliche Hashfunktionen konzentriert und eine möglichst Performante gesucht.

Weiterhin gibt es eine Hashmap bei den Jedis (JCL), die Du dir mal anschauen kannst. Sie verwenden einen interessanten Hashing-Algorithmus (PJW), der bei mir dem ELF knapp unterlegen war. Letztendlich würde ich mit einem Strategy-Muster die Funktion ermitteln, die für deinen Anwendungsfall die besten Ergebnisse erzielt.