C++UCS301
Linear Data StructuresC++17

Hash Tables

Hash tables map keys to buckets, giving expected constant-time lookup when hashing and load-factor management distribute keys well.

What to understand

  • Hash functions
  • Load factor
  • Separate chaining
  • Open addressing and probing

Remember this

  1. 1Collisions are unavoidable
  2. 2Average O(1), worst O(n)
  3. 3Rehash before load becomes excessive
  4. 4Equal keys must produce equal hashes

Detailed notes

A hash function converts a key into a bucket index. Because many possible keys map to fewer buckets, collisions are fundamental rather than exceptional and must be resolved correctly.

Separate chaining stores a collection per bucket. Open addressing stores every item in the table and probes alternative slots. Load factor controls expected probe or chain length and usually triggers resizing.

How it works

  1. 1Ensure equal keys always hash equally.
  2. 2Compress the hash value into the table range.
  3. 3Resolve collisions with chaining or a documented probing rule.
  4. 4Resize and rehash when the load threshold is exceeded.

Worked trace

Separate chaining collisions

Table size 5; keys 12, 7, 22
  1. 112 mod 5 = 2, so place 12 in bucket 2.
  2. 27 mod 5 = 2, so append 7 to bucket 2's chain.
  3. 322 mod 5 = 2, so append 22 to the same chain.
  4. 4Searching 22 hashes directly to bucket 2, then scans only that chain.
Result: Bucket 2: 12 → 7 → 22

Where it is used

  • Dictionaries, caches, and symbol tables
  • Frequency counting and duplicate detection
  • Database hash joins

Common mistakes

  • Assuming collisions mean the hash function is broken
  • Deleting open-addressed entries without tombstones
  • Using mutable fields as keys after insertion

Complexity analysis

OperationBestAverageWorstExtra space
SearchO(1)O(1)O(n)O(1)
InsertO(1)O(1)O(n)O(1)
DeleteO(1)O(1)O(n)O(1)

C++ implementation

C++17 reference
main.cpp

Separate-chaining hash table

Each bucket stores colliding keys in a list. Rehashing is the next production improvement.

#include <algorithm>
#include <functional>
#include <list>
#include <vector>
using namespace std;

class HashSet {
    vector<list<int>> buckets;
    size_t index(int key) const { return hash<int>{}(key) % buckets.size(); }
public:
    explicit HashSet(size_t bucketCount = 11) : buckets(bucketCount) {}
    bool contains(int key) const {
        const auto& bucket = buckets[index(key)];
        return find(bucket.begin(), bucket.end(), key) != bucket.end();
    }
    void insert(int key) {
        if (!contains(key)) buckets[index(key)].push_back(key);
    }
    void erase(int key) { buckets[index(key)].remove(key); }
};
20 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.