Производительность HashMap с различной начальной мощностью и коэффициентом загрузки

Вот моя ситуация. Я использую два java.util.HashMap для хранения некоторых часто используемых данных в веб-приложении Java, работающем на Tomcat. Я знаю точное количество записей в каждом Hashmap. Ключами будут строки и ints соответственно.

Мой вопрос в том, что лучший способ установить начальную емкость и loadfactor?

Должен ли я установить емкость, равную количеству элементов, которые она будет иметь, и нагрузке до 1,0? Я бы хотел получить абсолютную лучшую производительность, не используя слишком много памяти. Однако я боюсь, что таблица не будет оптимально заполняться. С таблицей нужного размера, не будет ли ключевое столкновение, вызвав (обычно короткое) сканирование, чтобы найти правильный элемент?

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

Кроме того, если есть лучшая структура данных, чем хэш-карта для этого, я также полностью открыт для этого.

Ответ 1

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

Предположим, что загрузочная способность по умолчанию (.75), используемая HashMap, является хорошим значением в большинстве ситуаций. В этом случае вы можете использовать его и установить начальную емкость вашего HashMap на основе собственных знаний о том, сколько элементов он будет удерживать, - установите его так, чтобы начальная емкость x.75 = количество элементов (округление вверх).

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

Ответ 2

Предполагая, что ваша хеш-функция "хороша", лучше всего установить начальный размер в ожидаемое количество элементов, предполагая, что вы можете получить хорошую оценку дешево. Это хорошая идея, потому что, когда размер HashMap изменяется, он должен пересчитывать хэш-значения для каждого ключа в таблице.

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

Если вы хотите вникнуть в математику поведения хеш-таблицы: Дональд Кнут (1998). Искусство компьютерного программирования ". 3: Сортировка и поиск (2-е изд.). Addison-Wesley. С. 513-558. ISBN 0-201-89685-0.

Ответ 3

Я считаю, что лучше не возиться с настройками по умолчанию, если мне действительно не нужно.

Hotspot отлично справляется с вашими оптимизациями.

В любом случае; Я бы использовал профилировщик (Say Netbeans Profiler), чтобы сначала определить проблему.

Мы регулярно храним карты с 10000 элементами, и если у вас есть хорошая равность и реализация hashcode (и строки и целые числа делают!), это будет лучше любых изменений нагрузки, которые вы можете сделать.

Ответ 4

Предполагая (и это растяжение), что хеш-функция является простым модулем 5 целых ключей

Это не так. Из HashMap.java:

static int hash(int h) {
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

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

Обратите внимание, что количество ведер также всегда равно 2, независимо от того, какой размер вы запрашиваете.

Ответ 5

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

Если у вас больше ковшей, у вас будет меньше коллизий. Однако большее количество ведер означает разброс в памяти и, следовательно, более медленный. Обычно коэффициент нагрузки в диапазоне 0,7-0,8 является примерно оптимальным, поэтому его, вероятно, не стоит менять.

Как всегда, это, вероятно, стоит профилировать, прежде чем вы повесите трубку на микротопление.