?
Am einfachen Beispiel erklärt:
Angenommen, ich will double-Werte speichern. Ich entwerfe einen einfachen Hash für den erwarteten Wertebereich, etwa
std::size_t hash(double x) {
return static_cast<std::size_t>((x - x_min) / (x_max - x_min) * std::numeric_limits<std::size_t>::max() + .5);
}
was, wenn ich jetzt keinen Programmierfehler gemacht habe, für gleichverteilte Werte wunderbar funktioniert.
Jetzt erwarte ich aber beispielsweise normalverteilte oder gar lognormal verteilte Werte (ich mache beispielsweise eine Monte-Carlo-Simulation über Aktienkurse oder etwas in der Art), und es stellt sich ziemlich schnell heraus, dass diese auf den ersten Blick sehr vernünftige Hashfunktion - die für gleichverteilte Wertmengen in der Tat vernünftig wäre - selbst bei sehr geringem Load-Faktor der Hashtable dauernd kollidiert, und als wäre das nicht genug, dass sie dauernd in der selben Gegend kollidiert und sich die Positionen der Werte entsprechend stark verschieben (jetzt mit closed hashing gedacht, das ist hier ja üblich).
Was man daraus sehen kann, ist, dass es wenig Sinn macht, eine Hashfunktion für double zu definieren und diese überall zu benutzen. Es ist nicht sinnvoll, die Hashfunktion an den Werttyp (im Sinne von Datentyp) zu binden, sondern man muss eine für die erwartete Wertemenge sinnvolle Hashfunktion benutzen. Gleiches gilt für alle anderen Datentypen. Speichere ich beispielsweise Strings, ist bei zufälligen Eingaben eine andere Funktion sinnvoll, als wenn ich die Funktionsnamen einer C-Bibliothek speichere, die als Namensraumersatz alle mit den gleichen n Zeichen anfangen. Speichere ich eine Punktmenge, macht es einen Unterschied, was diese beschreibt.
Es ist nunmal so, dass Hashing nicht ganz trivial ist. Wenn du einfach hinschreiben willst "mach mir etwas, was x nach y mappt", bist du mit std::map besser dran - da hast du Worst-Case-Garantien. Wenn sich das als Performanceproblem entpuppt, können Hashtables die Lösung sein, aber nur, wenn man sich die Arbeit macht, das Hashing vernünftig hinzukriegen.
