308
правок
Изменения
Нет описания правки
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
Для защиты от кластеризации используется Двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].
== Удаление элемента без пометок (в разработке) ==
Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на шаг назад. При этом необходимо, чтобы:
* если в цепочке встречается элемент с другим хешем, то он должен остаться на своём месте (такая ситуация может возникнуть если оставшаяся часть цепочки была добавлена позже этого элемента)
* в цепочке не должно оставаться "дырок", тогда любой элемент с данным хешем будет доступен из начала цепи
Учитывая это будем действовать следующим образом: при поиске следующего элемента цепочки будем пропускать все ячейки с другим значением хеша, копировать первый найденный в текущую ячейку и рекурсивно его удалять. Если такой следующей ячейки нет, то текущий элемент можно просто удалить, сторонние цепочки при этом не разрушатся (кстати это неверно для квадратичного поиска).
Псевдокод
delete(i)
j = i + q
while !isFree(table[j]) && table[j].key != table[i].key
if (isFree(table[j]))
table[i].makeFree()
exit
table[i] = table[j]
delete(j);
Массив считаем зацикленным
Асимптотика
==Двойное хеширование==
