Step 1 of 5

Buckets and chaining

You've used std::unordered_map and std::unordered_set for O(1) lookups. This module builds one yourself, so you know what's going on inside, why it's fast, and when it isn't.

A hash table stores items in an array of buckets. A hash function turns a key into a number, and hash % bucket_count picks the bucket. To look up a key, you compute its bucket and search only that bucket. With a good hash and enough buckets, each bucket holds just a few items, so lookup is O(1) on average.

Two keys can land in the same bucket: a collision. Separate chaining handles that by making each bucket a small list:

bucket 0: [16] -> [48]
bucket 1: [ ]
bucket 2: [2] -> [34]

#include <iostream>
#include <list>
#include <string>
#include <vector>

int main() {
    const std::size_t buckets = 5;
    std::vector<std::list<std::string>> table(buckets);

    auto bucket_of = [&](const std::string& word) {
        std::size_t h = 0;
        for (char c : word) h = h * 31 + (unsigned char)c;   // a simple string hash
        return h % buckets;
    };

    for (const char* w : {"cat", "dog", "owl", "bee", "ant", "yak"}) {
        table[bucket_of(w)].push_back(w);
    }
    for (std::size_t b = 0; b < buckets; b++) {
        std::cout << "bucket " << b << ":";
        for (const auto& w : table[b]) std::cout << " " << w;
        std::cout << "\n";
    }
    std::cout << "owl is in bucket " << bucket_of("owl") << "\n";
}

bucket 0: bee yak
bucket 1:
bucket 2: cat
bucket 3: owl ant
bucket 4: dog
owl is in bucket 3

How it works

The hash function mixes every character into one number. Any function works as long as the same key always gives the same hash; a good one also spreads different keys evenly across the buckets.
% buckets turns that big number into a valid bucket index.
To look up "owl", you hash it, go to its bucket, and search only that short list, never the whole table.
Two words sharing a bucket, like bee and yak, is fine: the list holds both, and lookups compare the actual keys. Bucket 1 being empty is fine too.

For built-in types, std::hash<T>{}(key) gives you a ready-made hash. For int it's often just the value itself.

Your task

IntSet has 16 buckets, each a std::list<int>.

insert: find the bucket with std::hash<int>{}(key) % buckets_.size(). If the key is already in that list, return false; otherwise push_back it, increase size_, and return true.
contains: search the same bucket.

std::find(list.begin(), list.end(), key) from <algorithm> searches a list for you.

Your turn: write IntSet with 16 buckets (a std::vector<std::list<int>>): bool insert(int) (false if already present), bool contains(int) const, and std::size_t size() const.

Next: Load factor and rehashing