Search code examples
c++hashstdc++17string-view

std::string_view compile time hashing


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?


Solution

  • 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.