I Wrote My Fastest Hashtable
The author seems to ignore that GCC's implementation of std::hash is the <i>identity</i> on integral types:
<a href="https://github.com/gcc-mirror/gcc/blob/cf8c140a8b8131b3ab4f500346dc4c004c899163/libstdc%2B%2B-v3/include/bits/functional_hash.h#L113" rel="nofollow">https://github.com/gcc-mirror/gcc/blob/cf8c140a8b8131b3ab4f5...</a><p>This is an incredibly poor design choice (at Facebook we'd say "clowntown") as it makes it unusable with any sophisticated hashtable data structure that assumes reasonable randomness. That's what causes the quadratic growth in the sequential example with dense_hash_map.<p>The solution is to use better hash functions, not prime hash table sizes. Prime modulus will only make the problems harder to notice, but if you have a poor hash function, you're giving up every complexity guarantee. Note that even if you reduce modulo a prime > n, you'll still have the identity over the first n numbers.<p>Personally I just use folly::Hash (<a href="https://github.com/facebook/folly/blob/da08e63ce3bac9196b18db82e64db8ecbb44d0ed/folly/Hash.h#L352" rel="nofollow">https://github.com/facebook/folly/blob/da08e63ce3bac9196b18d...</a>) as it uses sane defaults for hash functions, and contrary to std::hash it's a polymorphic functor so you can just drop it as template argument without having to specify the key type: dense_hash_map<int, int, folly::Hash>.<p>The other reason dense_hash_map uses power-of-2 sizes (other than to avoid the modulo) is that it is sufficient to guarantee that the quadratic probing schedule is transitive, that is, it can reach all the slots of the table. Quadratic probing is used because it's very effective for unsuccessful lookups. You can find a table of expected probe counts at different load factors here:
<a href="https://github.com/sparsehash/sparsehash/blob/4cb924025b8c622d1a1e11f4c1e9db15410c75fb/src/sparsehash/internal/densehashtable.h#L77" rel="nofollow">https://github.com/sparsehash/sparsehash/blob/4cb924025b8c62...</a><p>Hash tables are a fine craft. While it's interesting to gain these experiences first-hand, this is an amateurish post and it should be taken with a grain of salt.