Contestants

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.

Global selection

Integers

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

Random shuffle inserts: execution time (integers)

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.

Random full inserts: execution time (integers)

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.

Random full inserts with reserve: execution time (integers)

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.

Random full deletes: execution time (integers)

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.

Random shuffle reads: execution time (integers)

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.

Random full reads: execution time (integers)

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.

Random full reads misses: execution time (integers)

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.

Random full reads after deleting half: execution time (integers)

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.

Random full iteration: execution time (integers)

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.

Memory usage of random full inserts (integers)

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

Memory usage of random full inserts with reserve (integers)

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.

Small strings

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".

Inserts: execution time (small strings)

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

Inserts with reserve: execution time (small strings)

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.

Deletes: execution time (small strings)

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.

Reads: execution time (small strings)

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.

Reads misses: execution time (small strings)

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.

Reads after deleting half: execution time (small strings)

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.

Memory usage of inserts (small strings)

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

Memory usage of inserts with reserve (small strings)

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.

Strings

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".

Inserts: execution time (strings)

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

Inserts with reserve: execution time (strings)

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.

Deletes: execution time (strings)

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.

Reads: execution time (strings)

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.

Reads misses: execution time (strings)

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.

Reads after deleting half: execution time (strings)

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.

Memory usage of inserts (strings)

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

Memory usage of inserts with reserve (strings)

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.