{"id":108572,"date":"2023-08-08T07:00:00","date_gmt":"2023-08-08T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=108572"},"modified":"2023-08-08T07:43:57","modified_gmt":"2023-08-08T14:43:57","slug":"20230808-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20230808-00\/?p=108572","title":{"rendered":"Inside STL: The unordered_map, unordered_set, unordered_multimap, and unordered_multiset"},"content":{"rendered":"

The C++ standard library provides hash-based associative containers unordered_map<\/code>, unordered_set<\/code>, unordered_multimap<\/code>, and unordered_multiset<\/code>.<\/p>\n

All of these collections are hash tables with different payloads. The unordered_map<\/code> and the unordered_multimap<\/code> use a std::pair<Key, Value><\/code> as the payload, whereas the the unordered_set<\/code> and the unordered_multiset<\/code> use a Key<\/code> as the payload.<\/p>\n

Conceptually, the hash table consists of a bunch of buckets, and each bucket contains a linked list of the nodes that fall into that bucket. (This design is known as open hashing<\/i> or separate chaining<\/i>.) However, that’s not how the information is structured internally, because iterating through a traditionally-structured hash table requires more state than a single pointer: When you reach the end of each hash chain, you need some other information to tell you which chain to enumerate next.<\/p>\n

C++ standard library implementations instead structure the hash table like this:<\/p>\n

struct hashtable\r\n{\r\n    using hint = std::list<payload>::iterator;\r\n\r\n    std::list<payload> list;\r\n    std::vector<hint> buckets;\r\n};\r\n<\/pre>\n
The list<\/code> is a linked list of payloads, sorted by bucket. The buckets<\/code> is a vector of iterators (pointers) into the list that tells you where each bucket begins. Each bucket implicitly ends when the next bucket begins, or (for the last bucket) when the end of the list is reached.<\/p>\n
For example, suppose we have a hash table with four buckets, using the identity function as the hash function, and using “mod 4” as the bucket mapping function. Suppose that this hash table contains the values 2, 5, 6, 7. A traditional version of that hash table would look like a vector of lists:<\/p>\n\n\n\n\n\n\n\n
 <\/td>\nbuckets<\/td>\n<\/tr>\n
0<\/td>\nnull<\/td>\n<\/tr>\n
1<\/td>\n\u2022<\/td>\n\u2192<\/td>\n\n
5<\/div>\n<\/td>\n<\/tr>\n
2<\/td>\n\u2022<\/td>\n\u2192<\/td>\n\n
2<\/div>\n<\/td>\n
\u2192<\/td>\n\n
6<\/div>\n<\/td>\n<\/tr>\n
3<\/td>\n\u2022<\/td>\n\u2192<\/td>\n\n
7<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
However, in reality, the hash table looks like this:<\/p>\n\n\n\n\n\n
5<\/td>\n\u2192<\/td>\n2<\/td>\n\u2192<\/td>\n6<\/td>\n\u2192<\/td>\n7<\/td>\n<\/tr>\n
\u2191<\/td>\n <\/td>\n\u2191<\/td>\n <\/td>\n <\/td>\n <\/td>\n\u2191<\/td>\n<\/tr>\n
[0]
\n[1]<\/td>\n		 <\/td>\n[2]<\/td>\n <\/td>\n <\/td>\n <\/td>\n[3]<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
In this diagram, we see that<\/p>\n