Course contentsShow
← Computer Science
Lesson 408 of 2,87210. Hash TablesFree lesson

The Division Method

Using modulo operation (h(k) = k mod m) to map keys to table indices and choosing good table sizes.

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:

  • k is your key (a number)
  • m is your hash table size
  • h(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 16 only looks at the last 4 bits of k, 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.