Выбор подходящего размера таблицы для хэша

Question

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

Answer 1

Это зависит от коэффициента загрузки (точка «процент заполнения», когда таблица увеличивает свой размер и перераспределяет свои элементы). Если вы знаете, что у вас ровно 1000 записей, и это число никогда не изменится, вы можете просто установить коэффициент загрузки на 1,0 и начальный размер на 1000 для максимальной эффективности. Если вы не уверены в точном размере, вы можете оставить коэффициент загрузки по умолчанию равным 0,75 и установить начальный размер 1334 (ожидаемый размер / LF) для действительно хорошей производительности, за счет дополнительная память.

Вы можете использовать следующий конструктор для установки коэффициента загрузки:

Hashtable(int initialCapacity, float loadFactor) 

Answer 2

Вам также необходимо учитывать хеш-функцию.

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

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

Какие вещи вы хэшируете? Более подробная информация должна дать лучший совет.

Answer 3

Пусть растет. С этим размером, автоматическая обработка в порядке. Кроме этого, 2 x size + 1 - простая формула. Простые числа также хороши, но как только ваш набор данных достигнет определенного размера, реализация хэша может решить перефразировать и увеличить таблицу.

Ваши ключи определяют эффективность и, надеюсь, достаточно различимы.

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

Answer 4

Существует некоторое обсуждение этих факторов в документации для Hashtable

Answer 5

Я хотел бы повторить то, что https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany сказано выше. 1000 не кажется мне очень большим хэшем. Я использовал много хеш-таблиц такого размера в Java, не видя проблем с производительностью. И я почти никогда не слоняюсь с размером или коэффициентом загрузки.

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

В конце концов, в большинстве кодов проблема производительности не там, где вы думаете. Я стараюсь не предвидеть.

Answer 6

Дважды хорошо.

У вас нет большого набора ключей. Не беспокойтесь о трудных обсуждениях вашей реализации HashTable и переходите на 2000