Изменения

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

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

1 байт добавлено, 20:02, 6 июня 2012
Стратегии поиска
'' Последовательный поиск ''
[[Файл:hashtables1.png|thumb|280px380px|right|Последовательный поиск, частный случай линейного поиска.]]
При попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex>i+1, i+2, i+3</tex> и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.
'' Линейный поиск ''
[[Файл:hashtables2.png|thumb|280px380px|leftright|Линейный поиск с шагом q.]]
Выбираем шаг <tex>q</tex>. При попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex>i+(1 \cdot q), i+(2 \cdot q), i+(3 \cdot q)</tex> и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.
'' Квадратичный поиск ''
[[Файл:hashtables3.png|thumb|280px380px|right|Квадратичный поиск.]]
Шаг <tex>q</tex> не фиксирован, а изменяется квадратично: <tex>q = 1,4,9,16...</tex>. Соответственно при попытке добавить элемент в занятую ячейку <tex>i</tex> начинаем последовательно просматривать ячейки <tex> i+1, i+4, i+9</tex> и так далее, пока не найдём свободную ячейку.
Анонимный участник

Навигация