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

问题描述 投票:5回答:1

此后,我们使用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(即hash<decltype(value)>(value))的哈希值可能会采用不同的值。

但是为什么呢?此限制不在C ++ 11标准中,而是在C ++ 14,C ++ 17和C ++ 20标准中。作为用户(不是STL开发人员),如果std::hash是确定性的,那将非常有用。实现确定性哈希函数有任何数学困难吗?但是我们每天使用的哈希函数(例如,不建议使用的md5sum或更安全的sha256)都是确定性的。有效率问题吗?

c++ hash language-lawyer std
1个回答
2
投票

不需要在每次运行之间确定哈希函数,但是您仍然可以提供自己的哈希,例如用于无序容器(如果您依赖的行为)。

关于为什么,cppreference说:

散列函数仅需要在程序的一次执行中为相同的输入产生相同的结果;这允许使用盐腌的哈希值来防止冲突拒绝服务攻击。

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

© www.soinside.com 2019 - 2024. All rights reserved.