How does C++ STL unordered_map resolve collisions?

by

The standard defines a little more about this than most people seem to realize.

Specifically, the standard requires (ยง23.2.5/9):

The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket.

The interface includes a bucket_count that runs in constant time. (table 103). It also includes a bucket_size that has to run in time linear on the size of the bucket.

That’s basically describing an implementation that uses collision chaining. When you do use collision chaining, meeting all the requirements is somewhere between easy and trivial. bucket_count() is the number of elements in your array. bucket_size() is the number of elements in the collision chain. Getting them in constant and linear time respectively is simple and straightforward.

By contrast, if you use something like linear probing or double hashing, those requirements become all but impossible to meet. Specifically, all the items that hashed to a specific value need to land in the same bucket, and you need to be able to count those buckets in constant time.

But, if you use something like linear probing or double hashing, finding all the items that hashed to the same value means you need to hash the value, then walk through the “chain” of non-empty items in your table to find how many of those hashed to the same value. That’s not linear on the number of items that hashed to the same value though–it’s linear on the number of items that hashed to the same or a colliding value.

With enough extra work and a fair amount of stretching the meaning of some of the requirements almost to the breaking point, it might be barely possible to create a hash table using something other than collision chaining, and still at least sort of meet the requirements–but I’m not really certain it’s possible, and it would certain involve quite a lot of extra work.

Summary: all practical implementations of std::unordered_set (or unordered_map) undoubtedly use collision chaining. While it might be (just barely) possible to meet the requirements using linear probing or double hashing, such an implementation seems to lose a great deal and gain nearly nothing in return.

More Related Contents:

  1. How to choose between map and unordered_map?
  2. What is the default hash function used in C++ std::unordered_map?
  3. Why can’t I replace std::map with std::unordered_map
  4. error for hash function of pair of ints
  5. c++ push reference node to stl list
  6. Erasing elements from a vector
  7. Why can’t I make a vector of references?
  8. Concise explanation of reference collapsing rules requested: (1) A& & -> A& , (2) A& && -> A& , (3) A&& & -> A& , and (4) A&& && -> A&&
  9. Is there any advantage of using map over unordered_map in case of trivial keys?
  10. Using custom std::set comparator
  11. When vectors are allocated, do they use memory on the heap or the stack?
  12. In STL maps, is it better to use map::insert than []?
  13. Why use non-member begin and end functions in C++11?
  14. std::fstream doesn’t create file
  15. Where can I get a “useful” C++ binary search algorithm?
  16. Relative performance of std::vector vs. std::list vs. std::slist?
  17. Stack-buffer based STL allocator?
  18. std::sort does not always call std::swap
  19. How to use std::sort with a vector of structures and compare function?
  20. Checking if an iterator is valid
  21. Which STL container should I use for a FIFO?
  22. Reading and writing a std::vector into a file correctly
  23. Why are C++ STL iostreams not “exception friendly”?
  24. initializing std::string from char* without copy
  25. does (w)ifstream support different encodings
  26. C++11 STL containers and thread safety
  27. How can I use Standard Library (STL) classes in my dll interface or ABI?
  28. How can i estimate memory usage of std::map?
  29. Memory allocation and deallocation across dll boundaries
  30. Incrementing iterators: Is ++it more efficient than it++? [duplicate]

Leave a Comment