Что такое первичная и вторичная кластеризация в хэше?

Question

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

Answer 1

Первичная кластеризация означает, что, если кластер существует, а начальная позиция новой записи падает в любом месте кластера, размер кластера увеличивается. Линейное зондирование приводит к этому типу кластеризации.

Вторичная кластеризация менее серьезна, две записи имеют одинаковую цепочку столкновений, только если их начальное положение одинаково. Например, квадратичное зондирование приводит к этому типу кластеризации.

Answer 2

1. Первичная кластеризация - это тенденция к схеме разрешения коллизий, такой как линейное зондирование, для создания длинных серий заполненных слотоврядом с хэш-позицией ключей.
2. Если основной хеш-индекс xпоследующие исследования x+1,x+2, x+3 и так далее, это приводит к первичной кластеризации.
3. Как только основной кластер сформируется, чем больше кластер, тем быстрее он растет. И это снижает производительность.

---

1. Вторичная кластеризация - это тенденция к схеме разрешения коллизий, такой как квадратичное зондирование, для создания длинных серий заполненных слотоввдали от хеш-позиции ключей.
2. Если основной хеш-индекс xЗонды идут в x+1, x+4, x+9,x+16,x+25 и так далее, это приводит к вторичной кластеризации.
3. Вторичная кластеризация менее серьезна с точки зрения снижения производительности, чем первичная кластеризация, и является попыткой предотвратить формирование кластеров с помощью Quadratic Probing. Идея состоит в том, чтобы исследовать более широко разделенные ячейки, а не те, которые примыкают к первичному хэш-сайту.

Answer 3

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

Вторичная кластеризация. Вторичная кластеризация относится к тенденции ключей образовывать кластеры в пробной последовательности из-за неправильного выбора вторичной хеш-функции или размера шага при двойном хешировании. При использовании двойного хеширования вторичная хеш-функция используется для определения размера шага для каждого зонда. Если размер шага не очень хорошо распределен или неправильно выбран, это может привести к вторичной кластеризации. Ключи, которые конфликтуют в одной и той же первичной позиции, могут следовать одной и той же последовательности проб и образовывать кластеры в разных слотах таблицы. Вторичная кластеризация также может повлиять на производительность поиска и эффективность структур данных на основе хэша.