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