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

Question

Основная проблема с линейным зондированием - кластеризация, многие последовательные элементы образуют группы, и для поиска свободного слота или поиска элемента начинает требоваться время.

Почему последовательный элемент из группы и как это влияет на время поиска свободного слота?

Answer 1

Требуемый результат хеш-функции состоит в том, чтобы разбросать, скажем, 100 строк случайным образом, скажем, на 200 "голубых слотов". В случае коллизии, т. Е. Уже занятого интервала, линейное сканирование будет искать следующий незанятый интервал, делая сразу группу по меньшей мере из двух (она также может соединять две группы). Когда происходит столкновение с кластером, линейное зондирование добавляет кластер одним новым ключом, исходная позиция которого должна была быть где-нибудь в кластере.

Многие быстро оценивающие хэш-функции страдают от проблемы неравномерного распределения ключей. Когда входные данные также распределяются неравномерно, эти два явления подчеркивают друг друга и в случае линейного зондирования могут привести к значительному количеству ключей для кластеризации. По сути, это сделает не только вставку, но и поиск проблемы O(n) вместо O(1).

Answer 2

Это не тот случай, когда всегда последовательные элементы будут образовывать кластеры.

Противоречивый пример

Предположим, у вас есть хеш-таблица 100 записи: и хеш-функция:

h(x) = x mod 100;

Скажем, вы вставляете элементы:

948,748,172,973,473,572,72

Сформированные кластеры будут:

кластер 1: 948(position 48),748(position 49)(явно элементы не являются последовательными)

кластер 2: 172(position 72),973(position 73),473(position 74),572(position 75),72(position 76)(явно элементы не последовательные).

ДА, кластеризация влияет на время, чтобы найти свободный слот, потому что в linear probingмы сканируем хеш-таблицу, чтобы найти следующий свободный слот, поэтому из-за кластеров линейное сканирование займет больше времени из-за сформированных кластеров, но только из-за линейного сканирования в случае столкновения.