为什么不能保证std :: hash具有确定性? [英] Why is std::hash not guaranteed to be deterministic?
问题描述
此后，我们使用 N4140 (C ++ 14标准).
Hereafter, we use N4140 (C++14 Standard).
根据§17.6.3.4哈希要求，
返回的值应仅取决于参数
k在整个计划期间.
[注意:因此，表达式h(k)的所有求值具有相同的
对于给定的程序执行，k产生相同的结果 . —尾注]
[ Note: Thus all evaluations of the expression h(k) with the same value for
k yield the same result for a given execution of the program. — end note ]
和§20.9.12类模板哈希说
...
...
实例化hash<Key>应:
(1.1)-满足哈希要求(17.6.3.4)...
(1.1) — satisfy the Hash requirements (17.6.3.4) ...
(1.2)— ...
(1.2) — ...
这意味着如果重新启动程序，则哈希值value(即hash<decltype(value)>(value))可能会采用不同的值.
This means a hash value of value (i.e. hash<decltype(value)>(value)) may take a different value if you restart the program.
但是为什么呢?此限制不在C ++ 11的标准中，而是在C ++ 14，C ++ 17和C ++ 20的标准中.作为用户(不是STL开发人员)，如果std::hash是确定性的，这将非常有用.实现确定性哈希函数有任何数学困难吗?但是我们日常使用的哈希函数(例如已弃用的md5sum或更安全的sha256)都是确定性的.有效率问题吗?
But why? This limitation was not in the Standard of C++11, but in the Standard of C++14, C++17 and C++20. As a user (not a STL developer), it would be quite useful if std::hash were deterministic. Are there any mathematical difficulties in implementing a deterministic hash function? But hash functions we daily use (e.g. deprecated md5sum or safer sha256) are all deterministic. Is there a problem of efficiency?
推荐答案
在运行之间无需确定哈希函数，但是您仍然可以提供自己的哈希，例如用于无序容器(如果您所依赖的行为).
There is no need for the hash function to be deterministic between runs, but you can still provide your own hash, e.g. for unordered containers if it's a behavior you rely on.
关于原因， cppreference 说:
仅要求散列函数在程序的一次执行中为相同的输入产生相同的结果；这允许使用盐腌的哈希来防止冲突拒绝服务攻击.
Hash functions are only required to produce the same result for the same input within a single execution of a program; this allows salted hashes that prevent collision denial-of-service attacks.
如果Hash要求表明它是确定性的，那么您将无法在不违反要求的情况下提供加盐的哈希.
If the Hash requirements tells it to be deterministic, then you wouldn't be able to provide a salted hash without breaking the requirement.
这是为什么的实际解释
这篇关于为什么不能保证std :: hash具有确定性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
