Остаток от деления: как устроена хеш-таблица

Теория

Остаток от деления $k \bmod m$ — число $r$ из диапазона $0 \dots m-1$, для которого $k = q m + r$. Хеш-таблица с методом цепочек хранит $m$ корзин и кладёт ключ $k$ в корзину с номером

$$ h(k) = k \bmod m . $$

Если в одну корзину попадает несколько ключей, возникает коллизия: ключи образуют цепочку, и поиск в корзине требует перебора. Средняя длина цепочки равна коэффициенту заполнения $\alpha = n / m$, где $n$ — число ключей.

Скопления. Пусть ключи идут с шагом $s$: $k, k + s, k + 2s, \dots$ Их остатки по модулю $m$ повторяются с периодом $m / \gcd(s, m)$, поэтому ключи попадают не более чем в $m / \gcd(s, m)$ корзин. При $s = 10$ и $m = 10$ все ключи оказываются в одной корзине, а при простом $m = 11$ они распределяются равномерно. Поэтому в качестве $m$ часто выбирают простое число.

При равномерном распределении поиск, вставка и удаление выполняются в среднем за $O(1 + \alpha)$. Если все ключи собрались в одной цепочке, поиск деградирует до $O(n)$.