Метод открытой адресации

Видите ли вы недостатки в методе цепочек?
Тимофей: Другой способ разрешения коллизий — метод открытой адресации.
image
Добавление ключа:
  1. Вычисляем значение хеш-функции.
  2. Если соответствующая ячейка свободна, записываем туда данные.
  3. Иначе пробуем записать в следующую по порядку свободную ячейку. Дойдя до последнего индекса, переходим к началу таблицы.
Алгоритм поиска элемента:
  1. Вычисляем значение хеш-функции.
  2. Если искомый элемент в этой ячейке, поиск окончен.
  3. Иначе продолжаем искать в следующих по порядку ячейках, пока не встретится пустая.
Удаление ключа чуть сложнее. Нельзя просто удалить данные из ячейки, ведь следом могут быть записаны ключи, которые попали не в свою ячейку. Тогда при операции поиска алгоритм остановится, встретив пустую ячейку. И данные, которые на самом деле присутствуют, не будут найдены.
Гоша: И что же делать?
Тимофей: Решение — помечать удаляемые ячейки специальным значением. Например, “deleted”.
Тогда при вставке нужно проверять “deleted” и вставлять элемент на его место, встретив “deleted”, продолжать алгоритм.
Есть ли недостатки у этого метода?
Гоша: А как справиться с этой проблемой?
Тимофей: Если количество таких ячеек превышает заданный лимит, нужно перезаписать данные заново в таблицу, но уже без ячеек, помеченных символом “deleted”.
Гоша: Да, логично. Я себя уже чувствую специалистом по хеш-таблицам!
Тимофей: Рано тебя посетило это чувство.
Есть ли недостатки у рассмотренного метода?
Предположим, в таблице рядом записаны kk ключей. Тогда при попытке поиска или записи нужно проделать O(k)O(k) операций. Чем больше кластер, тем менее эффективным будет использование хеш-таблицы.
image
Гоша: Можно ли как-то с этим бороться?
Тимофей: Да. Но проблема в том, что на каждом шаге при попытке записи мы пойдём в следующую ячейку.
То есть h(k,i)=h(k)+ih(k, i) = h(k) + i — плохая стратегия.
Гоша: А какая хорошая, идти в предыдущую ячейку?
Тимофей: Нет. Вообще последовательность ячеек, куда мы хотим вставить элемент, — это перестановка чисел от 0 до m−1m-1, где mm — размер таблицы.
Нужно подобрать такую последовательность чисел, которая перебирала бы все значения, но не по порядку. Сделав mm проб, нужно попробовать вставить элемент в каждую из mm ячеек.
Рассмотренный алгоритм можно улучшить.
h(k,i)=h(k)+c⋅ih(k, i) = h(k) + c \cdot i.
То есть будем ходить с некоторым шагом cc.
Гоша: А cc может быть любое?
Тимофей: Не любое, cc и mm должны быть взаимно простые. Иначе будем ходить по одним и тем же ячейкам.
Например, если c=2c = 2 и mm — чётное число, то в ячейки с нечётными номерами мы никогда не попадём.
Рита: Можно, например, брать в качестве m степень двойки, а в качестве cc — простое число.
Варианты, в которых мы делаем единичный шаг и шаг cc, относятся к методам линейного пробирования.
Есть ли недостатки у методов линейного пробирования?
Рассмотрим метод квадратичного пробирования.
h(k,i)=h(k)+c1⋅i+c2⋅i2h(k, i) = h(k) + c_1 \cdot i + c_2 \cdot i ^ 2
В этом случае разные итерации пробирования двух элементов шагают по-разному.
Гоша: А как подобрать коэффициенты c1c_1 и c2c_2, чтобы покрыть все ячейки, сделав mm проб?
Рита: Можно вот так: h(k,i)=h(k)+i2+i22\displaystyle h(k, i) = h(k) + \frac{i}{2} + \frac{i^2}{2}.
Тимофей: h(k,i)=h(k)+i⋅(i+1)2\displaystyle h(k, i) = h(k) + \frac{i\cdot(i + 1)}{2} .
Кто из ребят прав?
Есть ли недостатки у метода квадратичного пробирования?
Алла: Как же с этим бороться?
Тимофей: Поможет двойное хеширование.
h(k,i)=h1(k)+h2(k)⋅ih(k, i) = h_1(k) + h_2(k) \cdot i
Будем ходить с шагом, индивидуальным для ключа. Даже если h1h_1 для двух ключей совпадёт, то вероятность совпадения h2h_2 для них очень маленькая.
Гоша: А как в этом случае обеспечить перебор всех ячеек?
Тимофей: Шаг, как и ранее, должен быть взаимно простым с размером таблицы. h2h_2 должна быть нечётной, а h1h_1 можно брать произвольной.
Время работы хеш-таблицы с использованием метода открытой адресации:
В лучшем случае: O(1)O(1).
В худшем: O(n)O(n).
В среднем: O(11−α)\displaystyle O\left (\frac{1}{1 - \alpha} \right ) , где α\alpha — коэффициент заполненности таблицы.
Решите задачи F, G: https://contest.yandex.ru/contest/19095/problems/F