Хеш-таблица: различия между версиями
| [отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Отклонено последнее 1 изменение (Artem.musa) |
|||
Строка 62:
* [[Линейное пробирование]]: ячейки хеш-таблицы последовательно просматриваются с некоторым фиксированным интервалом ''k'' между ячейками (обычно ''k'' = 1), то есть ''i''-й элемент последовательности проб — это ячейка с номером (hash(''x'') + ''ik'') mod ''N''. Для того, чтобы все ячейки оказались просмотренными по одному разу, необходимо, чтобы ''k'' было [[Взаимная простота|взаимно-простым]] с размером хеш-таблицы.
* [[Квадратичное пробирование]]: интервал между ячейками с каждым шагом увеличивается на константу. Если размер хеш-таблицы равен степени двойки (''N'' = 2<sup>''p''</sup>), то одним из примеров последовательности, при которой каждый элемент будет просмотрен по одному разу, является:
*: hash(''x'') mod ''N'', (hash(''x'') + 1*1) mod ''N'', (hash(''x'') +
* [[Двойное хеширование]]: интервал между ячейками фиксирован, как при линейном пробировании, но, в отличие от него, размер интервала вычисляется второй, вспомогательной хеш-функцией, а значит, может быть различным для разных ключей. Значения этой хеш-функции должны быть ненулевыми и взаимно-простыми с размером хеш-таблицы, что проще всего достичь, взяв [[простое число]] в качестве размера, и потребовав, чтобы вспомогательная хеш-функция принимала значения от 1 до ''N'' — 1.
| |||