8.5 ~45 min medium

Hashing Basics

A hash function turns a key into an array index, so search is O(1) on average. Collisions, separate chaining, linear probing and the load factor.

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental model

A library puts every book on a shelf chosen by the first letter of the author’s surname. To find “Tamassia” you walk straight to shelf T. You don’t search the whole library. That shelf rule is a hash function.

The idea

A hash function h(key) turns a key into an index of an array (the hash table) of size M. A common simple one:

int h(int key) { return key % M; }   // M is often a prime

Store the key at table[h(key)]; to search, look in the same place. No scanning, so it is O(1) on average.

A good hash function is fast and spreads keys evenly.

Collisions

Two keys can map to the same index (14 and 21 both give 0 when M = 7). Two classic fixes:

Separate chaining: each slot holds a linked list. Colliding keys join the list.
Open addressing (linear probing): if the slot is taken, try the next one, (h + 1) % M, then (h + 2) % M, … until an empty slot. Searching stops at an empty slot.

Load factor

α = n / M: how full the table is. As α grows, chains get longer and probe runs get longer. With probing, α must stay below 1 (keep it under about 0.7). With chaining, the table can still work above 1, but it gets slower.

In C++, std::unordered_map and std::unordered_set are hash tables.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Insert 21 and 28. Both land in bucket 0 with 14 and join its chain.

Loading visualizer…

Insert 21; slot 0 is taken, so it probes to slot 1. Then search for a key that is missing.

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

hashing.cpp55 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
#include <list>
#include <vector>
using namespace std;

const int M = 7;
int h(int key) { return key % M; }

struct ChainTable {                           // separate chaining
    vector<list<int>> table = vector<list<int>>(M);
    void insert(int key) { table[h(key)].push_back(key); }
    bool search(int key) const {
        for (int k : table[h(key)]) if (k == key) return true;
        return false;
    }
};

struct ProbeTable {                           // open addressing, linear probing
    int table[M];
    ProbeTable() { for (int& x : table) x = -1; }
    bool insert(int key) {
        for (int i = 0; i < M; i++) {
            int idx = (h(key) + i) % M;
            if (table[idx] == -1) { table[idx] = key; return true; }
        }
        return false;
    }
    int search(int key) const {               // index, or -1
        for (int i = 0; i < M; i++) {
            int idx = (h(key) + i) % M;
            if (table[idx] == -1) return -1;   // an empty slot ends the search
            if (table[idx] == key) return idx;
        }
        return -1;
    }
};

int main() {
    int keys[] = {14, 23, 12, 21, 30};
    ChainTable c;
    ProbeTable p;
    for (int k : keys) { c.insert(k); p.insert(k); }

    cout << "chaining:\n";
    for (int i = 0; i < M; i++) {
        cout << "  " << i << ":";
        for (int k : c.table[i]) cout << " " << k;
        cout << "\n";
    }
    cout << "linear probing: ";
    for (int x : p.table) cout << (x == -1 ? string("_") : to_string(x)) << " ";
    cout << "\n";
    cout << "search 21: chain " << (c.search(21) ? "found" : "missing") << ", probe index " << p.search(21) << "\n";
    cout << "search 5:  chain " << (c.search(5) ? "found" : "missing") << ", probe index " << p.search(5) << "\n";
}

#include <iostream>
#include <list>
#include <vector>
using namespace std;

const int M = 7;
int h(int key) { return key % M; }

struct ChainTable {                           // separate chaining
    vector<list<int>> table = vector<list<int>>(M);
    void insert(int key) { table[h(key)].push_back(key); }
    bool search(int key) const {
        for (int k : table[h(key)]) if (k == key) return true;
        return false;
    }
};

struct ProbeTable {                           // open addressing, linear probing
    int table[M];
    ProbeTable() { for (int& x : table) x = -1; }
    bool insert(int key) {
        for (int i = 0; i < M; i++) {
            int idx = (h(key) + i) % M;
            if (table[idx] == -1) { table[idx] = key; return true; }
        }
        return false;
    }
    int search(int key) const {               // index, or -1
        for (int i = 0; i < M; i++) {
            int idx = (h(key) + i) % M;
            if (table[idx] == -1) return -1;   // an empty slot ends the search
            if (table[idx] == key) return idx;
        }
        return -1;
    }
};

int main() {
    int keys[] = {14, 23, 12, 21, 30};
    ChainTable c;
    ProbeTable p;
    for (int k : keys) { c.insert(k); p.insert(k); }

cout << "chaining:\n";
    for (int i = 0; i < M; i++) {
        cout << "  " << i << ":";
        for (int k : c.table[i]) cout << " " << k;
        cout << "\n";
    }
    cout << "linear probing: ";
    for (int x : p.table) cout << (x == -1 ? string("_") : to_string(x)) << " ";
    cout << "\n";
    cout << "search 21: chain " << (c.search(21) ? "found" : "missing") << ", probe index " << p.search(21) << "\n";
    cout << "search 5:  chain " << (c.search(5) ? "found" : "missing") << ", probe index " << p.search(5) << "\n";
}

Expected output

chaining:
  0: 14 21
  1:
  2: 23 30
  3:
  4:
  5: 12
  6:
linear probing: 14 21 23 30 _ 12 _ 
search 21: chain found, probe index 1
search 5:  chain missing, probe index -1

05Complexity

search / insert / delete, average	O(1)
search / insert / delete, worst (all keys collide)	O(n)
Extra space	O(M + n)

Keep the load factor α = n / M low (under ~0.7 for probing) so chains and probe runs stay short.

06Watch

Hash Tables and Hash Functions

Computer Science Lessons · 13:53

Why this one: Hash functions, collisions, chaining and open addressing, with clear diagrams.

Watched

07Exam lens

Likely questions

What is hashing? What makes a good hash function?
Insert 14, 23, 12, 21, 30 into a table of size 7 with h(k) = k mod 7 using (a) chaining, (b) linear probing.
What is a collision? Describe two ways to resolve it.
What is the load factor and why does it matter?

Common mistakes

With linear probing, stopping a search at a slot holding a different key. Only an empty slot means "not found".
Forgetting to wrap around with % M when probing.
Claiming hashing is always O(1). The worst case is O(n).

08Quick check

1.M = 7, h(k) = k % 7. Which two keys collide: 15, 22, 9, 31?
2.Linear probing on a collision at index i tries…
3.Average search cost in a well-sized hash table?
4.The load factor is…

09Practice

🟢 Trace by hand

M = 7, h(k) = k % 7. Insert 14, 23, 12, 21, 30 with (a) chaining and (b) linear probing.

Show answer

(a) Chaining: bucket 0 → 14, 21 · bucket 2 → 23, 30 · bucket 5 → 12

(b) Probing: 14 → 0 · 23 → 2 · 12 → 5 · 21 → 0 taken → 1 · 30 → 2 taken, 3 free → 3

Table: 14 21 23 30 _ 12 _

🟡 Implement it

Write a string hash h(s) = (sum of s[i] × 31^i) % M and use it in a chained table of words. Then count word frequencies with std::unordered_map<string, int>.

Hint

Compute it like Horner: h = (h * 31 + c) % M for each character.

🔴 Solve problems

Two Sum easyleetcode.com
Hint
For each x, look up target − x in an unordered_map of value → index.
Contains Duplicate easyleetcode.com
Hint
Insert into an unordered_set; if the key is already there, you found a duplicate.
Valid Anagram easyleetcode.com
Hint
Count letters of s, subtract letters of t, check every count is 0.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

I can explain hashing with a hash function and a table.
I can insert keys by hand with chaining and with linear probing.
I can explain collisions and the load factor.
I know average O(1) and worst O(n).

0/4 ticked

My notes

View as Markdown · Chapter cheat sheet