Алгоритмы и структуры данных

Метод обработки коллизий — метод открытой адресации (Линейное зондирование)

При линейном зондировании поиск в хэш-таблице осуществляется последовательно, начиная с исходного местоположения хеша. Если в случае, если локация, которую мы получаем, уже занята, то мы проверяем наличие следующей локации.

Функция, используемая для перехеширования, выглядит следующим образом: rehash(key) = (n+1)%table-size

Пусть h(x) — номер ячейки, вычисленный с помощью хэш-функции, а S — размер таблицы:

Если ячейка h(x) % S заполнена, мы пытаемся (h(x) + 1) % S
Если (h(x) + 1) % S также заполнена, то (h(x) + 2) % S
Если (h(x) + 2) % S также заполнена, то (h(x) + 3) % S и тд.

www.tgoop.com/the_algorithms/4702

6.0K viewsFeb 19, 2024 at 09:00

Метод обработки коллизий — метод открытой адресации (Линейное зондирование)

При линейном зондировании поиск в хэш-таблице осуществляется последовательно, начиная с исходного местоположения хеша. Если в случае, если локация, которую мы получаем, уже занята, то мы проверяем наличие следующей локации.

Функция, используемая для перехеширования, выглядит следующим образом: rehash(key) = (n+1)%table-size

Пусть h(x) — номер ячейки, вычисленный с помощью хэш-функции, а S — размер таблицы:

Если ячейка h(x) % S заполнена, мы пытаемся (h(x) + 1) % S
Если (h(x) + 1) % S также заполнена, то (h(x) + 2) % S
Если (h(x) + 2) % S также заполнена, то (h(x) + 3) % S и тд.

BY Алгоритмы и структуры данных