Hashing · Data Structures

Arrays give O(1) access by index. What if you could turn any key — a roll number, a name — into an index? That is hashing: a hash function converts a key into an index of an array called a hash table.

Text

h(key) = key % tableSize

h(23) = 23 % 10 = 3   -> store 23 in slot 3
h(47) = 47 % 10 = 7   -> store 47 in slot 7

Search, insert and delete then take O(1) on average.

Good hash functions

A good hash function is fast, deterministic, and spreads keys uniformly over the table.

Method	Formula	Notes
Division	`h(k) = k mod m`	choose `m` prime, away from powers of 2
Multiplication	`h(k) = ⌊m × frac(k × A)⌋`, 0 < A < 1	`m` can be anything
Mid-square	square `k`, take the middle digits	old textbook method
Folding	split `k` into parts and add them	for long keys like phone numbers
Strings	`h = h × 31 + c` for each character	how Java hashes strings

Collisions

Two keys can hash to the same slot: with m = 10, both 23 and 33 go to slot 3. That is a collision, and every hash table needs a strategy for it.

Separate chaining

Each slot holds a linked list of all keys that hash there.

Separate chaining with h(k) = k mod 7. 50, 85 and 92 all hash to slot 1 and share a chain.

#include <stdio.h>
#include <stdlib.h>

#define M 7
typedef struct Node { int key; struct Node *next; } Node;
Node *table[M];

int h(int k) { return k % M; }

void insert(int k) {
    Node *n = malloc(sizeof(Node));
    n->key = k;
    n->next = NULL;
    Node **p = &table[h(k)];
    while (*p) p = &(*p)->next;       // walk to the end of the chain
    *p = n;
}

int search(int k) {
    for (Node *p = table[h(k)]; p; p = p->next)
        if (p->key == k) return 1;
    return 0;
}

int main(void) {
    int keys[] = {50, 700, 76, 85, 92, 73, 101};
    for (int i = 0; i < 7; i++) insert(keys[i]);
    for (int i = 0; i < M; i++) {
        printf("%d:", i);
        for (Node *p = table[i]; p; p = p->next) printf(" %d ->", p->key);
        printf(" NULL\n");
    }
    printf("search 92: %s, search 15: %s\n", search(92) ? "found" : "missing", search(15) ? "found" : "missing");
    return 0;
}

Output

0: 700 -> NULL
1: 50 -> 85 -> 92 -> NULL
2: NULL
3: 73 -> 101 -> NULL
4: NULL
5: NULL
6: 76 -> NULL
search 92: found, search 15: missing

Try it Yourself

Open addressing

All keys live inside the array. On a collision, probe other slots in a fixed sequence until an empty one is found.

Probing	Try slots	Weakness
Linear	h, h+1, h+2, … (mod m)	primary clustering — long runs of filled slots
Quadratic	h, h+1², h+2², h+3², …	secondary clustering; may miss empty slots
Double hashing	h, h + h₂(k), h + 2·h₂(k), …	best spread; needs h₂(k) ≠ 0

The same keys with linear probing. 85 wanted slot 1 (taken by 50) and moved to 2; 92 wanted 1 and ended in 3.

Try it

Insert keys and compare chaining, linear probing and quadratic probing:

#include <stdio.h>

#define M 7
int table[M];

void insert(int k) {
    for (int i = 0; i < M; i++) {
        int slot = (k % M + i) % M;              // linear probing
        if (table[slot] == -1) {
            table[slot] = k;
            printf("%3d -> slot %d%s\n", k, slot, i ? " (after collision)" : "");
            return;
        }
    }
    printf("table full, cannot insert %d\n", k);
}

int main(void) {
    for (int i = 0; i < M; i++) table[i] = -1;
    int keys[] = {50, 700, 76, 85, 92, 73, 101};
    for (int i = 0; i < 7; i++) insert(keys[i]);
    return 0;
}

Output

 50 -> slot 1
700 -> slot 0
 76 -> slot 6
 85 -> slot 2 (after collision)
 92 -> slot 3 (after collision)
 73 -> slot 4 (after collision)
101 -> slot 5 (after collision)

Try it Yourself

Load factor and rehashing

The load factor α = n / m (keys stored ÷ table size) measures how full the table is.

Chaining: average chain length is α, so keep α around 1.
Open addressing: performance falls sharply as α approaches 1; keep α below about 0.7.
When α gets too high, rehash: allocate a table about twice the size and reinsert every key.

Costs

	Average	Worst case
Search / insert / delete	O(1)	O(n) — everything collides

Hash tables power dictionaries in Python, unordered_map in C++, database indexes, caches and compilers' symbol tables.

Test yourself

4 questions · pick an answer to check it instantly

1
Using h(k) = k mod 11, which slot does 46 go to?
2
Which collision technique stores colliding keys in linked lists?
3
What is primary clustering?
4
A table of size 20 holds 15 keys. What is the load factor?

#Good hash functions

#Collisions

#Separate chaining

#Open addressing

#Try it

#Load factor and rehashing

#Costs

Test yourself

Good hash functions

Collisions

Separate chaining

Open addressing

Try it

Load factor and rehashing

Costs