Probing Sequence

Probing Sequence is used in Open Addressing (Hash Collision). It generates a sequence of offset indices to find the next available index from a Hash Collision.

We have the following sequence

Probing Sequence Type

Linear Probing

$$ P(x) = ax + b $$

• $a$ and $b$ are constant

Quadratic probing

$$ P(x) = ax^2 + bx + c $$

• $a$, $b$ and $c$ are sequence

Double Hashing

$$ P(x) = x \times H_2(k) $$

• $H_2(k)$ is a secondary hashing function where $k$ is the key

Pseudo random number generator

$$ P(k, x) = x \times \text{random}(H(k))$$

• Where random(seed) is a random number generator seed with $H(k)$

Cycle Problem

If we don't design our probing function carefully, we might get to a cycle. For example, if our probing function is P(x) = 4x and size = 12. We have:

• index = hash(key) = 8
• index = (8 + P(1)) % 12 = (8 + 4) % 12 = 0
• index = (8 + P(2)) % 12 = (8 + 8) % 12 = 4
• index = (8 + P(3)) % 12 = (8 + 12) % 12 = 8
• index = (8 + P(4)) % 12 = (8 + 16) % 12 = 4
• …

As a result it will keep looping between 8, 0, 4 forever and goes into a loop.

How to avoid?

Use pre-defined probing function.

Hash Table Probing Technique - Quadratic Probing (topcoder.com)