16.7. Analysis of hash tables

The table below shows the average case complexity of some basic std::unordered_map operations. These estimates assume a good hash function, a reasonable load factor, and fixed-size keys whose hash and equality operations take constant time. For lookup, insertion, and erasure, the worst-case complexity can be \(O(N)\) when many keys occupy the same bucket. clear is linear because it visits every stored element.

Average complexity of C++ unordered map operations

Operation	Complexity
operator[]	O(1)
insert()	O(1)
find()	O(1)
contains()	O(1)
erase()	O(1)
clear()	O(n)

C++20 Feature

C++20 added unordered_map::contains for membership checks when the mapped value is not needed. Its average complexity is constant under the same assumptions as find.

The reason these operations may have \(O(n)\) complexity is because the performance of the container is ultimately controlled by the quality of the hash function for the key type in the container. If the hash function performs poorly (many collisions), then the benefits of hash tables are lost and we decay into list performance. When the hash function quality is high, then the performance is good.

When we discussed the messy and neat closets in Tree ADT concepts, we mentioned that search is a primary motivation for non-sequential containers. A hash table can usually select the correct bucket in expected constant time, and then searches the bucket for an equal key. The hash computation and key comparison costs are part of the operation's total cost.

The following code shows what happens when searching in an unordered map vs a vector.

#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <vector>

int main() {
    using clock = std::chrono::steady_clock;
    std::cout << std::setw(6) << "size"
              << std::setw(10) << "vector"
              << std::setw(20) << "hash table\n";
    // for(int size = 10'000; size < 100'001; size += 20'000) {
    int size = 35000;
        // fill vector
        std::vector<int> sequence (size);
        std::iota(sequence.begin(), sequence.end(), 0);
        // search vector
        auto begin = clock::now();
        for(const auto& it: sequence){
            if(std::find(sequence.begin(), sequence.end(), it) == sequence.end()) {
                std::cerr << "Failed to find an expected value in vector! Halting.\n";
                return -2;
            }
        }
        auto end = clock::now();
        std::chrono::duration<double> elapsed_secs = end - begin;
        // fill hash table
        std::unordered_map<int, int> table;
        for(int item = 0; item < size; ++item){
            table[item] = item;
        }
        begin = clock::now();
        // search hash table
        for(const auto& it: table){
            if(table.find(it.first) == table.end()) {
                std::cerr << "Failed to find an expected value in map! Halting.\n";
                return -2;
            }
        }
        end = clock::now();
        std::chrono::duration<double> elapsed_secs_ht = end - begin;

        // Printing final output
        std::cout << std::fixed   << std::setprecision(4)
                  << std::setw(6) << size << '\t'
                  << std::setw(8) << elapsed_secs.count() << '\t'
                  << std::setw(8) << elapsed_secs_ht.count() << '\n';
    // }
    return 0;
}

Try This!

The online compiler is limited in both memory and time allowed.

Run this example on your own computer with the loop enabled and with larger values and compare.

The vector is linear in std::distance(begin, end) and as expected, the hash table is constant time. Running the previous code should produce results similar to this:

So what about the tree ADT? The standard does not require a particular implementation for std::set, but it does guarantee logarithmic complexity in the size of the container for search. This is a guaranteed bound, unlike the average constant-time bound for an unordered container.

How does std::set find compare to std::unordered_map find?

#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <set>
#include <unordered_map>

int main() {
    using clock = std::chrono::steady_clock;
    std::cout << std::setw(6) << "size"
              << std::setw(10) << "set"
              << std::setw(20) << "hash table\n";
    for(int size = 5'000; size < 100'001; size += 5'000) {
        // fill set
        std::set<int> tree;
        for(int item = 0; item < size; ++item){
            tree.insert(item);
        }
        // search set
        auto begin = clock::now();
        for(const auto& it: tree){
            if(tree.find(it) == tree.end()) {
                std::cerr << "Failed to find an expected value in set! Halting.\n";
                return -2;
            }
        }
        auto end = clock::now();
        std::chrono::duration<double> elapsed_secs = end - begin;
        // fill hash table
        std::unordered_map<int, int> table;
        for(int item = 0; item < size; ++item){
            table[item] = item;
        }
        begin = clock::now();
        // search hash table
        for(const auto& it: table){
            if(table.find(it.first) == table.end()) {
                std::cerr << "Failed to find an expected value in map! Halting.\n";
                return -2;
            }
        }
        end = clock::now();
        std::chrono::duration<double> elapsed_secs_ht = end - begin;

        // Printing final output
        std::cout << std::fixed   << std::setprecision(4)
                  << std::setw(6) << size << '\t'
                  << std::setw(8) << elapsed_secs.count() << '\t'
                  << std::setw(8) << elapsed_secs_ht.count() << '\n';
    }
    return 0;
}

Although the std::set find is logarithmic complexity, from a practical sense, it compares favorably with the hash table. The graph below shows example output for values up to 1,000,000.

Try This!

The online compiler is limited in both memory and time allowed.

Run this example on your own computer with larger values and compare.

---

More to Explore

• std::unordered_map

• std::unordered_set

• std::set

• Unordered associative container requirements