Почему рандомизированное исследование более популярно в реализациях хеш-таблиц?

Question

Согласно различным источникам, таким как Википедия и различные веб-сайты .edu, найденные Google, наиболее распространенными способами хеш-таблицы для разрешения коллизий являются линейное или квадратичное зондирование и связывание. Рандомизированное зондирование кратко упоминается, но не уделяется много внимания. Я реализовал хеш-таблицу, которая использует рандомизированное зондирование для разрешения коллизий. Предполагая, что есть столкновение, разрешение работает следующим образом:

1. Полный (32-битный) хэш объекта используется для заполнения линейного конгруэнтного генератора случайных чисел.
2. Генератор генерирует 32-битные числа, и модуль используется для определения того, где в хеш-таблице будет выполняться поиск.

Это имеет очень приятное свойство, которое, независимо от того, сколько хеш-коллизий существует в пространстве модулей, ожидается, что время поиска и вставки будет равно O (1), если в полном 32-битном хеш-пространстве мало коллизий. Поскольку последовательность зондов является псевдослучайной, в результате столкновений с модульным пространством поведение кластеризации не возникает в отличие от линейного зондирования. Поскольку вся система имеет открытый адрес и нигде не использует связанные списки, вам не нужно выделять память для каждой вставки, в отличие от цепочки.

Кроме того, поскольку размер хеша обычно равен размеру адресного пространства (32 бита на 32-разрядных машинах), просто невозможно разместить достаточно элементов в адресном пространстве, чтобы вызвать большое количество коллизий хеша в полном объеме. -битное хеш-пространство при хорошей схеме хеширования.

Почему же тогда рандомизированное исследование такой непопулярной стратегии разрешения столкновений?

Answer 1

Одной из причин использования линейного поиска (например, double hasing ) является локальность кэша. Сделав вторую (перефразировочную) функцию добавлением небольшого целого числа, большинство шансов, что вы попадете в ту же строку кэша. Это очень важно для больших хэшей.

Цепное хеширование, вероятно, используется из-за его простоты.

Answer 2

Реализация словаря Python делает это. Очень хороший комментарий в dictobject.c говорит:

...
The first half of collision resolution is to visit table indices via this
recurrence:

    j = ((5*j) + 1) mod 2**i

For any initial j in range(2**i), repeating that 2**i times generates each
int in range(2**i) exactly once (see any text on random-number generation for
proof).
...

Конечно, для меня это выглядит как линейный конгруэнтный ГСЧ!

Обратите внимание, что полное состояние такого ГСЧ составляет всего i битов - должно быть, чтобы избежать повторного входа в записи - чтобы вы не могли осмысленно использовать "[t] he full (32- бит) хеш объекта "для затравки ГСЧ. Изначально Python содержит j с i битами из хеша. Если происходит еще одно столкновение, он берет еще 5 битов из хэша и выбрасывает их в микс. (Прочитайте оставшуюся часть этого комментария, особенно там, где говорится о PERTURB_SHIFT.) Это продолжается таким образом, добавляя больше битов при каждом столкновении, пока не будет использован весь хэш-код. Таким образом, Python использует приличное количество любой случайности, которую предлагает хеш-код, и код прост и быстр.

Это один из лучших кодов, которые я когда-либо читал. Это показано в главе 18 Красивый код . Так что я бы сказал, что вы к чему-то!

Answer 3

Возможные причины: линейное или квадратичное зондирование

• имеют одинаковую сложность времени наихудшего случая (O (размер таблицы))
• имеют одинаковую сложность времени в лучшем случае (O (1))
• проще реализовать
• быстрее, чем хороший RNG (так как скорость является основным преимуществом для хэш-таблиц)

Но я не уверен. Реализовали ли вы свою собственную хеш-таблицу с другим разрешением коллизий и сравнили их при разных обстоятельствах? Это было бы очень поучительно.

Answer 4

Я думаю, что причина, по которой случайное хеширование мало используется, состоит в том, что коллизии хеш-функции, когда небольшое значение хеш-функции вычисляется из 32-битного хеш-кода, склонны быть редкими, если в хэш-функции нет чего-то «неправильного», и в этом В этом случае существует большая вероятность того, что все 32 бита хеш-функции будут совпадать (например, потому что только часть ключа была использована для вычисления хеш-функции). Если хэш-функции приемлемы, а коэффициенты загрузки достаточно низки, линейное и квадратичное зондирование обеспечивают хорошую локализацию кэша (помните, что большинство коллизий хеш-функции будет разрешено, если рассмотреть только один дополнительный элемент, который будет как с линейными, так и с квадратичными зондами). тот, который следует за первым предположением). Линейный зонд предлагает несколько лучшую производительность в случае, когда все ключи отображаются на одно и то же значение, а иногда даже если они отображаются на небольшое количество значений. Хеширование в цепочке позволяет легко удалять предметы.

Answer 5

Не возникнет ли у вас проблема с тем, что для вставок в неполную таблицу нет гарантии, что вы попадете во все элементы хеш-таблицы, прежде чем начнете перебирать дублирующиеся элементы?

В результате время вставки не будет точно определено.