Метод линейного опробования (открытое хэширование)
Является наиболее простым методом обработки коллизий. При возникновении коллизии (ячейка хэш-таблице уже занята другим элементом), проверяется следующая ячейка таблицы и осуществляется поиск первой незанятой ячейки (при достижении конца таблицы реализуется переход к ее началу). Такую попытку принято называть пробой.
Метод реализует следующую последовательность действий: на первом шаге все ячейки хэш-таблицы помечаются как свободные. При добавлении нового ключа проверяется, занята ли данная ячейка. Если ячейка занята, то алгоритм осуществляет просмотр в области адреса пока не найдется свободное место.
При поиске элемента в таблице, результатами пробы могут быть следующие ситуации:
· позиция таблицы содержит элемент, который совпадает с искомым – поиск завершен успешно;
· позиция таблицы содержит элемент, который не совпадает с искомым – поиск продолжается, проверяется ячейка с следующим индексом (при достижении конца таблицы реализуется переход к ее началу), поиск продолжается до тех пор, пока не будет найден искомый ключ, не будет обнаружена пустая ячейка или не будет достигнута начальная ячейка поиска (при полностью заполненной таблице).
· позиция таблицы не содержит элемент (пустая) – поиск завершен, искомый элемент отсутствует в таблице.
На рисунке 5.14 представлен пример добавления ключа k4 с рассчитанным индексом i = 0 в хэш-таблицу. Поскольку ячейка уже занята, реализуется просмотр ячейки с индексами i = 1 (тоже занята) и i = 2 (свободна). Так как ячейка с индексом i = 2 свободна, в нее помещается искомый элемент. Теперь, при поиске ключа k4 в хэш-таблице будет проделана та же работа: рассчитан индекс i = 0, в которой отсутствует искомый элемент, проверены ячейки i = 1 (поиск продолжается) и i = 2 (элемент найден).
|
|
|
Рис. 5.15. Пример добавления и поиска элемента в хэш-таблице методом линейного опробывания
Для успешной (и быстрой) работы метода в хэш-таблице должно находиться достаточное число пустых ячеек. Поиск и добавление элемента в переполненной таблице будет занимать много времени. Из этого вытекает главный недостаток всех методов открытого хэширования – для реализации хэш-таблицы требуется зачительно больше памяти, чем необходимо для хранения всех ее элементов (для наличия пустых ячеек в таблице).
К достоинствам метода линейного опробования можно отнести простоту его реализации, в сравнении с методом цепочек.
Метод повторного хэширования
Метод подразумевает наличие на одной хэш-функции, а некоторого набора таких функций:
В таком случае, если в результате хэширования функцией 
был получен адрес уже заполненной ранее ячейки таблицы, тогда адрес определяется с помощью функции 
. Нахождение адреса производится до тех пор, пока не будет обнаружена свободная ячейка в хэш-таблице. Поиск в методе повторного хэширования реализуется с расчетом индекса тем же набором хэш-функций, вычисляемых в той же последовательности.
|
|
|
Очевидно, что все методы открытого хэширования могут столкнуться с проблемой, когда таблица будет полностью заполнена. Такие ситуации требуют расширения таблицы и ее полного перестроения. Эта процедура занимает много времени. Также перестроение хэш-таблицы рекомендуется выполнять, если ее заполненность достигает 60% - после этого поиск и добавление новых элементов в таблицу будет занимать значительное время. Именно поэтому на начальном этапе создания хэш-таблицы важно оценить количество элементов, которые в нее планируется занести.
Дата добавления: 2020-01-07; просмотров: 465; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!