How std::unordered_map is implemented

by

The Standard effectively mandates that implementations of std::unordered_set and std::unordered_map – and their “multi” brethren – use open hashing aka separate chaining, which means an array of buckets, each of which holds the head of a linked list†. That requirement is subtle: it is a consequence of:

  • the default max_load_factor() being 1.0 (which means the table will resize whenever size() would otherwise exceed 1.0 times the bucket_count(), and
  • the guarantee that the table will not be rehashed unless grown beyond that load factor.

That would be impractical without chaining, as the collisions with the other main category of hash table implementation – closed hashing aka open addressing – become overwhelming as the load_factor()](https://en.cppreference.com/w/cpp/container/unordered_map/load_factor) approaches 1.

References:

23.2.5/15: The insert and emplace members shall not affect the validity of iterators if (N+n) < z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container’s bucket count, and z is the container’s maximum load factor.

amongst the Effects of the constructor at 23.5.4.2/1: max_load_factor() returns 1.0.

† To allow optimal iteration without passing over any empty buckets, GCC’s implementation fills the buckets with iterators into a single singly-linked list holding all the values: the iterators point to the element immediately before that bucket’s elements, so the next pointer there can be rewired if erasing the bucket’s last value.

Regarding the text you quote:

No, that is not at all the most efficient way to implement a hash map for most common uses. Unfortunately, a small “oversight” in the specification of unordered_map all but requires this behavior. The required behavior is that iterators to elements must stay valid when inserting or deleting other elements

There is no “oversight”… what was done was very deliberate and done with full awareness. It’s true that other compromises could have been struck, but the open hashing / chaining approach is a reasonable compromise for general use, that copes reasonably elegantly with collisions from mediocre hash functions, isn’t too wasteful with small or large key/value types, and handles arbitrarily-many insert/erase pairs without gradually degrading performance the way many closed hashing implementations do.

As evidence of the awareness, from Matthew Austern’s proposal here:

I’m not aware of any satisfactory implementation of open addressing in a generic framework. Open addressing presents a number of problems:

• It’s necessary to distinguish between a vacant position and an occupied one.

• It’s necessary either to restrict the hash table to types with a default constructor, and to construct every array element ahead of time, or else to maintain an array some of whose elements are objects and others of which are raw memory.

• Open addressing makes collision management difficult: if you’re inserting an element whose hash code maps to an already-occupied location, you need a policy that tells you where to try next. This is a solved problem, but the best known solutions are complicated.

• Collision management is especially complicated when erasing elements is allowed. (See Knuth for a discussion.) A container class for the standard library ought to allow erasure.

• Collision management schemes for open addressing tend to assume a fixed size array that can hold up to N elements. A container class for the standard library ought to be able to grow as necessary when new elements are inserted, up to the limit of available memory.

Solving these problems could be an interesting research project, but, in the absence of implementation experience in the context of C++, it would be inappropriate to standardize an open-addressing container class.

Specifically for insert-only tables with data small enough to store directly in the buckets, a convenient sentinel value for unused buckets, and a good hash function, a closed hashing approach may be roughly an order of magnitude faster and use dramatically less memory, but that’s not general purpose.

A full comparison and elaboration of hash table design options and their implications is off topic for S.O. as it’s way too broad to address properly here.

More Related Contents:

  1. How to specialize std::hash::operator() for user-defined type in unordered containers?
  2. Generic hash for tuples in unordered_map / unordered_set
  3. Choosing between std::map and std::unordered_map [duplicate]
  4. Why is std::unordered_map slow, and can I use it more effectively to alleviate that?
  5. What is the default hash function used in C++ std::unordered_map?
  6. Why can’t I replace std::map with std::unordered_map
  7. error for hash function of pair of ints
  8. Converting std::__cxx11::string to std::string
  9. C++ lambda with captures as a function pointer
  10. Will std::string always be null-terminated in C++11?
  11. SFINAE working in return type but not as template parameter
  12. Implementing comparison operators via ‘tuple’ and ‘tie’, a good idea?
  13. Why do std::shared_ptr work
  14. Extract year/month/day etc. from std::chrono::time_point in C++
  15. No matches with c++11 regex [duplicate]
  16. Pass by value vs pass by rvalue reference
  17. Is there a way to cancel/detach a future in C++11?
  18. Get function pointer from std::function when using std::bind
  19. In C++, is it still bad practice to return a vector from a function?
  20. Lambda expressions as class template parameters
  21. Using export keyword with templates
  22. What is the reason behind cbegin/cend?
  23. Understanding gsl::narrow implementation
  24. Conflict between copy constructor and forwarding constructor
  25. Futures vs. Promises
  26. How to get the precision of high_resolution_clock?
  27. STL algorithms: Why no additional interface for containers (additional to iterator pairs)?
  28. Does C++11 unique_ptr and shared_ptr able to convert to each other’s type?
  29. Proper way to receive a lambda as parameter by reference
  30. When to use functors over lambdas

Leave a Comment