The Division Method
What You'll Learn
You'll learn how to use the modulo operation to convert any key into a valid hash table index, and why picking the right table size matters.
The Core Idea
The division method is the simplest and most common hash function technique. It works by dividing your key by the table size and using the remainder as the index:
h(k) = k mod m
Where:
kis your key (a number)mis your hash table sizeh(k)is the resulting index (always between 0 and m-1)
How It Works
Think of it like organizing books on shelves. If you have 7 shelves and receive book #24, you divide: 24 ÷ 7 = 3 remainder 3. Book #24 goes on shelf 3. The modulo operation (24 mod 7 = 3) gives you exactly that remainder.
This guarantees every key maps to a valid index. If your table has 10 slots, k mod 10 always produces 0 through 9.
Choosing Good Table Sizes
Not all table sizes work equally well:
- Avoid powers of 2 (like 8, 16, 32):
k mod 16only looks at the last 4 bits ofk, ignoring most of your key's information - Prefer prime numbers (like 7, 13, 101): Primes distribute keys more evenly and reduce patterns that cause collisions
- Avoid numbers with small divisors: A table size of 100 (2×2×5×5) creates clustering
If you need ~100 slots, choose 101 (prime) instead of 100.
Key Takeaway: The division method uses h(k) = k mod m to map keys to indices, and choosing a prime number for your table size m produces better, more uniform distribution of keys.