Изменения
Нет описания правки
# Предложите алгоритм удаления элемента из хеш-таблицы с открытой адресацией такой, что число занятых ячеек всегда равно числу элементов в хеш-таблице, все операции все еще должны работать за $O(1)$.
# Пусть при хешировании используется разрешение конфликтов с открытой адресацией линейным проходом, размер хеш-пространства равен $cn$, где $n$ {{---}} число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)
# Докажите, что конструкция семейства $H = \{ (ax + b) \bmod p \bmod m \}$, где случайно выбираются $a$ и $b$, $0 \le < a, b < p$, является универсальным семейством хеш-функций.
# Универсальное семейство $H$ хеш функций обладает свойством попарной независимости, если для любых двух злементов $x$ и $y$ и любых двух хеш-значений $a$ и $b$ вероятность того, что $h(x) = a$ и $h(x) = b$ есть $1/m^2 + o(1 / m^2)$ (вероятность берется по случайному выбору хеш-функции из множества $H$). Докажите, что семейство из предыдущего задания обладает этим свойством.
</wikitex>
