Hash of std::vector<dna4> is linear, should be constant for unordered_maps.

[h-2]

Interesting: https://en.cppreference.com/w/cpp/utility/hash says

The actual hash functions are implementation-dependent and are not required to fulfill any other quality criteria except those specified above. Notably, some implementations use trivial (identity) hash functions which map an integer to itself. In other words, these hash functions are designed to work with unordered associative containers, but not as cryptographic hashes, for example.

But, when using unorderd_map it says in https://en.cppreference.com/w/cpp/container/unordered_map/hash_function:

Complexity

Constant.

[marehr]

Just one remark the standard library uses https://github.com/gcc-mirror/gcc/blob/d1ca0650375baefa8851f7b1bebf70ebb1ea1446/libstdc%2B%2B-v3/libsupc%2B%2B/hash_bytes.cc#L74 for strings, which is linear, but uses some internal shenanigans to cache results of hash operations.

[smehringer]

Since hashing for containers is also linear do we still want to implement a constant version (by sampling or else)?