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要求告诉它是确定性的,那么您将无法在不违反要求的情况下提供加盐哈希。
@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”并找到了一个信息丰富的页面:当您意识到世界上的每台服务器都易受攻击的那一刻。