Two-probe hashing (separate-chaining variant)

Hash to two positions, insert key in shorter of the two chains.

Double hashing

В чём заключается

$h(key, i) = (h_1(key)+i*h_2(key))\bmod{m}$

$h_1$ и $h_2$ — вспомогательные хэш-функции.

Идеально этот способ работает тогда, когда результат $\bf h_2$ является relatevily prime к размеру таблицы ($m$). Самый простой способ это сделать — сделать $m$ точной степенью двойки, а хэш-функция $h_2$ пусть выдаёт только нечётные значения.

Double hashing complexity

If load-factor is a constant, an unsuccessful search runs in O(1) time.

Cuckoo hashing (linear-probing variant)

Hash key to two positions; insert key into either position; if occupied, reinsert displaced key into its alternative position (and recur).