Why Does `std::unordered_map` Use Open Hashing?

Implementation of std::unordered_map

By analysis of the C standard, it becomes clear that the implementation of std::unordered_map must use a method known as open hashing, also known as separate chaining. This method consists of an array of buckets, each holding the head of a linked list, which enables efficient iteration without bypassing empty buckets.

The choice of open hashing was made intentionally to meet specific performance requirements outlined in the C standard. Firstly, the default maximum load factor is set to 1.0, which means that the table will resize whenever the size would surpass the bucket count by a factor of 1.0. Secondly, the table is guaranteed not to be rehashed unless it is grown beyond that load factor. These requirements make open hashing necessary because closed hashing becomes impractical as the load factor approaches 1 due to excessive collisions.

While some argue that open hashing is not the most efficient method for all use cases, it remains a reasonable choice for general usage due to its reliable handling of collisions, adaptability to key/value types of varying sizes, and overall efficiency in handling large volumes of insertions and deletions without performance degradation.

Therefore, std::unordered_map leverages open hashing to fulfill the specified performance requirements and remains a robust choice for most applications due to its versatility and efficiency.

The above is the detailed content of Why Does `std::unordered_map` Use Open Hashing?. For more information, please follow other related articles on the PHP Chinese website!