Hash 4 Integers



  • Ich hatte hash_combine irgendwie wieder verdrängt, weil ich zwischenzeitlich noch ein anderes Problem hatte.
    Ich habe es nun einmal implementiert und es ist vermutlich tatsächlich schneller als crc16, wobei ich noch genauere Tests durchführen muss.
    Was mich sehr überrascht ist, dass ich 0% Kollisionen hatte bei 70000 Elementen. Also eine beträchtliche Steigerung im Vergleich zu CRC16. Einziger Nachteil daran ist natürlich die zusätzliche Dependency, da das Projekt ansonsten bis jetzt boost-frei war. Aber das ist vermutlich verkraftbar. Was ich noch überlege, ist, ob ich nicht das Array als Key entferne oder vllt. auch zwei Hashes in unterschiedlicher Reihenfolge nehme als Sicherheit, wenn ich in weiteren Tests weiterhin auch bei 100000 Elementen 0% Kollisionen habe. Könnte vllt. noch einmal einen kleinen Performanceschub geben, wobei es bereits so eine Verbesserung von min. 70% darstellt (wie gesagt: um das definitiv sagen zu können sind weitere Tests notwendig).



  • Du brauchst dafür boost nicht einzubinden. Schau dir den Code von hash_combine an, das sind 1-2 Zeilen.



  • Und noch ein kleiner Tip zu "schau dir den Code an": step einfach in Debugger rein. Erleichtert das Finden des Codes ungemein. Speziell bei so Sachen wie boost::hash_value (welches von boost::hash_combine aufgerufen wird) wo es nur ca. 1 Mio. Overloads gibt die dann mit diversen SFINAE Hilfsklassen enabled/disabled werden und...

    OK, gibt natürlich schlimmeres als boost::hash_value, aber übersichtlich ist es auf jeden Fall nicht.



  • Ja, ich habe mir den Code bereits angesehen und der sollte tatsächlich ziemlich einfach zu kopieren sein. Weiß da jemand wie das mit Copyright aussieht?
    Ich bin gerade aber sowieso an anderer Stelle am Überlegen, boost zu verwenden, wo es nicht so einfach herauskopierbar wäre. Muss ich mir beides noch einmal ansehen.
    Danke auf jeden Fall für eure Hilfe.



  • @unterfliege sagte in Hash 4 Integers:

    Was ich noch überlege, ist, ob ich nicht das Array als Key entferne oder vllt. auch zwei Hashes in unterschiedlicher Reihenfolge nehme als Sicherheit

    Du hast irgendwie komische Überlegungen. Du brauchst das Array gar nicht, warum hast du es denn da genutzt? Warum brauchst du irgendwas "als Sicherheit"?



  • @tggc Wenn der Hash gut genug wäre und auf mehrere 100000 Arrays keine Kollisionen liefert, wäre der Geschwindigkeitsvorteil eventuell die Gefahr einer Kollision wert.
    Aber natürlich brauche ich am Anfang schon die Pointer im Array, aber eben nur um die Hashwerte zu erzeugen.
    Die Idee wurde aber sowieso wieder verworfen.


  • Mod

    @unterfliege sagte in Hash 4 Integers:

    @tggc Wenn der Hash gut genug wäre und auf mehrere 100000 Arrays keine Kollisionen liefert, wäre der Geschwindigkeitsvorteil eventuell die Gefahr einer Kollision wert.
    Aber natürlich brauche ich am Anfang schon die Pointer im Array, aber eben nur um die Hashwerte zu erzeugen.
    Die Idee wurde aber sowieso wieder verworfen.

    Du weißt schon, dass eine Kollision kein Beinbruch für eine Map ist? Funktioniert wunderbar und ist dann halt mal minimal langsamer. Es ist wahrscheinlich keine gute Idee, bei jedem Zugriff doppelt und dreifachen Rechenaufwand zu betreiben, um die Kollisionswahrscheinlichkeit von 1:100000 auf 1:1000000 zu senken. Den Aufwand einer besseren Hashfunktion möchtest du betreiben, wenn du so viele Werte hast, dass eine Kollision der Normalfall anstatt der Ausnahmefall wird.



  • @seppj Wenn ich den Hashwert als Key nehme, dann sind Kollisionen natürlich relevant. Dann habe ich schließlich nicht mehr die eigentlich wesentlichen Pointer zum Vergleich. Und wenn die Map keine weiteren Informationen außer dem Hashwert hat, dann kann sie auch nichts mehr machen, da sie bei Kollisionen keine Unterschiede erkennen kann.
    Diese Idee wurde aber ja schließlich sowieso schon verworfen. Da ist es wohl sinnvoller, sich nach einer besseren std::unordered_map umzusehen, wie die schon vorgeschlagene Googles dense_hash_map.



  • @unterfliege Hast du inzwischen denn std::unordered_map überhaupt mal ausprobiert? Die Idee "Hashwert als Key" ist seltsam, aber zum Glück schon verworfen.



  • @wob Ja, natürlich, damit arbeite ich natürlich schon die ganze Zeit, seitdem ich die Hash-Funktion verwende. Klappt mit dem boost-Code auch sehr gut.
    War ja auch nur eine Idee, da ich anfangs tatsächlich 0.0% Kollisionen hatte, war aber vermutlich nur Glück.
    Nun habe ich gerade eben auch noch einmal profilt und die map ist damit gerade nur noch die drittgrößte Bremse. Ich werde mich also noch an andere Optimierungen machen und anschließend noch einmal der Map zuwenden und z.B. die erwähnte dense_hash_map versuchen oder eine andere Implementation.


Anmelden zum Antworten