9
Если у меня есть набор ключей 1000, что подходит для моей таблицы хэшей, и как это определить?Выбор подходящего размера стола для хэша
A
ответ
9
Это зависит от коэффициента загрузки (точка «процента полной», в которой таблица увеличит свой размер и перераспределит ее элементы). Если вы знаете, что у вас точно 1000 записей, и это число никогда не изменится, вы можете просто установить коэффициент нагрузки 1,0 и начальный размер до 1000 для максимальной эффективности. Если вы не были уверены в точном размере, вы можете оставить коэффициент загрузки по умолчанию 0,75 и установить начальный размер до 1334 (ожидаемый размер/LF) для действительно хорошая производительность за счет дополнительной памяти.
Вы можете использовать следующий конструктор для установки коэффициента нагрузки:
Hashtable(int initialCapacity, float loadFactor)
1
3
Вы должны учитывать в хэш-функции, а также.
Одно эмпирическое правило предлагает сделать размер стола около двух, так что есть место для расширения, и, надеюсь, количество столкновений мало.
Другое эмпирическое правило состоит в том, чтобы предположить, что вы выполняете какое-то связанное с модулем хэширование, затем округлите размер таблицы до следующего наибольшего простого числа и используйте это простое число как значение по модулю.
Какие вещи вы хешируете? Более подробная информация должна давать более эффективные рекомендации.
0
Дважды хорошо.
У вас нет большого набора ключей. Не беспокойтесь о трудных дискуссиях о вашей реализации HashTable и перейдите на 2000 год.
+0
2000 не делает хороший размер, потому что он не является простым. 2001 год был бы хорош, это не просто, но, по крайней мере, даже не. Будет лучше распространять ключи в таблице. Хорошая хеш-таблица будет заботиться о хорошей хэш-функции, но большую часть времени используется размер. – ReneS 2008-11-14 19:21:34
1
Позвольте этому расти. При таком размере автоматическая обработка в порядке. Кроме того, 2 x size + 1 - простая формула. Типичные числа также хороши, но как только ваш набор данных достигнет определенного размера, реализация хэширования может решить перефразировать и развернуть таблицу.
Ваши ключи управляют эффективностью и, надеюсь, достаточно отчетливо.
Нижняя линия: задайте вопрос размера, когда у вас есть проблемы, такие как размер или низкая производительность, кроме этого: не волнуйтесь!
0
Я хотел бы повторить, что https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany сказал выше. 1000 не кажется очень большим хешем для меня. Я использовал много хэш-таблиц об этом размере в java, не видя проблем с производительностью. И я почти никогда не гадаю с размером или коэффициентом нагрузки.
Если вы запустили профайлер на свой код и определили, что хеш-таблица является вашей проблемой, тогда обязательно начните настройку. В противном случае я бы не предположил, что у вас проблемы, пока вы не уверены.
В конце концов, в большинстве случаев проблема с производительностью - это не то место, где вы думаете. Я стараюсь не предвидеть.
Предполагая, что хеш-функция хорошо себя ведет по набору ожидаемых ключей. Хозяйственная хэш-функция дома может плохо вести себя в таблице минимального размера. Для домашней работы вам придется запускать эксперименты. – 2008-11-13 03:07:03
Если хеш-функция не выполнена хорошо, встречные элементы будут храниться в том же ведре (в LinkedList). Минимальный размер стола не будет иметь никакого эффекта при работе. – 2008-11-13 03:12:33