unordered_set and unordered_map: Jump Straight to the Right Bucket

Zara runs the server of an online game, and every new player picks a username. Thousands of times a second, the server must answer one question: is this name taken? A scan of a million names costs a million comparisons per question. A set from Module 8 needs a few dozen, and an array indexed by the name cannot exist, because a name is not a number. But what if the name itself could say where to look?

A number that says where to look

A hash function turns a key into a whole number, and the same key always gives the same number while the program runs. C++ ships one for every number type and for string: std::hash. hash<int>() makes a small hashing object, and (42) hands it the key 42.

#include <functional>
#include <iostream>
#include <string>
using namespace std;

int main() {
    cout << hash<int>()(42) << '\n';
    cout << hash<string>()("cat") << '\n';
    cout << hash<string>()("act") << '\n';
    for (int key : {12, 7, 20, 9, 31}) {
        cout << key << " % 5 = " << hash<int>()(key) % 5 << '\n';
    }
    return 0;
}

42
5726227304015210059
18297190751667054611
12 % 5 = 2
7 % 5 = 2
20 % 5 = 0
9 % 5 = 4
31 % 5 = 1

On GCC 12, an int's hash is the number itself, so 42 gives 42. A string's hash mixes every byte, so cat and act, the same three letters, get very different numbers. These numbers are GCC 12's own: the C++ standard fixes none of them, and another library may print others.

A hash container keeps an array of buckets, short lists of keys. To place a key, it takes the key's hash modulo the number of buckets, as the program's last lines do. That number is the key's bucket. To find the key later, it computes the same bucket and searches that bucket only. Two keys in one bucket, like 12 and 7 here, are a collision.

So a lookup never scans the whole table: one hash, one %, and a search of one short bucket.

Watch the table fill, collide and grow

unordered_set<int> s(5) asks for a table of five buckets. The widget replays what GCC 12 did with it, one call at a time. Every state was printed by a program on Compiler Explorer. Watch the order inside a bucket, and what happens when the sixth key arrives.

The load factor is the number of keys divided by the number of buckets. GCC 12 lets it reach 1, so five keys may fill five buckets. A sixth would push it past 1, so the table first grew to 11 buckets and moved every key to its new bucket: a rehash. GCC 12 picked 11, a prime number at least twice the old count, and lesson 05 shows the whole list.

Inside a bucket, the newest key comes first: 7 went in front of 12. find(31) compared three keys of bucket 9 and touched no other bucket. find(5) met an empty bucket and stopped without a single comparison. So a lookup costs one bucket's worth of comparisons, and the rehash keeps every bucket short.

The syntax you need on day one

#include <unordered_set>
#include <unordered_map>

unordered_set<T> s;               an empty set of keys of type T
unordered_set<T> s{a, b, c};      a set made from a list; repeats are dropped
s.insert(x);                      add x; nothing happens if x is already there
s.erase(x);                       remove x, if it is there
s.count(x)                        1 if x is there, 0 if not
s.find(x)                         an iterator to x, or s.end() if x is not there
s.size()    s.empty()             how many keys, and whether there are none
for (T x : s)                     every key once, in an order you cannot count on

unordered_map<K, V> m;            keys of type K, each with a value of type V
m[k] = v;                         store v under k; k is added if it is missing
m[k]                              the value under k; a missing k is added first
m.find(k)                         an iterator to the pair (k, value), or m.end()
for (auto& [k, v] : m)            every key with its value, in no fixed order

So the calls are the ones a set and a map use; only the order and the cost change.

insert, and a walk in no particular order

s.insert(x) puts x in its bucket, and a range-for walks every key once. Module 8's set walked its keys sorted. This one does not.

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s{5, 3, 9, 1, 7};
    s.insert(3);
    cout << "walk:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << " (size " << s.size() << ")\n";
    return 0;
}

walk: 7 1 9 3 5 (size 5)

The second 3 changed nothing, so the size stayed 5. The walk is not sorted, and it is not the order of the list either. It is GCC 12's own order, which comes from the buckets and from when each key arrived.

That order can change while the keys stay the same. This program puts five keys in, then adds nine more and erases them again. The extra keys grow the table, and the walk afterwards differs.

#include <iostream>
#include <unordered_set>
using namespace std;

void show(const unordered_set<int>& s) {
    cout << s.bucket_count() << " buckets:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << '\n';
}

int main() {
    unordered_set<int> s;
    for (int x : {40, 7, 21, 3, 15}) {
        s.insert(x);
    }
    show(s);
    for (int x = 50; x < 59; x++) {
        s.insert(x);
    }
    for (int x = 50; x < 59; x++) {
        s.erase(x);
    }
    show(s);
    return 0;
}

13 buckets: 15 3 21 7 40
29 buckets: 40 7 3 15 21

The same five keys gave two different walks: the table grew from 13 buckets to 29, and the rehash rebuilt it. Erasing the nine keys did not shrink it back. So never let a program depend on the walk order of a hash container: the next rehash, or another compiler, can change it.

Is it there? count and find

s.count(x) returns 1 if x is there and 0 if not. s.find(x) returns an iterator to x, or s.end() when x is missing.

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s{3, 9, 14, 27, 31};
    cout << s.count(14) << ' ' << s.count(5) << '\n';
    auto it = s.find(27);
    if (it != s.end()) {
        cout << "found " << *it << '\n';
    }
    if (s.find(5) == s.end()) {
        cout << "5 is not there\n";
    }
    return 0;
}

1 0
found 27
5 is not there

Compare find's answer with end() before you read it with *, because reading *s.end() is undefined behaviour. So count answers a plain yes or no, and find also gives you the place.

erase by key

s.erase(x) removes x if it is there, and does nothing if it is not.

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s{3, 9, 14, 27, 31};
    s.erase(14);
    s.erase(5);
    cout << "size " << s.size() << ", 14 there: " << s.count(14) << '\n';
    return 0;
}

size 4, 14 there: 0

erase(14) found 14 in its bucket and unhooked it. erase(5) found nothing and did nothing, with no error. So erasing a missing key is safe.

unordered_map: a value for every key

An unordered_map stores a value beside each key, like a price beside the name of an item. The key picks the bucket, and the value travels with it. A value can be anything a key should remember: a price, a level, or how many times something happened.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> price;
    price["tea"] = 20;
    price["bun"] = 15;
    price["tea"] = 25;
    cout << "tea " << price["tea"] << ", size " << price.size() << '\n';

    auto it = price.find("bun");
    if (it != price.end()) {
        cout << it->first << " costs " << it->second << '\n';
    }
    cout << "cake " << price["cake"] << ", size " << price.size() << '\n';

    for (const auto& [item, cost] : price) {
        cout << item << ' ' << cost << '\n';
    }
    return 0;
}

tea 25, size 2
bun costs 15
cake 0, size 3
cake 0
bun 15
tea 25

price["tea"] = 25 replaced the 20, because each key appears once. find("bun") gave an iterator to the pair, the key in first and the value in second. Reading price["cake"] added cake with the value 0, so the size went from 2 to 3. The last loop names each pair [item, cost], a structured binding, and visits the pairs in GCC 12's order.

So use [] to store a value, and find to ask without adding.

What a lookup costs: O(1) on average, O(n) at worst

A lookup computes one hash and one %, then compares the key with the keys of one bucket. GCC 12 rehashes before the load factor passes 1, so a bucket holds about one key on average. So a lookup compares a key or two, however many keys the table holds: O(1) on average. An insert and an erase cost the same, and a rehash now and then moves every key once.

The worst case is every key in one bucket. Then a lookup compares with all n keys, O(n), as a plain list would. That needs keys chosen against the hash, and lesson 04 builds such keys. A set from Module 8 takes about 20 to 40 steps for a million keys, whatever they are. It never gets down to one or two.

So a hash container gives up order and a firm worst case, and in return a lookup searches one short bucket.

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s;
    for (int x : {42, 7, 19, 7, 3}) {
        s.insert(x);
    }
    cout << s.size() << " different values:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

4 different values: 19 7 3 42

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<string> taken{"zara", "kenji", "bob", "zara1"};
    for (string want : {"maria", "zara", "bob"}) {
        string name = want;
        int n = 1;
        while (taken.count(name) == 1) {
            name = want + to_string(n);
            n++;
        }
        taken.insert(name);
        cout << want << " gets " << name << '\n';
    }
    cout << taken.size() << " names taken\n";
    return 0;
}

maria gets maria
zara gets zara2
bob gets bob1
7 names taken

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> level{{"zara", 4}, {"kenji", 2}, {"amara", 7}};
    for (string who : {"kenji", "zara", "kenji"}) {
        level[who]++;
    }
    for (string who : {"bob", "kenji"}) {
        auto it = level.find(who);
        if (it == level.end()) {
            cout << who << " has not played yet\n";
        } else {
            cout << who << " is on level " << it->second << '\n';
        }
    }
    for (const auto& [name, lv] : level) {
        cout << name << ": level " << lv << '\n';
    }
    return 0;
}

bob has not played yet
kenji is on level 4
amara: level 7
kenji: level 4
zara: level 5

#include <iostream>
using namespace std;

int main() {
    unordered_set<int> s{3, 1, 2};
    cout << s.size() << '\n';
    return 0;
}

unordered_set<string> names{"maria", "bob", "zara", "amara"};
for (const string& name : names) {
    cout << name << '\n';
}

unordered_set<int> s{10, 20, 30};
cout << s[0] << '\n';

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s{5, 3, 9, 1, 7};
    cout << "walk:";
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    unordered_set<string> banned;   // every banned word
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        // Add word to banned.
    }

    int m = 0;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string word;
        cin >> word;
        // Print word, or *** if it is banned. Put one space between two
        // words, and end the line after the last one.
    }
    return 0;
}

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    unordered_map<string, int> total;   // each player's points so far
    for (int i = 0; i < n; i++) {
        string name;
        int points;
        cin >> name >> points;
        // Add points to name's total.
    }

    // Walk total and keep the winner: more points wins, and a tie goes to
    // the name that comes first in alphabetical order. Print the winner's
    // name and total.

    return 0;
}

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_set<int> seen;   // every number the game has reached so far

    // Play the game from n: each step replaces the number by the sum of the
    // squares of its digits. Print how many steps it takes to reach 1, or
    // loops if the game never gets there.

    return 0;
}

Next, lesson 02 goes through every operation of the four hash containers, one by one, each with its cost.