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;
 }
};

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;
 }
};

Eine modifizierte "Stefan2-" Hashfunktion

Hier mal eine modifizierte Version aus dem Kapitel "Algorithms and Data Structures" aus "The Practice of Programming" von Brian W. Kernighan und Rob Pike:

struct stefan2_hash {
 size_t operator()(const std::wstring &word) const {
  size_t h = 0;
  const wchar_t * s_ptr = word.c_str();
  for (const wchar_t * p = s_ptr; *p != L'\0'; ++p) {
   h = 31 * h + (unsigned wchar_t)*p;
  }
  return h;
 }
};

Der Benchmark

Nun wird gemessen, wie performant die einzelnen Hashfunktionen sind. Der Test erfolgt in einer virtuellen Maschine (KVM) -> AMD FX-8150, zugewiesen 4GB RAM, vier Kerne. 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. -O als Optimierungsflag wurde beim Kompilieren NICHT gesetzt!

Resultat: Jenkins- Hash

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

Erster Durchlauf (schnellster):

real 0m29.072s
user 0m28.887s
sys 0m0.174s

Zweiter Durchlauf:

real 0m29.753s
user 0m29.562s
sys 0m0.183s

Dritter Durchlauf:

real 0m29.315s
user 0m29.122s
sys 0m0.185s

Resultat: Standard- Hashfunktion

Erster Durchlauf (schnellster):

real 0m25.912s
user 0m25.677s
sys 0m0.172s

Zweiter Durchlauf:

real 0m26.131s
user 0m25.877s
sys 0m0.180s

Dritter Durchlauf:

real 0m26.097s
user 0m25.833s
sys 0m0.196s

Resultat: Stefan- Hashfunktion

Nun tritt meine selbstgeschriebene Hashfunktion an.

Erster Durchlauf:

real 0m54.855s
user 0m54.541s
sys 0m0.204s

Zweiter Durchlauf:

real 0m54.796s
user 0m54.412s
sys 0m0.247s

Dritter Durchlauf (schnellster):

real 0m54.742s
user 0m54.539s
sys 0m0.189s

Resultat: Stefan2- Hashfunktion

Die leicht modifizierte Hashfunktion aus Kernighan´s "The Practice of Programming"!

Erster Durchlauf:

real 0m25.396s
user 0m25.179s
sys 0m0.207s

Zweiter Durchlauf:

real 0m25.625s
user 0m25.424s
sys 0m0.180s

Dritter Durchlauf (schnellster):

real 0m25.230s
user 0m25.017s
sys 0m0.199s

Fazit

Für die Speicherung von wide-strings ist die modifizierte Version aus "The practice of Programming" am schnellsten und hängt die Standardhashfunktion der unordered_map ab. Etwas dahinter ist die "one-at-a-time" Jenkins-Hashfunktion. Meine "eben" hingeschriebene Hashfunktion liegt deutlich abgeschnitten auf dem letzten Platz. Am besten vertraut man auf die Standardhashfunktion der STL, da kann man eigentlich nichts falsch machen. Sofern man vorhat, eine eigene Funktion zu schreiben, sollte man diese natürlich auch ausführlich testen -> auch mit großen Datenmengen.

Dieser Artikel wurde am 23.12.2012 aktualisiert: Es wurden alte, schlechte Hashfunktionen herausgenommen, und die Benchmarks auf einer leistungsfähigeren Maschine durchlaufen + die Resultate ebenfalls aktualisiert. Sollte ich noch performantere Hashfunktionen für diesen Zweck finden, werden diese hier beschrieben! Der alte Artikel befindet sich hier.

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.