Обязательно ли делать максимальный размер хэш-таблицы простым числом?
В теории прочитал, что размер хэш-таблицы должен быть простым числом, но готовые словари ЯП могут иметь чётный размер, - что я не так понял?
Ответы (1 шт):
Это требование не обязательно. Простой размер таблицы делает ситуацию чуть лучше если хеш-функция плохая. С хорошей хеш-функцией размер может быть любым.
Например, если хеш-функция выдаёт только чётные значения и хеш-таблица имеет чётный размер, нечётные корзины останутся пустыми. В более общем случае заполненость таблицы зависит от НОД(<период функции>, <размер таблицы>). Если он единица, все корзины имеют шанс заполнится, нет - нет. Так как заранее качество хеш-функции не известно (эти функции пишут программисты разной квалификации), надо так подобрать размер таблицы, чтобы был шанс на НОД = 1 (период функции и размер таблицы должны быть взаимно просты). С каким размером это сделать проще всего? С простым.
Объяснение на пальцах, но можно подвести строгую базу почему простые размеры лучше. Повторюсь, если сама хеш-функция хорошо хеширует, размер не важен.
С другой стороны, если размер таблицы - степень двойки, то вместо деления по модулю, можно обойтись применением двоичной маски. Обращение к таблице частая операция, hash & mask вместо hash % size заметно улучшает производительность.