# 8.5 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.

Chapter: Advanced Sorting & Searching · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/hashing

## Mental 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:

```cpp
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.

## C++ code: hashing.cpp

```cpp
#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:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| search / insert / delete, average | O(1) |
| search / insert / delete, worst (all keys collide) | O(n) |

Space: O(M + n)

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

## Videos

- [Hash Tables and Hash Functions](https://youtu.be/KyUTuwz_b7Q) (Computer Science Lessons): Hash functions, collisions, chaining and open addressing, with clear diagrams.

## Exam 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).

## Quick check

1. M = 7, h(k) = k % 7. Which two keys collide: 15, 22, 9, 31?
   A. 15 and 22
   B. 9 and 31
   C. 15 and 31
   D. none
   Answer: A. 15 % 7 = 1 and 22 % 7 = 1. 9 → 2 and 31 → 3.

2. Linear probing on a collision at index i tries…
   A. i − 1
   B. (i + 1) % M, then (i + 2) % M, …
   C. a random slot
   D. a new table
   Answer: B. Step forward one slot at a time, wrapping around.

3. Average search cost in a well-sized hash table?
   A. O(1)
   B. O(log n)
   C. O(n)
   D. O(n log n)
   Answer: A. The hash function jumps straight to (almost) the right place.

4. The load factor is…
   A. M / n
   B. n / M
   C. collisions / n
   D. the hash of the key
   Answer: B. Items stored divided by table size.

## Practice

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

Solution:

(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.

**Problems:**

- [Two Sum](https://leetcode.com/problems/two-sum/) (easy). Hint: For each x, look up `target − x` in an unordered_map of value → index.
- [Contains Duplicate](https://leetcode.com/problems/contains-duplicate/) (easy). Hint: Insert into an unordered_set; if the key is already there, you found a duplicate.
- [Valid Anagram](https://leetcode.com/problems/valid-anagram/) (easy). Hint: Count letters of s, subtract letters of t, check every count is 0.

## Mastery checklist

- [ ] 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).