Schlecht, wenn's kracht

std::unordered_set benötigt für die Speicherung und das Wiederfinden von Objekten zwei Operationen: die Berechnung des Hashcodes und den Vergleich auf Gleichheit. Speziell bei ersterem sollte man bei der Implementierung aufpassen.

Video

Quelltext

#include <iostream>
#include <unordered_set>
#include <boost/date_time/posix_time/posix_time.hpp>
 
struct StupidHash
{
  std::size_t operator()(int) const
  {
    return 0;
  }
};

int main()
{
  int retries = 1000;
   
  for (int max = 1; max <= 16384;  max *= 2) {
    std::unordered_set<int> us;
    std::unordered_set<int, StupidHash> sus;
     
    std::cerr << "@" << max << " Elemente:\n";
     
    for (int i = 0; i < max; ++i) {
      us.insert(i);
      sus.insert(i);
    }
     
    boost::posix_time::ptime before1 = boost::posix_time::microsec_clock::local_time();
    for (int j = 0; j < retries; ++j) {
      int x = *us.find(j*max/retries);
    }
    boost::posix_time::ptime after1 = boost::posix_time::microsec_clock::local_time();
    std::cerr << "   sinnvoll: ø" <<
         static_cast<double>((after1-before1).total_microseconds())/retries <<
         " µs pro Suche\n";
 
    boost::posix_time::ptime before2 = boost::posix_time::microsec_clock::local_time();
    for (int j = 0; j < retries; ++j) {
      int x = *sus.find(j*max/retries);
    }
    boost::posix_time::ptime after2 = boost::posix_time::microsec_clock::local_time();
    std::cerr << "   dämlich: ø" <<
         static_cast<double>((after2-before2).total_microseconds())/retries <<
         " µs pro Suche\n";
  }
}

Erklärung

std::unordered_set bietet zwei Templateparameter, um eine Konfiguration des Hashverfahrens und des Vergleichs auf Gleichheit zu ermöglichen. Ähnlich wie bei std::set gibt es sinnvolle Vorbelegungen für den Vergleich auf Gleichheit. Beim Hashverfahren sieht das anders aus: das eigene Datentypen standardmäßig keine Methode zum Hashing bereitstellen (anders, als der operator< für den von std::set benötigten Vergleich), muss man quasi immer eine entsprechende Implementierung angeben. Dafür gibt es wieder zwei Möglichkeiten: entweder global gültig durch eine Spezialisierung von std::hash<> für den entsprechenden Datentyp oder lokal durch Angabe eines entsprechenden Funktionstyps. Die Signatur des passenden operator() ist immer gleich: er bekommt ein Element des zu hashenden Datentyps und liefert in einem std::size_t den berechneten Index zurück.

Das Beispiel zeigt, dass dabei einiges schiefgehen kann. Hash-Datenstrukturen arbeiten mit zwei Teilalgorithmen zum Auffinden von Elementen: Hashing und Sondieren. Hashing ist in O(1): man berechnet den Code und schaut am entsprechenden Index in der Datenstruktur nach. Dummerweise kommt es beim Hashing zwangsläufig zu Kollisionen: Abbildungen von verschiedenen Elementen auf den selben Hashcode. Dafür nutzt die Datenstruktur dann das Sondieren: Schritt für Schritt werden benachbarte Zellen des Hashcodes abgesucht, um das passende Element zu finden (oder eine freie Zelle beim Schreiben). Dieser Anteil ist in O(n) (deswegen auch lineares Sondieren genannt). Erzeugt ein Hashverfahren also besonders viele Kollisionen, so ist die Datenstruktur besonders häufig zum Ausweichen auf das Sondieren gezwungen und ihr Laufzeitverhalten ist stark beeinträchtigt. Der Extremfall ist das StupidHash-Verfahren im Beispiel oben: es erzeugt nur Kollisionen, da es den gesamten Eingaberaum auf einen Index abbildet. Hier wird aus der eigentlich effizienten O(1)-Datenstruktur plötzlich ein O(n).

Implementiert man also std::hash<> (oder eine eigene Struktur) für einen Datentyp, dann sollte man sich über die Verteilung der zu speichernden Daten einigermaßen im Klaren sein, um solche Probleme zu vermeiden. Ggf. muss man eine Implementierung testen und messen.