Step 1 of 5
Buckets and chaining
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. Looking up a key only searches one bucket, so with a good hash and enough buckets, 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]
std::hash<int>{}(key) gives a hash for built-in types. For ints it's often just the value itself.
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.