Почему увеличение размера хеш-таблицы уменьшает количество коллизий?

Из того, что я прочитал в Интернете, есть два способа уменьшить количество столкновений:

  1. Используйте лучшую хеш-функцию
  2. Увеличьте размер вашей хеш-таблицы

Я могу понять первую причину, но не могу понять вторую.

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


hash hashtable hash-collision
person Core_Dumped    schedule 26.10.2017    source источник
comment
см. это: stackoverflow.com/questions/4980757 / [источник: javarevisited .blogspot.co.il / 2011/02 /   -  person AsfK    schedule 26.10.2017

Ответы (2)


arrow_upward
1
arrow_downward

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

Например:
Предположим, если размер массива равен 3, а значения передачи - 2 и 5
, тогда 2% 3 и 5% 3 занимают то же место, т.е. 1.
< br /> Теперь возьмем для примера размер массива 5
, тогда 2% 5 и 5% 5 занимают разные места, т.е. 2 и 0 соответственно.

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

person Ankit Jain    schedule 26.10.2017

arrow_upward
0
arrow_downward

Я понял.

Хеширование состоит из двух частей: хеш-функции и функции сжатия. Изменение размера хеш-таблицы приведет к изменению функции сжатия, что приведет к тому, что ключи будут назначены разным сегментам.

person Core_Dumped    schedule 26.10.2017