List of the contestants for the benchmark. Note that some implementations are here multiple times but with a different max load factor. When comparing two hash maps, don't forget to take the load factor into account (it is easier for a hash map with a load factor of 0.2 to be faster than one with 0.9). When hovering over a data point, you will be able to see the load factor of the map for the data point.

- std::unordered_map: chaining with a max load factor of 1.0, libstdc++ implementation, v3.4.
- google::dense_hash_map: quadratic probing with a max load factor of 0.5, v2.0.
- google::dense_hash_map (0.9 mlf): quadratic probing with a max load factor of 0.9, v2.0.
- google::sparse_hash_map: sparse quadratic probing with a max load factor of 0.8, v2.0.
- QHash: chaining with a max load factor of 1.0, v4.8.
- tsl::sparse_map: sparse quadratic probing with a max load factor of 0.5, v0.1.
- tsl::hopscotch_map: hopscotch hashing with a max load factor of 0.9, v1.4.
- tsl::hopscotch_map (0.5 mlf): hopscotch hashing with a max load factor of 0.5, v1.4.
- tsl::hopscotch_map (with StoreHash): hopscotch hashing with a max load factor of 0.8 and StoreHash equals to true, v1.4.
- tsl::robin_map: linear robin hood probing with a max load factor of 0.5, v0.1.
- tsl::robin_map (0.9 mlf): linear robin hood probing with a max load factor of 0.9, v0.1.
- tsl::robin_map (with StoreHash): linear robin hood probing with a max load factor of 0.5 and StoreHash equals to true, v0.1.
- tsl::robin_map_pg: linear robin hood probing with a max load factor of 0.5 and using a prime as table size, v0.1.
- tsl::ordered_map: linear robin hood probing with keys-values outside the bucket array and with a max load factor of 0.75, v0.4.
- tsl::array_map: array hash table, specialized for strings, with a max load factor of 2.0, v0.3. Note that the implementation doesn't use a std::string as key which give it some advantage regarding its memory usage.
- tsl::array_map (1.0 mlf): array hash table, specialized for strings, with a max load factor of 1.0, v0.3. Note that the implementation doesn't use a std::string as key which give it some advantage regarding its memory usage.
- ska::flat_hash_map: linear robin hood probing with a max load factor of 0.5 and using a prime as table size.
- ska::flat_hash_map (power of two): linear robin hood probing with a max load factor of 0.5 and using a power of two as table size.
- spp::sparse_hash_map: sparse quadratic probing with a max load factor of 0.5.
- boost::unordered_map: chaining with a max load factor of 1.0, v1.62.
- emilib::HashMap: linear probing with a max load factor of 0.625.

Analysis of the data.

The benchmark was compiled with Clang 5.0 and ran on Linux 4.11 x64 with an Intel i5-5200u and 8 Go of RAM.

For the integers tests, we use hash maps with int64_t as key and int64_t as value.

Before the test, we generate a vector with the values [0, nb_entries) and shuffle this vector. Then for each value k in the vector, we insert the key-value pair (k, 1) in the hash map.

number of entries in hash table

Before the test, we generate a vector of nb_entries size where each value is randomly taken from an uniform random number generator from all possible positive values an int64_t can hold. Then for each value k in the vector, we insert the key-value pair (k, 1) in the hash map.

number of entries in hash table

Same as the random full inserts test but the reserve method of the hash map is called beforehand to avoid any rehash during the insertion. It provides a fair comparison even if the growth factor of each hash map is different.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the random full insert test. We then delete each key one by one in a different and random order than the one they were inserted.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the random shuffle inserts test. We then read each key-value pair in a different and random order than the one they were inserted.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the random full inserts test. We then read each key-value pair in a different and random order than the one they were inserted.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the random full inserts test. We then generate another vector of nb_entries random elements different from the inserted elements and we try to search for these unknown elements in the hash map.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the random full inserts test before deleting half of these values randomly. We then try to read all the original values in a different order which will lead to 50% hits and 50% misses.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the random full inserts test. We then use the hash map iterators to read all the key-value pairs.

number of entries in hash table

Before the random full inserts benchmark finishes, we measure the memory that the hash map is using.

number of entries in hash table

Before the random full inserts with reserve benchmark finishes, we measure the memory that the hash map is using. The benchmark is similar to the one above but without measuring the memory fragmentation that the rehash process may cause.

number of entries in hash table

For the small string tests, we use hash maps with std::string as key and int64_t as value.

Each string is a random generated string of 15 alphanumeric characters (+1 for the null terminator). A generated key may look like "ju1AOoeWT3LdJxL".

For each entry in the range [0, nb_entries), we generate a string as key and insert it with the value 1.

number of entries in hash table

Same as the inserts test but the reserve method of the hash map is called beforehand to avoid any rehash during the insertion. It provides a fair comparison even if the growth factor of each hash map is different.

number of entries in hash table

Before the test, we insert nb_entries elements in the hash map as in the inserts test. We then delete each key one by one in a different and random order than the one they were inserted.

number of entries in hash table

Before the test, we insert nb_entries elements in the hash map as in the inserts test. We then read each key-value pair in a different and random order than the one they were inserted.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the inserts test. We then generate nb_entries strings different from the inserted elements and we try to search for these unknown elements in the hash map.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the inserts test before deleting half of these values randomly. We then try to read all the original values in a different order which will lead to 50% hits and 50% misses.

number of entries in hash table

Before the inserts benchmark finishes, we measure the memory that the hash map is using.

number of entries in hash table

Before the inserts with reserve benchmark finishes, we measure the memory that the hash map is using. The benchmark is similar to the one above but without measuring the memory fragmentation that the rehash process may cause.

number of entries in hash table

For the string tests, we use hash maps with std::string as key and int64_t as value.

Each string is a random generated string of 50 alphanumeric characters (+1 for the null terminator). A generated key may look like "nv46iTRp7ur6UMbdgEkCHpoq7Qx7UU9Ta0u1ETdAvUb4LG6Xu6".

For each entry in the range [0, nb_entries), we generate a string as key and insert it with the value 1.

number of entries in hash table

Same as the inserts test but the reserve method of the hash map is called beforehand to avoid any rehash during the insertion. It provides a fair comparison even if the growth factor of each hash map is different.

number of entries in hash table

Before the test, we insert nb_entries elements in the hash map as in the inserts test. We then delete each key one by one in a different and random order than the one they were inserted.

number of entries in hash table

Before the test, we insert nb_entries elements in the hash map as in the inserts test. We then read each key-value pair in a different and random order than the one they were inserted.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the inserts test. We then generate nb_entries strings different from the inserted elements and we try to search for these unknown elements in the hash map.

number of entries in hash table

Before the test, we insert nb_entries elements in the same way as in the inserts test before deleting half of these values randomly. We then try to read all the original values in a different order which will lead to 50% hits and 50% misses.

number of entries in hash table

Before the inserts benchmark finishes, we measure the memory that the hash map is using.

number of entries in hash table

Before the inserts with reserve benchmark finishes, we measure the memory that the hash map is using. The benchmark is similar to the one above but without measuring the memory fragmentation that the rehash process may cause.

number of entries in hash table