Warum verwendet Data.HashTable Hashing mit Salz (aus Data.Hashable)?

Question

Ich verstehe nicht, warum Data.HashTableData.Hashable verwendet, die hashWithSalt als die (einzige/grundlegende) Methode hat.

Dies passt nicht mit der natürlichen Optimierung der Berechnung der Hash-Wert einmal, und speichern Sie es im Objekt (natürlich, weil Haskell-Objekte unveränderlich sind). Wenn ich HashTables damit verwenden möchte, bin ich gezwungen, hashWithSalt zu implementieren. (Going 1.2.0. * 1.2.1. *, Hashable wieder eingeführt hash als Klassenmethode, aber das hilft nicht?)

Das tatsächliche Tabelle Implementierungen scheint nicht Gebrauch von hashWithSalt zu machen (HashTable.ST.Linear nicht, HashTable.ST.Cuckoo verwendet nur zwei feste Salze).

Answer 1

Wie Carl in den Kommentaren bemerkt, war der Umzug in die hashWithSalt Methode über nur hash (wie das Original Hashable verwendet) war es, Menschen DOS-Angriffe auf Hash-Kollisionen abzuschwächen. Für einen Zeitraum wurde bei jedem Lauf ein anderes zufälliges Standard-Salz erzeugt, auch wenn unsafePerformIO im Hintergrund verwendet wurde. Dieser Mangel an Reproduzierbarkeit stellte sich jedoch als großes Problem für Leute heraus, die an z.B. Persistente Datenstrukturen über Läufe hinweg, um zuverlässige Benchmarking-Nummern usw. zu erhalten.

So ist der aktuelle Ansatz, die Methode zur Verfügung zu stellen, tendieren jedoch dazu, auf eine Standard-Salz zu verschieben, die behoben wird, und dann eine Warnung an die Dokumentation hinzufügen bleibt anfällig für verschiedene potentielle DOS-Angriffsvektoren, wenn sie in einer öffentlich zugänglichen Weise verwendet werden. (Sie können hier in der Dokumentation selbst sehen: http://hackage.haskell.org/package/hashable-1.2.1.0/docs/Data-Hashable.html)

Da hash seine eigene Klassenmethode ist, ist es einfach genug, um ein Objekt mit einem „saltless“ Hash zu implementieren, die mit ihm ist memoed, und darüber hinaus können Sie implementieren Sie hashWithSalt als nur xor ing mit dem Salz wenn Sie mögen. Oder, wie die Kommentare bemerken, können Sie hashWithSalt über eine legitimere Methode von hash implementieren Ihre generierte/memoed hash.