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

Question

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

Answer 1

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

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

Hashtable(int initialCapacity, float loadFactor) 

Answer 2

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

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

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

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

Answer 3

Об этих факторах рассказано в документации для <код> Hashtable

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

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

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