Warum ist std :: hash nicht garantiert deterministisch?

Im Folgenden verwenden wir N4140 (C ++ 14 Standard).

Gemäß § 17.6.3.4 Hash-Anforderungen ,

Der zurückgegebene Wert hängt nur vom Argument k für die Dauer des Programms ab .

[Hinweis: Somit ergeben alle Auswertungen des Ausdrucks h(k)mit demselben Wert für kdasselbe Ergebnis für eine bestimmte Ausführung des Programms . - Endnote]

und § 20.9.12 Klassenvorlagen-Hash sagt

...

Die Instanziierung hash<Key>soll:

(1.1) - die Hash-Anforderungen erfüllen (17.6.3.4) ...

(1.2) - ...

Dies bedeutet, dass ein Hashwert von value(dh hash<decltype(value)>(value)) einen anderen Wert annehmen kann, wenn Sie das Programm neu starten.

Aber warum? Diese Einschränkung war nicht im Standard von C ++ 11 enthalten, sondern im Standard von C ++ 14, C ++ 17 und C ++ 20. Als Benutzer (kein STL-Entwickler) wäre es sehr nützlich, wenn er std::hashdeterministisch wäre. Gibt es mathematische Schwierigkeiten bei der Implementierung einer deterministischen Hash-Funktion? Aber Hash-Funktionen, die wir täglich verwenden (z. B. veraltet md5sumoder sicherer sha256), sind alle deterministisch. Gibt es ein Effizienzproblem?

Es ist nicht erforderlich, dass die Hash-Funktion zwischen den Läufen deterministisch ist, aber Sie können trotzdem Ihren eigenen Hash bereitstellen, z. B. für ungeordnete Container, wenn Sie sich auf dieses Verhalten verlassen.

Was den Grund betrifft, sagt cppreference :

Hash-Funktionen sind nur erforderlich, um innerhalb einer einzigen Programmausführung dasselbe Ergebnis für dieselbe Eingabe zu erzielen. Dies ermöglicht gesalzene Hashes, die Kollisions-Denial-of-Service-Angriffe verhindern.

Wenn die HashAnforderungen vorschreiben, dass sie deterministisch sind, können Sie keinen gesalzenen Hash bereitstellen, ohne die Anforderung zu brechen.

Hier ist die eigentliche Erklärung warum

Diese von @NathanOliver vorgeschlagene Antwort (und die darin enthaltenen Links) ist letztendlich hilfreich. Lassen Sie mich wichtige Teile anführen.

Für eine nicht kryptografische Hash-Funktion ist es möglich, massive Eingaben mit demselben Hash-Wert vorab zu berechnen, um die ungeordneten Container algorithmisch zu verlangsamen, und dies führt zu einem Denial-of-Service-Angriff.

(ab Ausgabe 2291. std :: hash ist anfällig für Kollisions-DoS-Angriffe )

Aus diesem Grund migrieren Sprachdesigner zu zufälligem Hashing. Beim zufälligen Hashing kann sich der Hashwert der Zeichenfolge "a" jedes Mal ändern, wenn Sie Ihr Programm ausführen. Zufälliges Hashing ist jetzt die Standardeinstellung in Python (ab Version 3.3), Ruby (ab Version 1.9) und Perl (ab Version 5.18).

(von Ist Ihnen klar, dass Sie zufälliges Hashing verwenden? )

Gehen Sie zu Ready und nicht zu Sofort, da selbst die Erlaubnis in der Reflektordiskussion umstritten war

(ab Ausgabe 2291. std :: hash ist anfällig für Kollisions-DoS-Angriffe )

In der Praxis std::hashimplementiert meines Wissens keine Implementierung von zufälligem Hashing, aber Sie können Ihre eigenen schreiben my::secure_hash.

(aus dieser Antwort )

PS

Ich habe gerade "Hash Table Dos" gegoogelt und eine informative Seite gefunden: Der Moment, in dem Sie feststellen, dass jeder Server auf der Welt anfällig ist .