277
правок
Изменения
Qqqq
,→Открытое хеширование с линейным разрешением коллизий
=== Открытое хеширование с линейным разрешением коллизий ===
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в некотором заданном порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую неё и будет записан новый элемент. Этот порядок вычисляется на лету, что Это позволяет сэкономить память на памяти для хранение указателей, требующихся в хеш-таблицах с цепочками.
Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность <tex>h_0(x)</tex>, <tex>h_1(x)</tex>, ...,<tex>h_n</tex><tex>_-</tex><tex>_1</tex><tex>(x)</tex>, где <tex>x</tex> — ключ элемента, а <tex>h_i(x)</tex> — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.
Алгоритм поиска просматривает ячейки хеш-таблицы в том же самом порядке, что и при вставке, до тех пор, пока не найдется либо элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).
Удаление элементов в такой схеме несколько затруднено. Обычно поступают так: заводят булевый флаг для каждой ячейки будем помечать каждую учейку по признаку, помечающийудалили мы из неё элемент, удален ли элемент в ней или нет. Тогда удаление элемента состоит в установке этого флага В этом случаем, удалением является установка метки {{---}} удалён, для соответствующей соответсвующей ячейки хеш-таблицы, но при этом необходимо остаётся только модифицировать процедуру поиска существующего элемента такпоиск (если удалён, чтобы она считала удалённые ячейки занятымито занято) и вставку (если удалён, а процедуру добавления — чтобы она их считала свободными и сбрасывала значение флага при добавлениито пусто) элементов.
== Примечания ==
