6

我不明白为什么Data.HashTable 要使用Data.Hashable ,它hashWithSalt是(唯一/基本)方法。

这不符合计算哈希值一次并将其存储在对象中的自然优化(自然,因为 Haskell 对象是不可变的)。

如果我想使用HashTables它,那么我将被迫实施hashWithSalt. (从 1.2.0.* 到 1.2.1.*,hashablehash作为类方法重新引入,但这没有帮助?)

实际的 Table 实现似乎没有使用hashWithSaltHashTable.ST.Linear根本没有,HashTable.ST.Cuckoo只使用两个固定的盐)。

4

1 回答 1

2

As Carl notes in the comments, the move to the hashWithSalt method over just hash (as the original Hashable used) was to allow people to mitigate DOS attacks based on hash collisions. For a period, a different random default salt was generated on every run, even, using unsafePerformIO in the background. This lack of reproducibility turned out to be a huge problem, however, for people interested in e.g. persisting data structures across runs, getting reliable benchmarking numbers, etc.

So, the current approach is to provide the method, but tend to defer to a default salt that is fixed, and then add a warning to the documentation that this remains susceptible to various potential DOS attack vectors if used in a public-facing ways. (You can see for yourself in the documentation here: http://hackage.haskell.org/package/hashable-1.2.1.0/docs/Data-Hashable.html)

Because hash is its own class method, it is easy enough to implement an object with a "saltless" hash that is memoed with it, and furthermore, you can implement hashWithSalt as just xoring with the salt if you like. Or, as the comments note, you can implement hashWithSalt via a more legitimate method of hashing your generated/memoed hash.

于 2015-02-23T05:50:45.783 回答