Для заданного хеш-значения индексы, сгенерированные линейным зондированием, следующие:
h, h+1, h+2, h+3 и т. д.
Для заданного хеш-значения индексы, сгенерированные квадратичным зондированием, следующие:
h, h+1, h+4, h+9 и т.д..
Кластер будет сформирован в случае линейного, но не в случае квадратичного.
Но почему квадратичный более эффективен, чем линейный, когда оба процесса (метода) требуют выполнения одинакового количества шагов для вставки или поиска. Спасибо!
Вы прекратите поиск в таблице, когда нажмете на пустой слот, поскольку знаете, что если вы нажмете на пустой слот, то значение, которое вы ищете, не будет в хеш-таблице. Из-за уменьшенной кластеризации вы с большей вероятностью попадете в пустой слот и прекратите поиск. Кроме того, из-за уменьшения кластеризации вы с большей вероятностью найдете пустую ячейку при вставке, что в свою очередь приведет к более быстрому поиску этого значения.
Эффективность зависит от типов кластеризации, образованных линейным зондирование и квадратичное зондирование.
Линейное зондирование формирует первичную кластеризацию, после формирования которой, чем больше становится кластер, тем быстрее он растет. Это сильно снижает производительность. Роберт Лафор привел хороший пример: это похоже на толпу, которая собирается, когда кто-то теряет сознание в торговом центре. Первые прибыли потому, что видели падение жертвы; прибывшие позже собираются, потому что им интересно, на что смотрят все остальные. Чем больше становится толпа, тем больше людей к ней притягивается.
В то время как квадратичное зондирование формирует вторичную кластеризацию. Это попытка предотвратить формирование кластеров. Идея состоит в том, чтобы исследовать более удаленные друг от друга ячейки, а не те, которые примыкают к основному хэш-сайту. Следуя аналогии, он пытается предотвратить появление первых прибывающих, чтобы не образовалась толпа. Вторичная кластеризация является более тонкой и не такой серьезной с точки зрения производительности по сравнению с первичной кластеризацией.
Из-за меньшего образования кластеров. Значения будут более разбросаны, поэтому в квадратичном случае среднее количество требуемых датчиков будет меньше.
