При открытой адресации (open addressing) все элементы лежат в самом массиве, никаких списков. При коллизии ищется следующая свободная ячейка: такой поиск называется пробированием (probing). Для сравнения с цепочками см. предыдущую тему.

Линейное пробирование: ключ 19 попадает в ячейку 5, потому что ячейки 3 и 4 заняты
Линейное пробирование: ключ 19 попадает в ячейку 5, потому что ячейки 3 и 4 заняты

Способы пробирования

Ячейка для попытки i: (h + f(i)) % m. Способ определяется выбором f(i).

  • Линейное: f(i) = i. Самое простое и дружелюбное к кэшу, но даёт первичную кластеризацию: занятые ячейки образуют блок, а блок притягивает новые коллизии.
  • Квадратичное: f(i) = i². Уменьшает первичную кластеризацию, но в зависимости от m может обойти не все ячейки.
  • Двойное хеширование: f(i) = i * h2(key). Второй хеш делает шаг зависящим от ключа. Чтобы обойти все ячейки, h2 должен быть взаимно прост с m (например, при m = 2^k шаг нечётный).
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