Да, действительно, не подходит такой вариант. Тогда так — предположим, что у нас хорошая хэш функция, которая возвращает не связанные хэшкоды — тут разницы простое число или нет скорее всего не будет. А теперь представим, что хэшкоды связаны, например х, 2х, 3х, 4х и т.д. Например если ваши хэши — 2,4,6,8,10,12,14,16,18,20, то и корзины в которые они попадут будут одними и теми же.
2 % 10 = 12 % 10 = 2 и т.д.
И простое чило, выбранное в качестве делителя здесь просто помогает компенсировать плохую работу хэш функции.
Давайте я приведу пример. У вас есть словарик на 10 элементов (capacity = 10). При вычислении индекса корзины, в которую попадет элемент, мы берем остаток от деления на 10. Логично, что элемент, в зависимости от его хэша, попадет в 0..9 корзину. А теперь представьте что у хэша и размера словаря есть общие делители — например 2 (или 5). Тогда, элемент уже может попасть только в 0..4 (либо 0..1). А это значит что бОльшая часть корзин останется неиспользованными. А теперь возьмите простые числа — они делятся только на 1 и самих себя. Т.е. при емкости 11, элементы будут случайным образом всегда занимать 0..10 корзины.
Упрощенно, процент использования всех корзин можно представить как (GCD — наибольший общий делитель)
И простое чило, выбранное в качестве делителя здесь просто помогает компенсировать плохую работу хэш функции.
Упрощенно, процент использования всех корзин можно представить как (GCD — наибольший общий делитель)
По 2 вопросу — отредактировал пост. Вы правы, там не хэш, там индекс корзины который получился по формуле:
Тут, как вы понимаете результат может быть одинаковый для разных хэшей.