为什么 std::hash 不能保证是确定性的?

ynn*_*ynn 28 c++ hash std language-lawyer

此后,我们使用N4140(C++14 标准)。


根据§ 17.6.3.4 哈希要求

返回值应仅取决于k 程序持续时间的参数。

[注意:因此,对于给定的程序执行,h(k)具有相同值 的表达式的所有评估都会k产生相同的结果。— 尾注 ]

§ 20.9.12 类模板哈希

...

实例化hash<Key>应:

(1.1) — 满足哈希要求 (17.6.3.4) ...

(1.2) — ...


这意味着如果您重新启动程序,value(ie hash<decltype(value)>(value))的哈希值可能会采用不同的值。

但为什么?这个限制不在 C++11 的标准中,而是在 C++14、C++17 和 C++20 的标准中。作为用户(不是 STL 开发人员),如果std::hash是确定性的,那将非常有用。在实现确定性散列函数时有什么数学上的困难吗?但是我们日常使用的散列函数(例如已弃用md5sum或更安全sha256)都是确定性的。效率有问题吗?

Geo*_*roy 17

散列函数不需要在运行之间具有确定性,但您仍然可以提供自己的散列,例如对于无序容器,如果它是您依赖的行为。

至于为什么,cppreference说:

哈希函数只需要在程序的单次执行中为相同的输入产生相同的结果;这允许防止碰撞拒绝服务攻击的加盐哈希。

如果Hash要求告诉它是确定性的,那么您将无法在不违反要求的情况下提供加盐哈希。

这是原因实际解释


ynn*_*ynn 7

@NathanOliver建议的这个答案(及其中的链接)最终很有帮助。让我引用重要的部分。

对于非加密散列函数,可以使用相同的散列值预先计算大量输入,以通过算法减慢无序容器的速度,并导致拒绝服务攻击。

(来自问题 2291。std::hash 容易受到碰撞 DoS 攻击

出于这个原因,语言设计者正在迁移到随机散列。在随机散列中,每次运行程序时,字符串“a”的散列值都会改变。随机散列现在是 Python(从 3.3 版开始)、Ruby(从 1.9 版开始)和 Perl(从 5.18 版开始)的默认设置。

(来自您是否意识到您正在使用随机散列?

移动到就绪,而不是立即,因为在反射器讨论中,即使是许可也有争议

(来自问题 2291。std::hash 容易受到碰撞 DoS 攻击

在实践中,据我所知,没有std::hash实现随机散列,但您可以编写自己的my::secure_hash.

(来自这个答案


聚苯乙烯

我刚刚在 google 上搜索了“hash table dos”并找到了一个信息丰富的页面:当您意识到世界上的每台服务器都易受攻击的那一刻