unordered_dense v4.9.0

A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion

Release notes

## New

- **Look up with a hash computed once.** `hash_for(key)` returns a precomputed hash that `find`, `contains`, `count`, `equal_range` and `at` accept as a second argument, so a key looked up in several tables is hashed once rather than once per table. The hash is tied to the hasher, so it is shared by every table using that hasher — a `map<std::string, int>` and a `set<std::string>` can use the same one. (#156)
- **Mark a hash avalanching from outside it.** `ankerl::unordered_dense::hash_is_avalanching<Hash>` can be specialized for a hash you did not write, including a `std::hash` specialization, and the table asks the trait everywhere it used to look for the member typedef. `require_avalanching<Hash>` wraps a hash and static_asserts that it qualifies, so a hash that quietly loses its marker fails to compile rather than silently costing a rehash. The trait deliberately has the same name, the same two spellings and the same meaning as `boost::hash_is_avalanching`, so a hash annotated for either library is read correctly by the other. (#92)

## Behaviour change

wyhash produces different values than 4.8.1 for inputs of 8–16 bytes and for inputs over 48 bytes. Hash values and iteration order therefore differ from 4.8.1. Nothing ever promised either across versions, but anything that persists a hash, a bucket array or an iteration order needs re-checking.

## Fixes

- Allocator handling in `segmented_vector`, in `detail::table`'s constructors, and for the bucket container in copy, move, swap and assignment
- The bucket array is allocated on the first insert rather than in the constructor, so a default-constructed table costs no allocation
- The table is left valid and leak-free when a copy, move, assignment, erase or extract throws — including a block whose pointer could not be stored, and an erased value whose move out throws
- A `max_load_factor` that open addressing cannot honour is refused instead of hanging
- `segmented_vector`'s iterator reports itself as random access
- A map that was `extract()`ed from is usable again
- Swapping two maps no longer allocates
- `noexcept` specifications now say what they meant to say
- A segmented `BucketContainer` no longer calls `deallocate_bucket` while growing
- MSVC C4163 on ARM64EC, macOS clang signedness warnings, and `fmt/core.h` deprecation

## Performance

- Faster hashing, probing and erase
- The bucket array is copied once instead of twice
- No memset when clearing an already-empty table

## Development

libFuzzer and AFL++ targets with committed corpora and a nightly fuzzing workflow, clang-format enforced at a pinned version, and CI extended to libc++ on Linux.

**Full Changelog**: https://github.com/martinus/unordered_dense/compare/v4.8.1...v4.9.0

Share this resource