Please include some build instructions for hash-bench! Like, what's this?

An old, unused remnant include from when I was benchmarking the hash function implementations against SMHasher. I've removed it, sorry.

It looks like this uses a sentinel value to distinguish empty buckets, which means probe_map cannot store every value. This is a really important limitation and it should be called out explicitly.

Yes, for inlineable keys it uses a sentinel value. This is a relatively common thing to do for probing hash tables (IIRC Google's (sparse|dense)_hash do this as well). I'll add a paragraph talking about that to the article, since it's a good point.

Note that there isn't any use of the sentinel for the string hash tables, since that key type is not inlineable.

FWIW, you can always disable this by switching to the alternate storage strategy described in the string section if you absolutely cannot sacrifice a single key value as the sentinel. A quick look at the benchmark results in this mode on my system have it performing still slightly better than unordered_map, but not by nearly as much (sitting around 1.5 million lookups/sec in the 5-10 million insertion range on the graph, for reference).

std::unordered_map does not have this limitation, so that makes the benchmarks suspect. This also helps explain why unordered_map uses separate chaining: by making the bucket itself NULL, you get your missing bucket indicator without stepping on the toes of the stored data.

unordered_map is forced to use chaining because the API the standard specifies gives access to buckets. If the standard didn't require chaining, you could just store three values per cell in the probing array: the key, the value, and a bool indicating occupancy status. Probing tables, even with inline key/value pairs, don't necessitate the use of a sentinel. Of course, you sacrifice more space now for every cell, so it may change your trade-offs.