Изменения

Перейти к: навигация, поиск

Разрешение коллизий

114 байт добавлено, 04:00, 17 мая 2011
Литература
'' Квадратичный поиск ''
Шаг <tex>q</tex> не фиксирован, а изменяется квадратично. В качестве начального значения часто выбирается : <tex>q = 1,4,9,16...</tex>. При Соответственно при попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex>i, i+q1, i+q^24, i+q^39</tex> и так далее, пока не найдём свободную ячейку.
== Проверка наличия элемента в таблице==
Ещё при поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца. Однако, если мы придём в ту ячейку, откуда начинался поиск, то добавить элемент в текущую таблицу будет невозможно и необходимо провести операцию перехеширования.
 
==Литература==
* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест'': Алгоритмы: построение и анализ, 2-е изд
42
правки

Навигация