Как может Hash Set подвергнуться столкновению?

Question

Если хэш-набор содержит только один экземпляр какого-либо отдельного элемента (элементов), как может произойти столкновение в этом случае?

А как может быть проблема с коэффициентом загрузки, поскольку существует только один элемент?

Пока это домашнее задание, оно не для меня.Я обучаю кого-то, и мне нужно знать, как им это объяснить.

Answer 1

Давайте предположим, что у вас есть HashSet из целых чисел, а ваша хэш-функция имеет мод 4. Целые числа 0, 4, 8, 12, 16 и т. Д. Все будут совпадать, если вы попытаетесь вставить их. (мод 4 - ужасная хеш-функция, но она иллюстрирует концепцию)

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

Теперь, при условии, что вы используете линейное зондирование (т. Е. При столкновении, используйте следующую доступную запись), как только вы достигнете 3 записей в таблице, у вас есть вероятность столкновения 0,75, а если у вас есть столкновение, в лучшем случае вы перейдете к следующей записи, но в худшем случае вам придется пройти через 3 записи, поэтому столкновение означает, что вместо прямого доступа вам потребуется в среднем линейный поиск со средним числом 2 элементов. .

Конечно, у вас есть лучшие стратегии для обработки столкновений, и, как правило, в непатологических случаях допустима нагрузка в 0,7, но после этого столкновения возрастают и производительность падает.

Answer 2

Общая идея «хэш-таблицы» (которой является «множество хеш-функций») состоит в том, что у вас есть ряд объектов, содержащих значения «ключа» (например, строки символов), которые вы хотите поместить в некоторыесортировать контейнер и затем легко находить отдельные объекты по их «ключевым» значениям, не проверяя каждый элемент в контейнере.

Можно, например, поместить значения в отсортированный массив и затем выполнитьбинарный поиск, чтобы найти значение, но поддержание отсортированного массива стоит дорого, если есть много обновлений.

Таким образом, значения ключей «хэшируются».Можно, например, сложить все значения ASCII символов, чтобы создать одно число, которое является «хешем» строки символов.(Существуют лучшие алгоритмы вычисления хеша, но точный алгоритм не имеет значения, и его легко объяснить.)

Когда вы сделаете это, вы получите число, которое для десятисимвольного символастрока будет в диапазоне от 600 до 1280. Теперь, если вы поделите это, скажем, на 500 и возьмете остаток, вы получите значение от 0 до 499. (Обратите внимание, что строка не должнабыть десятью символами - более длинные строки добавят к большим значениям, но когда вы разделите и возьмете остаток, вы все равно получите число от 0 до 499.)

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

Но (особенно с приведенным выше алгоритмом наивного хеша) вы можете иметь две разные строки с одинаковым хешем.Например, «ABC» и «CBA» будут иметь одинаковый хэш и в конечном итоге попадут в один и тот же слот в массиве.

Для обработки этого «столкновения» существует несколько стратегий, но наиболее распространенным являетсясоздать связанный список из записи массива и поместить в него различные «синонимы хеша».

Обычно вы пытаетесь сделать массив достаточно большим (и иметь лучший алгоритм вычисления хеша), чтобы минимизировать такиеколлизии, но, используя схему хеширования, невозможно полностью предотвратить коллизии.

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