Ich bin auf der Suche nach einer Hash-Funktion, um eine (globale) feste Größe ID für Strings, die meisten von ihnen URIs.effiziente Hash-Funktion für Uris
es sein sollte:
wäre http://murmurhash.googlepages.com/ eine gute Wahl oder ist etwas besser geeignet?
Versuchen Sie MD4. Was die Kryptographie angeht, ist sie "kaputt", aber da Sie keine Sicherheitsbedenken haben (Sie wollen eine 64-Bit-Ausgabegröße, die zu klein ist, um eine angemessene Sicherheit gegen Kollisionen zu bieten), sollte das kein sein Problem. MD4 ergibt einen 128-Bit-Wert, den Sie nur auf die gewünschte Größe kürzen müssen.
Kryptografische Hash-Funktionen sind für die Widerstandsfähigkeit gegen explizite Versuche zum Aufbau von Kollisionen ausgelegt. Vorstellbar ist, dass man eine schnellere Funktion aufbauen kann, indem man diese Bedingung entspannt (es ist leichter, zufällige Kollisionen zu übertreffen als ein bestimmter Angreifer). Es gibt einige solche Funktionen, z.B. Murmur Hash. Aber es kann eine ziemlich spezifische Einstellung erfordern, um tatsächlich den Geschwindigkeitsunterschied zu bemerken. Mit meinem Heim-PC (einem 2,4 GHz Core2) kann ich mit MD4 mit einem einzigen CPU-Kern (ich habe vier Kerne) ungefähr 10 Millionen kurze Ketten pro Sekunde hashen. Damit MurmurHash auf nicht zu vernachlässigende Weise schneller als MD4 ist, müsste es in einem Kontext verwendet werden, der mindestens eine Million Hashaufrufe pro Sekunde umfasst. Das passiert nicht sehr oft ...
Ich würde etwas länger warten, bis MurmurHash3 fertiggestellt ist, dann benutze es. Die 128-Bit-Version sollte Ihnen einen angemessenen Kollisionsschutz gegen das Geburtstagsparadoxon bieten.
Ich denke, md4 sollte in Ordnung sein. Ich kann sogar mehr Bits nehmen. aber ich frage mich immer noch, ob es möglich und sinnvoll wäre, eine Hash-Funktion für URIs zu optimieren. Die Idee wäre, dass die Top-Tabelle und vielleicht sogar die Domain häufiger sind als die Zeichen am Ende. – yawniek
Ich habe MurmurHash tatsächlich mit SHA-1 verglichen, daher kann ich Ihnen versichern, dass der Unterschied in der Praxis ziemlich signifikant ist. Es ist besonders schmerzhaft für viele kurze Saiten, da SHA-1 einen großen Setup-Aufwand hat, aber selbst mit langen Saiten, die mit I/O vermischt sind, summiert sich der Unterschied schnell. –