1302
правки
Изменения
м
Нет описания правки
В массиве <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> — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.<ref>[[Поиск свободного места при закрытом хешировании | Поиск свободного места при закрытом хешированииРазрешение коллизий]]</ref>
== Примечания ==
