Ich arbeite an einem System, bei dem Hash-Kollisionen ein Problem darstellen würden. Im Wesentlichen gibt es ein System, das auf Elemente in einer Hash-Tabelle+Baumstruktur verweist. Das fragliche System kompiliert jedoch zunächst Textdateien, die Pfade in der Struktur enthalten, in eine Binärdatei, die stattdessen die gehashten Werte enthält. Dies geschieht aus Leistungsgründen. Dies hat jedoch zur Folge, dass es zu Kollisionen kommt, da die Struktur nicht zwei Elemente mit demselben Hash-Wert speichern kann; der Teil, der nach einem Element fragt, hätte nicht genügend Informationen, um zu wissen, welches er benötigt.
Mein erster Gedanke ist, dass 2 Hashes, entweder mit 2 verschiedenen Algorithmen oder mit demselben Algorithmus zweimal, mit 2 Salts kollisionssicherer sein würden. Zwei Elemente mit demselben Hash für verschiedene Hash-Algorithmen wären sehr unwahrscheinlich.
Ich hatte gehofft, den Hash-Wert aus Platzgründen bei 32 Bit halten zu können, also dachte ich, ich könnte zwei 16-Bit-Algorithmen anstelle eines 32-Bit-Algorithmus verwenden. Aber das würde den Bereich der möglichen Hash-Werte nicht vergrößern...
Ich weiß, dass die Umstellung auf zwei 32-Bit-Hashes kollisionssicherer sein würde, aber ich frage mich, ob die Umstellung auf 2 16-Bit-Hashes zumindest einen gewissen Vorteil gegenüber einem einzelnen 32-Bit-Hash hat? Ich bin nicht die mathematisch begabteste Person, daher weiß ich nicht einmal, wie ich anfangen soll, nach einer Antwort zu suchen, außer sie mit Gewalt zu erzwingen...
Einige Hintergrundinformationen zum System:
Elemente werden von Menschen benannt, sie sind keine zufälligen Zeichenfolgen und bestehen in der Regel aus Wörtern, Buchstaben und Zahlen ohne Leerzeichen. Es handelt sich um eine verschachtelte Hash-Struktur. Wenn Sie also etwas wie { a => { b => { c => 'blah' }}} hätten, würden Sie den Wert 'blah' erhalten, indem Sie den Wert von a/b/c abrufen, die kompilierte Anfrage wäre 3 Hash-Werte in unmittelbarer Folge, die Hash-Werte von a, b und dann c.
Es gibt nur dann ein Problem, wenn es auf einer bestimmten Ebene zu einer Kollision kommt. Eine Kollision zwischen einem Element auf der obersten Ebene und einer niedrigeren Ebene ist kein Problem. Sie können { a => {a => {...}}} verwenden, was Kollisionen auf verschiedenen Ebenen fast garantiert (kein Problem).
In der Praxis wird eine bestimmte Ebene wahrscheinlich weniger als 100 Werte haben, die gehasht werden müssen, und keiner davon wird ein Duplikat auf derselben Ebene sein.
Um den von mir verwendeten Hash-Algorithmus zu testen (ich habe vergessen, welchen, aber ich habe ihn nicht erfunden), habe ich die gesamte Liste der CPAN-Perl-Module heruntergeladen, alle Namespaces/Module in eindeutige Wörter aufgeteilt und schließlich jedes einzelne auf der Suche nach Kollisionen gehasht. Das bedeutet, dass der Algorithmus für jedes eindeutige Wort in der CPAN-Namespace-Liste einen anderen Hash-Wert hat (oder dass ich es falsch gemacht habe). Das scheint mir gut genug zu sein, aber es nagt immer noch an meinem Gehirn.
