Разрешение столкновений: квадратичное зондирование и отдельная цепочка

Question

Итак, я провел несколько экспериментов с хеш-таблицами и различными проблемами разрешения коллизий. Я пытаюсь выяснить, что является более эффективным для выполнения поиска, хеш-таблицу, которая использует отдельное сцепление или квадратичное зондирование для разрешения коллизий. Мои результаты показывают, что раздельное сцепление выполняется быстрее, чем квадратичное зондирование, даже при небольших коэффициентах нагрузки, таких как 0,4 или 0,2. Это так или мои результаты неверны?

Answer 1

Разница в стоимости обработки между двумя подходами заключается в том, что
(с цепочкой)
- косвенность, т.е. разыменование указателя
против
(с квадратичным зондированием)
- оценка [простой, но составной] арифметической формулы
- индексация на новое место
- возможные их повторения (из-за коллизии между значением зонда и нецелевыми значениями, хранящимися в этих местах; что-то цепное не должно волновать.

Поэтому неудивительно, что сцепление происходит быстрее; Разыменование указателя - это "нативная" инструкция большинства процессоров, сравнимая (идентичная в большинстве случаев) с индексацией в массиве, оставляя арифметические операции и возможные коллизии в качестве издержек при отказе от исследования. Самая простая из формулы последовательности зондирования потребует нескольких инструкций ЦП (инициализация stepNr, обычно некоторое смещение stepNr, добавление к текущему местоположению / зондированию), что само по себе в несколько раз медленнее, чем разыменование указателя. (Возможное предостережение: пожалуйста, смотрите "Правка" вскоре после этого, так как в нем обсуждается, как цепочка может привести к большему количеству пропусков кэша на уровне ЦП, что делает его менее эффективным, чем линейное зондирование)

Преимущества квадратичной (или других форм) цепочки

• более простая логика для управления хранилищем (без динамического выделения)
• более быстрые вставки (по причине более простого хранения)
• уменьшенное требование к хранению в целом

Думая об этом компромиссе между пространством и скоростью (или также временем вставки и временем поиска) в очень общих выражениях, накладные расходы хранения цепочки (в основном для самих указателей, не учитывая возможные накладные расходы на управление кучей) используются для хранения предварительно -считанные значения [того, что было бы с зондированием] "мест зондирования". Поскольку эти вычисления легко выполняются, подход цепочки быстрее во время поиска.
Изменить (спасибо, Антс Аасма)
Предостережение в этом аргументе [о предварительно рассчитанных местоположениях] заключается в том, что на современных процессорах и их кэшах стоимость выполнения небольших вычислений может быть намного меньше, чем стоимость доступа к памяти [данных], когда кэш отсутствует. Это говорит о том, что последовательное зондирование (или, в более общем случае, с помощью зондирующих функций, которые создают местоположения, физически близкие к точке столкновения) может превзойти стратегию объединения из-за более низкого коэффициента пропусков кэша. В этом свете метод последовательного зондирования является лучшей из функций зондирования, поскольку он очень прост, но важнее, потому что он максимизирует шансы попадания в кэш. Имея это в виду, когда хеш-функция имеет хорошее распределение и коэффициент загрузки является небольшим (следовательно, с коротким / локальным путем поиска после первоначального столкновения), следует экспериментировать с линейным (или очень локальным) подходом зондирования; однако следует избегать зондирующих функций, которые обеспечивают путь поиска, который не является физически локальным.

---

Трудно конкретно прокомментировать эксперимент, упомянутый в вопросе, например, не зная размер хэша (если этот размер соответствует размеру слов / регистров в ЦП, арифметика может быть быстрее), или не зная коэффициент коллизий (предположим, хорошая, хорошо распределенная хеш-функция).
Продолжая экспериментировать с этим, было бы интересно собрать отдельный набор времени / статистики для доступа к элементам с их хэш-слотом по сравнению с теми, которые вызвали столкновение.

"Даже" в "... даже для небольших коэффициентов нагрузки..." указывает на то, что вы ожидаете, что относительное преимущество сцепления должно увеличиваться с увеличением нагрузки, следовательно, по мере того, как столкновения становятся более многочисленными. Я тоже ожидаю, что это будет иметь место.
Кроме того, увеличение нагрузки может проиллюстрировать еще один недостаток зондирования: случаи, когда циклы зондирования и / или, в более общем случае, когда нет места для установки конкретного предмета.