To expand on this a bit, the C++ unordered map (hash table) uses basically a linked list to track the entries in each bucket (separate chaining for collisions) because the standard requires that operations that may resize the map don't invalidate iterators.
You pay for this with extra memory allocations and non-contiguous memory access.
In most low level benchmarks, other collision mechanisms (probing, etc) perform much better.
You pay for this with extra memory allocations and non-contiguous memory access.
In most low level benchmarks, other collision mechanisms (probing, etc) perform much better.