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

Question

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

Так что для записей = n существует ли оптимальный (или рекомендуемый) размер s для хеш-таблицы, который зависит от n? Допустим, скажем 2n (удвоить количество записей) или какое-то другое значение?

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

Answer 1

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

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

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

Answer 2

В Java с классом HashTable коэффициент загрузки по умолчанию (0,75) предлагает хороший компромисс между временными и пространственными затратами.

Более высокое значение коэффициента нагрузки уменьшает требования к пространству и увеличивает вероятность столкновения. Столкновение увеличивает количество времени, необходимое для выполнения get () и put (...).

Более низкое значение коэффициента загрузки увеличивает требования к пространству на диске / памяти, в результате чего много зарезервированного пространства, которое постоянно не используется. Увеличение количества бинов уменьшает вероятность столкновения.

Таким образом, коэффициент загрузки (.75) означает, что корзины HashTable заполнены на 75%. Если у вас есть 75 элементов для хранения, количество корзин в вашем HashTable должно быть 100.

Поэтому, отвечая на ваш вопрос, учитывая N в качестве количества элементов для хранения в вашей HashTable, размер вашей HashTable должен составлять примерно (1,33 * n). В некоторых ситуациях другие факторы могут ускорить изменение коэффициента нагрузки.

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Hashtable.html