THashMap - einfache Hashmap-Implementation

[3_of_8]

Hallo,

Ich habe mal vor einiger Zeit eine Hashmap gebraucht und mir schnell eine implementiert. Da ich in der DP noch keine Implementation gefunden habe, habe ich mir gedacht, ich könnte die mal noch etwas verbessern und dann hier reinstellen.

Das Prinzip ist recht einfach: Man hat einen String als Schlüssel und einen Pointer als Wert (bei der THashMap). Ich habe gleich noch 2 abgeleitete Klassen mit reingepackt: Eine TObjectHashMap, die TObject-Instanzen verwaltet (und auf Wunsch, ähnlich wie die TObjectList, automatisch freigibt, wenn sie gelöscht werden oder die Hashmap freigegeben wird) und davon abgeleitet eine TStringHashmap, die über eine Wrapper-Klasse Strings enthalten kann.

Als Hash-Funktion verwende ich momentan den Adler32-Algorithmus, der allerdings keine sonderlich guten Ergebnisse zu bringen scheint, bei einem Füllungszustand von 50% sind gerade einmal 35% der Buckets gefüllt und die Kollisionsrate liegt dementsprechend bei etwa einer Kollision auf 3,5 Werte. (knapp 30%)

Wenn jemand einen Verbesserungsvorschlag hat, nur her damit!

[3_of_8]

*hüstel* *push*

[St.Pauli]

Probier es doch mal mit einer kryptographischen Hash-Funktion. Deren Aufgabe ist es, Kollisionen möglichst zu vermeiden.

[3_of_8]

Das wäre äußerst ineffizient. Erstens wäre das deutlich langsamer und zweitens wäre die Effizienz der Hashfunktion mit der geringen Bucket-Zahl nicht wirklich genutzt.

[Dax]

Du könntest immer 4 Chars als ein Integer verXORen, aber ob das so viel mehr bringt als zb MD4?

[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.

[3_of_8]

Interessant. Ich lasse bis jetzt immer den User (bzw. den, der die Hashmap erzeugt) die Bucket-Anzahl bestimmen, habe aber eine Primzahl als Standardgröße verwendet. An automatische Erweiterung habe ich auch schon gedacht. Danke.