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

Double Hashing

Applying a second hash function to determine probe sequence, avoiding clustering patterns.

Double Hashing

You'll learn how to use a second hash function to generate better probe sequences and avoid the clustering problems that plague linear and quadratic probing.

The Core Idea

In double hashing, when a collision occurs, instead of stepping forward by a fixed amount (like linear probing's +1, +2, +3...) or a quadratic pattern (+1, +4, +9...), you calculate the step size using a second, different hash function.

Think of it like this: if your first hash function tells you where to start looking, the second hash function tells you how far to jump each time you need to try again. Different keys get different jump sizes, which spreads them out more evenly.

How It Works

  1. First hash function h₁(key) determines your starting position
  2. Second hash function h₂(key) determines your step size
  3. The probe sequence becomes: h₁(key), h₁(key) + h₂(key), h₁(key) + 2·h₂(key), h₁(key) + 3·h₂(key), etc.

All positions are taken modulo the table size to wrap around.

Why This Helps

Unlike linear probing where everyone steps by 1 (creating primary clustering) or quadratic probing where everyone follows the same +1, +4, +9 pattern (creating secondary clustering), double hashing gives each key its own unique jump pattern. Key "Alice" might jump by 7 each time, while key "Bob" jumps by 3, preventing them from repeatedly colliding even if they start near each other.

Important: The second hash function should never return zero (or you'd probe the same spot forever) and ideally should be relatively prime to the table size for best distribution.

Key Takeaway: Double hashing uses a second hash function to compute individualized probe sequences, dramatically reducing clustering and improving hash table performance during collisions.