It seems the std::hash functions for the C++17 string_view are not constexpr's.
It seems to me that a string view bound to a const char[] could be hashed at compile time (which would be very sweet), or is there anything which prevents this?
1 Answer
Since C++14 (see 17.6.3.4 Hash requirements, table 26), we have:
The value returned shall depend only on the argument k for the duration of the program. [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]
Two different executions can give different hashes:
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 DoS attacks.
This behaviour is useful to mitigate hash collision-based DoS attacks.
Details
Here's the wording about the requirements of the Hash concept from the C++17 standard:
The value returned shall depend only on the argument k for the duration of the program. [ 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 ]
It does not explicitly state anything about random hashing. The std::hash text does not mandate and does not preclude random hashing.
History
Here's the N3242 2011-02-28 draft which did not mention “for the duration of the program”:
Shall not throw exceptions. The value returned shall dependonly on the argument k. [Note: thus all evaluations of the expression h(k) with the same value for k yield the same result. — end note
We can see that the addition of "for the duration of the program" "for a given execution of the program" was added as a resolution for "2291. std::hash is vulnerable to collision DoS attack".
In practice
AFAIU, no implementation of std::hash implements random hashing but you can write your own my::secure_hash.
2 Comments
Damon
Unluckily, the last sentence is not true at all. The standard indeed requires that the value depends only on the argument for a given execution of the program, that's right. However, that's because some implementations just cast pointers into hash values. Other implementations (e.g. GCC) demonstrably hash byte-wise at runtime using FNV1 with a built-in constant seed, so in practice there is no such thing as randomized hashing. So, the standard gives us the worst of two worlds: No predictable output value, no constexpr, and at the same time no reliably non-predictable output value.
ysdx
@Damon: I'd say it's not that bad. What the standard gives you is the ability to write you own
my::secure_hash with non-predictable hashing and your own my::fast_hash with constexpr-ability. And it gives the ability for an implementation to use non-predictable hashing for std::hash.
hash<T>::operator()is constexpr, even for integral types (or at least I can't find any mention of constexpr hash in n4567.)