In open addressing all elements live in the array itself, with no lists. On a collision we look for the next free cell: this search is called probing. For a comparison with chaining see the previous topic.

Linear probing: key 19 lands in cell 5 because cells 3 and 4 are taken
Linear probing: key 19 lands in cell 5 because cells 3 and 4 are taken

Probing methods

The cell for attempt i is (h + f(i)) % m. The method is defined by the choice of f(i).

  • Linear: f(i) = i. The simplest and cache-friendly, but it causes primary clustering: occupied cells form a block, and the block attracts new collisions.
  • Quadratic: f(i) = i². Reduces primary clustering, but depending on m it may not visit all cells.
  • Double hashing: f(i) = i * h2(key). A second hash makes the step depend on the key. To visit all cells h2 must be coprime to m (for example, for m = 2^k the step is odd).
python
def linear(h, m):
    return [(h + i) % m for i in range(m)]

def quadratic(h, m):
    return [(h + i * i) % m for i in range(m)]

def double(h, m, step):
    return [(h + i * step) % m for i in range(m)]

print(linear(3, 8))
print(quadratic(3, 8), len(set(quadratic(3, 8))))
print(double(3, 8, 5), len(set(double(3, 8, 5))))
print(double(3, 8, 4), len(set(double(3, 8, 4))))
text
[3, 4, 5, 6, 7, 0, 1, 2]
[3, 4, 7, 4, 3, 4, 7, 4] 3
[3, 0, 5, 2, 7, 4, 1, 6] 8
[3, 7, 3, 7, 3, 7, 3, 7] 2

The result: for m = 8 the quadratic sequence visits only 3 distinct cells, and double hashing with step = 4 only 2: a slot may not be found even in an almost empty table. step = 5 (odd) visits all 8 cells.