Fresh Tweak on Open Addressing Hash Maps

/u/pdimov2 posted about the upcoming boost::unordered_flat_map for Boost 1.81 on r/cpp (see the post if you are interested).

A commenter unearthed a mini high-level design description in the source code itself.

Of particular interest, to me, is the tweak to the overflow representation. Both the Swiss Map (Abseil) and F14 (Facebook) use a counter as far as I know, which allows them -- when deleting a value -- to reduce the counter, so that if it ever reaches 0 again, they know that no further value is overflowing a given group, and can cut the probing sequence sooner.

Instead, the new Boost implementation uses the overflow byte as a Bloom Filter, by setting the bit at index hash % 8 in case of overflow. This makes it impossible to ever recover that bit in O(1) during deletion, in exchange of splitting the overflow indicator into 8 parallel track, so that a single overflowed value only incur a longer probing sequence for 1/8th of searches.

While the theoretical property of being able to recover from overflow is nice, it's not clear how often one benefits from it in practice: it requires that all overflowed values be removed from the map, after all, which seems quite a specific scenario. A single overflowed value remaining behind foils the scheme.

On the other hand, the 8 parallel track provides an immediate benefit. And I can only surmise that it is partly the cause for the new Boost hash map to beat the Swiss Map in performance in most scenarios.