C++: Eigene Hashfunktion für ungeordnete Container

Der neue C++ Standard bringt neue, ungeordnete Container mit, für die sich eigene Hashfunktionen implementieren lassen, sofern man das möchte. Das habe ich mal ausprobiert und vier Hashfunktionen getestet und auch einen kleinen Benchmarktest dafür gemacht. Zum Einsatz kommen folgende Hashfunktionen:

Als Testgrundlage dient eine 600MB große Textdatei, die englische Wörter bis zur Wortlänge 20 zeilengetrennt beinhaltet. Diese wird dann durch Imbuing eingelesen und alle Wörter werden in eine unordered- Map eingefügt. Diese Wortliste (wordlist.txt) kann in Kürze auch hier heruntergeladen werden.

Es folgt nun die Implementation der drei Hashfunktionen:

Jenkins- Hashfunktion

struct jenkins_hash {
 size_t operator()(const std::wstring &word) const {
  size_t h = 0;
  for(size_t i = 0; i < word.length(); i++) {
   h += word[i];
   h += (h << 10);
   h ^= (h >> 6);
  }
  h += (h << 3);
  h ^= (h >> 11);
  h += (h << 15);
  return h;
 }
};

Bad- Hashfunktion

Eine nicht wirklich gute Hashfunktion soll hier mal als "schlechtes" Beispiel dienen - die bad- Hashfunktion reduziert verschiedene Eingabewert auf den Hashwert, der der Länge des Eingabewertes entspricht. Somit belegen gleichlange Wörter immer ein und denselben Hashwert:

struct bad_hash {
 size_t operator()(const std::wstring &word) const {
  return word.length();
 }
};

Verybad- Hashfunktion

Die verybad- Hashfunktion reduziert verschiedene Eingabewerte auf nur EINEN Hashwert, das wird sich später auf ihre Performanz sehr stark auswirken!

struct bad_hash {
 size_t operator()(const std::wstring &word) const {
  return 0;
 }
};

Eine "Stefan-" Hashfunktion

Hier mal eine kleine, kurze Hashfunktion die ich mir schnell ausgedacht habe:

struct stefan_hash {
 size_t operator()(const std::wstring &word) const {
  size_t h = 0;
  for(size_t i = 0; i < word.length(); i++) {
   h += i * (unsigned char)word[i];
  }
  return h;
 }
};

Der Benchmark

Nun wird gemessen, wie performant die einzelnen Hashfunktionen sind. Der Test erfolgt auf einem 32-bit System, Dual- Core Rechner. Als Eingabedatei dient wie oben erwähnt die wordlist.txt:

stefan@politeia:~$ wc -l wordlist.txt
116767840 wordlist.txt

Es werden also ca. 116 Millionen Wörter eingelesen und in der unordered- Map gespeichert.

Resultat: Jenkins- Hash

Der Jenkins- Hash tritt als erstes an. Es werden drei Durchläufe gemacht:

Erster Durchlauf:

real 0m58.871s
user 0m57.992s
sys 0m0.761s

Zweiter Durchlauf:

real 0m58.934s
user 0m57.966s
sys 0m0.833s

Dritter Durchlauf (schnellster):

real 0m58.840s
user 0m57.925s
sys 0m0.780s

Resultat: Standard- Hashfunktion

Erster Durchlauf (schnellster):

real 0m56.067s
user 0m55.126s
sys 0m0.802s

Zweiter Durchlauf:

real 0m56.837s
user 0m55.931s
sys 0m0.777s

Dritter Durchlauf:

real 0m56.722s
user 0m55.877s
sys 0m0.719s

Resultat: Stefan- Hashfunktion

Nun tritt meine selbstgeschriebene Hashfunktion an.

Erster Durchlauf (schnellster):

real 1m27.143s
user 1m26.142s
sys 0m0.810s

Zweiter Durchlauf:

real 1m27.457s
user 1m26.476s
sys 0m0.801s

Dritter Durchlauf:

real 1m27.584s
user 1m26.519s
sys 0m0.860s

Resultat: Bad- Hashfunktion

Da diese Funktion ziemlich unperformant ist, wurde nur ein Testlauf durchgeführt!

Durchlauf:

real 48m52.841s
user 48m45.438s
sys 0m1.243s

Resultat: Verybad- Hashfunktion

Da diese Funktion noch unperformanter ist, als die Bad- Hashfunktion, wurde hier ebenfalls nur ein Testlauf durchgeführt!

Durchlauf:

real 169m48.203s
user 169m7.659s
sys 0m6.747s

Fazit

Die Jenkins- Hashfunktion kommt bei wide- String ziemlich nah an die Performanz der Standardhashfunktion der ungeordneten Container in C++ heran! Die beiden Funktionen trennen gerade mal 2 Sekunden. Etwas länger dauerte dann meine eigene Hashfunktion, die ca. 30 Sekunden mehr Zeit benötigt, als die Standardhashfunktion. Wirklich weit abgeschlagen die liegen beiden "bad-" Hashfunktionen. Zusammenfassend kann man sagen, dass die ungeordneten Container tolle neue Möglichkeiten bieten, eigene Hashfunktionen zum implementieren (spanned wird es mit eigenen Klassen dann) nur man kann auch sehr, sehr viel "falsch" machen!

Ausblick

Desweiteren bietet sich mit solchen großen Datenmengen auch wunderbar ein Vergleich von dem Durchlaufen solcher (ungeordneten) Containern an. Im nächsten Artikel werde ich einmal die Performanz von Iteratoren, Range- For und Boost For- Each vergleichen!

Downloads

wordlist.txt: Rund 600 MB (!) groß, zeilengetrennte, englische Wörter (bis Wortlänge 20). Zu finden hier.

main.cpp: Das Hauptprogramm, welches alle Hashfunktionen implementiert und die wordlist.txt in die ungeordneten Container einliest. Zu finden hier.

Aktualisierung

Eine neue, aktualisierte Version dieses Artikels befindet sich hier!