Разница в стоимости обработки между двумя подходами равна
(с цепочкой)
- косвенное обращение, то есть разыменование указателя
против
(с квадратичным зондированием)
- оценка [простой, но составной] арифметической формулы
- индексирование на новое место
- возможные их повторения (из-за коллизии между значением зонда и нецелевыми значениями, хранящимися в этих местах; не о чем беспокоиться о цепочке.
Поэтому неудивительно, что сцепление происходит быстрее ; Разыменование указателя - это «нативная» инструкция большинства процессоров, сравнимая (идентичная в большинстве случаев) с индексацией в массиве, оставляя арифметические операции и возможные коллизии в качестве издержек при отказе от исследования. Самая простая из формулы последовательности зондирования потребует нескольких инструкций ЦП (инициализация stepNr, обычно некоторое смещение stepNr, добавление к текущему местоположению / зондированию), что само по себе в несколько раз медленнее, чем разыменование указателя. (Возможное предостережение: пожалуйста, смотрите «Правка» вскоре после этого, поскольку в нем обсуждается, как цепочка может привести к большему количеству пропусков кэша на уровне ЦП, что делает его менее эффективным, чем linear probeing)
Преимущества квадратичной (или других форм) цепочки:
- более простая логика для управления хранилищем (без динамического выделения)
- более быстрые вставки (по причине более простого хранения)
- Снижение требований к хранению в целом
Думая об этом компромиссе между пространством и скоростью (или также временем вставки и временем поиска) в очень общих выражениях , накладные расходы на хранилище (в основном для самих указателей, без учета возможной кучи) - накладные расходы на управление) используется для хранения предварительно рассчитанных значений [того, что было бы с зондированием] «местоположений зондов» . Поскольку эти вычисления легко выполняются, подход цепочки быстрее во время поиска.
Редактировать (спасибо, Антс Аасма)
Предостережение в этом аргументе [о предварительно рассчитанных местоположениях] заключается в том, что на современных процессорах и их кэшах стоимость выполнения небольших вычислений может быть намного меньше, чем стоимость доступа к памяти [данных] при отсутствии кеша. Это говорит о том, что зондирование последовательно (или, в более общем случае, с помощью зондирующих функций, которые создают местоположения, физически близкие к месту столкновения) может превзойти стратегию сцепления из-за более низкого коэффициента пропусков кэша. В этом свете метод последовательного зондирования является наилучшей из функций зондирования, поскольку он очень прост, но важнее, поскольку он максимизирует шансы попадания в кэш. Имея это в виду, когда хеш-функция имеет хорошее распределение и коэффициент загрузки является небольшим (следовательно, с коротким / локальным путем поиска после первоначального столкновения) , следует экспериментировать с линейным (или очень локальным) подходом зондирования ; однако следует избегать зондирующих функций, которые обеспечивают физически не локальный путь поиска.
Трудно прокомментировать конкретно эксперимент, упомянутый в вопросе , например, не зная размера хеша (если этот размер соответствует размеру слов / регистров в ЦП, арифметика может быть быстрее) или не зная коэффициент коллизий (предположим, хорошая, хорошо распределенная хеш-функция).
Продолжая экспериментировать с этим, было бы интересно собрать отдельный набор времени / статистики для доступа к элементам с их хэш-слотом и теми, которые вызвали столкновение.
" даже " в " ... даже для небольших коэффициентов нагрузки ... " указывает на то, что вы ожидаете, что относительное преимущество сцепления будет увеличиваться с увеличением нагрузки, следовательно как столкновения становятся все более многочисленными. Я тоже ожидаю, что так и будет.
Кроме того, увеличение нагрузки может проиллюстрировать еще один недостаток исследования : случаи, когда циклы измерения и / или, в более общем случае, когда нет места для установки конкретного элемента.