How Std::Unordered_Map Is Implemented

How std::unordered_map is implemented

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.

implementation of bucket in unordered_map

The standard doesn't mandate any particular implementation.

Only linked lists are used in the libstdc++ and Microsoft implementations (I didn't study other implementations, so here I'm considering only these two). Both of them use one long linked list (libstdc++ - singly-linked list, Microsoft - doubly-linked list) that holds all the buckets. This allows fast iteration through the whole container and makes operator++ operation on iterator O(1).

The bucket array in libstdc++ holds pointers to one element before the first bucket element (because it is a singly-linked list). In Microsoft implementation the bucket array holds pairs of iterators - to the first bucket element and to the one past the last one.

Schematic representation* for libstdc++:

Schematic representation* for Microsoft:

* Both diagrams correspond to std::unordered_set<Key>. For std::unordered_map<Key, Value>, key should be replaced with std::pair<Key, Value>.

How does std::unordered_map store and compare its keys to achieve fast access to elements without ordering?

Fast element access does require some form of ordering. Unordered_map is called that way because the ordering might not make sense to a human and might not remain stable when you add or remove elements.

unordered_map is not faster than map because comparing hashes one to one is faster than comparing arbitrary objects one to one. It is faster because it doesn't need comparisons at all. This is why it doesn't need a compare template parameter.

The typical unordered_map implementation is a hash table. A hash table is mostly a regular array of key-value pairs that uses a clever trick to help you find the element you're looking for quickly.

An ideal hash function is uniformly distributed: if you were to pick a hash from any object at random, the value of hash % N for some integer N should be roughly uniform (pretending for a second that modulo bias doesn't exist). If you choose N to be the size of your array of key-value pairs, you can use hash(key) % size as an array index for quick lookup.

Since the hash value is supposed to be uniformly-distributed, different objects will usually have a different index, so things will usually work in your favor by doing just that. However, it's still possible that hash(key) % N is the same thing for two objects. In this case, the hash table needs to handle a collision: there are multiple strategies, but all of them typically devolve to a linear search within the keys that fell in the same hash bucket (and for that reason, the hash table needs to contain the key too, not just the hash of the key). This is why the worst-case access time for a hash table is O(n), andd it highlights the importance of having a good hash function.

In some cases, this can be a reason to prefer map over unordered_map, as the access performance of map (O(log n)) is very predictable.

Also, as the number occupied buckets in a hash table increases, the chances of a collision also increases. In general, for that reason, hash tables will have more buckets than elements, meaning that it's "wasting" space for efficiency.

How a std::unordered_map search algorithm is implemented?

You can search through a std::unordered_map for a key with a code like below: (here key variable equals to the key you are searching):

if (your_map.find(key) != your_map.end()) {
    ...
}

If you want to search for a value you can use for loop like this:

for (const auto& pair : your_map) {
    if (pair.second == the_value_you_are_finding) {
        ...
        break;
    }
}

But if you want to know how does your program searchs through the unordered map or how the functions used above are implemented then you have to see the source code of your C++ Standard Library as it depends on your library.

C++ stl unordered_map implementation, reference validity

Yes, linked lists are involved, although not quite in the way you suggest.

The 2011 standard says (23.2.5 para 8), "The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket."

Within each bucket, the elements are in a linked list (a separate list for each bucket, not one big list for the whole container). When the container is rehashed, the elements will be assigned to new buckets, but the pointers to each element remain valid. The linked list in each new bucket is assembled from pointers to the existing elements that end up in that bucket.

Iterators are invalidated by a rehash, since an iterator needs to hold pointers to both the element and its bucket (so it can be stepped from the last element of one bucket to the first element of the next). The element pointer remains valid, so existing pointers and references to an element are still valid, but the bucket pointer is invalidated by a rehash, so the iterator isn't usable.

(This is also why unordered containers only support forward iterators, instead of the bidirectional iterators supported by the ordered associative containers. The elements of each bucket are in a singly linked list, so you can't step backwards through them.)

How does std::unordered_map determine the location of a specific key in a hash table?

Typically a hash map keeps an array of buckets inside. A bucket, on the other hand is a list of entries. And so something like this:

template<class TKey, class TValue>
class HashMap {
    vector<vector<pair<TKey, TValue>>> Buckets;
};

Then when you do a lookup, it simply takes the key, computes its hash, say hash, goes to Buckets[hash % Buckets.size], which is of type vector<pair<TKey,TValue>> and does a linear search on it. This makes the amortized (average) lookup complexity constant, while in the worst case (e.g. bad hashing function) it is linear. And indeed, this is the guarantee you get with the unordered_map.

Note that the top level vector will eventually grow when you add elements (maybe even when you remove), in order to allow more entries and avoid collisions. Rehashing is likely to take place in such case. And so adding/removing elements is not trivial, and can be expensive from time to time.

Also note that since vector allocates memory on the heap under the hood, then there is no issue with using more than one map. They share nothing (well, they may share something, but it doesn't affect the behaviour). But even if an implementation does not use vector (which is not mandatory, its just an example), some form of dynamic malloc has to be used to guarantee that.

Is gcc std::unordered_map implementation slow? If so - why?

I found the reason: it is a Problem of gcc-4.7!!

With gcc-4.7

inserts: 37728
get    : 2985

With gcc-4.6

inserts: 2531
get    : 1565

So std::unordered_map in gcc-4.7 is broken (or my installation, which is an installation of gcc-4.7.0 on Ubuntu - and another installation which is gcc 4.7.1 on debian testing).

I will submit a bug report.. until then: DO NOT use std::unordered_map with gcc 4.7!

---

Related Topics