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

Question

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

Мой вопрос: как лучше всего установить начальную емкость и коэффициент загрузки?

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 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, независимо от размера, который вы запрашиваете.

Answer 5

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

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

Как всегда, возможно, стоит заняться профилированием, прежде чем зацикливаться на этих настройках.