Почему размер хэш-таблицы обязательно простое число?

[Zefick]

Вопрос в следующем: при проектировании хэш-таблиц обычно делают так, чтобы их размер был равен простому числу. Чаще всего это числа Мерсенне. Почему так? Что будет, если задать другой размер?
Например, при модульном хэшировании (хэш-код = (ключ)mod(размер)) если таблица будет иметь размер 20 и мы вставим в неё ключи от одного до ста, то в каждый ковш попадёт ровно по 5 значений и никакого перекоса не будет. Значит и саставные числа неплохо подходят, так почему-же именно простые выбирают в качестве размера?

[pu4koff]

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

[Zefick]

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

[pu4koff]

Сообщение от Zefick

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

Я говорил про идеальную хэш-таблицу. Еще скажите, что коллизии просто необходимы и с ними лучше.
Хэш-таблица в идеале должна представлять из себя следующую структуру:
+------+----------+
| ключ | значение |
+------+----------+
| | |
+------+----------+
Одно обращение к этой таблице должно находить нужную запись и возвращать соответствующее значение, т.е. должен быть массив, у которого для навигации используется не индекс, а ключ. Наличие коллизий усложняет ситуацию, т.к. нужно реализовывать методы разрешения коллизий, что увеличивает время поиска.
Допустим коллизий у нас нет. Из-за этого автоматически "сама структура таблицы имеет мало смысла"? Если Вы имели ввиду, что более 2 коллизий плохо, то для этого какраз и выбирают в качестве размера таблицы большие простые числа, т.к. остаток от деления на них будет явно реже повторяться, а соответственно меньше коллизий будет. Или я заблуждаюсь?

[Zefick]

Сообщение от pu4koff

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

Коллизии никогда не бывают к лучшему, просто непонятно, что вы имеете ввиду, говоря об идеальной таблице. Незаполненные таблицы отличаются только размером. Невозможно создать такую таблицу, в которой коллизии заранее исключены, если только она не бесконечного размера. Просто для таблиц с цепочками коллизий рекомендуется подбирать размер так, чтобы он был в два раза меньше, чем количество ключей, которое в ней собираются хранить. Тогда на каждую цепочку придётся по 2-3 значения, но трудоёмкость поиска всё равно останется постоянной. Альтернатива - сделать бОльшую таблицу и уменьшить вероятность коллизий ценой увеличения памяти для пустых ячеек.

Сообщение от pu4koff

Допустим коллизий у нас нет. Из-за этого автоматически "сама структура таблицы имеет мало смысла"?

Да, так как методы разрешения коллизий тогда не нужны.

Сообщение от pu4koff

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

Нет, скорее всего вы не заблуждаетесь. Я как раз и хочу выяснить почему остаток от деления на простые числа будет реже повторятся. Это вовсе не очевидно. Например, если размер таблицы 250, а мы вставляем туда ключи от 0 до 1000000, то существует по 4000 ключей, которые потенциально могут находится в каждой ячейке. Это кочичесво существенно не изменится, если размер таблицы будет 251 - простое число.