Почему рандомизированное зондирование не более популярно в реализациях хеш-таблицы?
Обычно каждый раз, когда Вы не используете таблицу для обеспечения расположения.
Таблицы-> данные
Отделения-> расположение
(главным образом)
4 ответа
Реализация словаря 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] полный (32-битный) хеш объекта» для заполнения ГСЧ. Python изначально заполняет j i битами из хеша. Если происходит еще одно столкновение, он берет еще 5 битов из хеша и добавляет их в микс. (Прочтите оставшуюся часть этого комментария, особенно там, где говорится о PERTURB_SHIFT .) Он продолжается таким же образом, добавляя новые биты при каждой коллизии, пока не будет использован весь хэш-код. Таким образом, Python использует приличное количество любой случайности, которую предлагает хэш-код, а код получается простым и быстрым.
Это один из лучших кодов, которые я когда-либо читал. Это описано в главе 18 Beautiful Code . Я бы сказал, что вы кое-что знаете!
Возможные причины в том, что линейное или квадратичное зондирование
- имеет одинаковую временную сложность наихудшего случая (O (размер таблицы))
- имеет одинаковую временную сложность наилучшего случая ( O (1))
- легче реализовать
- быстрее, чем хороший RNG (поскольку скорость является основным аргументом в пользу хэш-таблиц)
Но я не уверен. Вы реализовали свою собственную хеш-таблицу с другим разрешением коллизий и сравнивали их при разных обстоятельствах? Это было бы очень поучительно.
Разве у вас не возникнет проблема, что для вставок в нередко заполненную таблицу нет гарантии, что вы попадете во все элементы хеш-таблицы перед тем, как начать итерацию по повторяющимся элементам?
В результате время вставки не будет точно определено.
Одной из причин использования линейного поиска (например, двойного хеширования ) является локальность кэша. Сделав вторую функцию (повторное хеширование) добавлением небольшого целого числа, вы скорее всего попадете в ту же строку кэша. Это очень важно для больших хешей.
Цепное хеширование, вероятно, используется из-за его простоты.