Параметры инициализации HashMap (load / initialcapacity)

Question

Какие значения я должен передать, чтобы создать эффективные структуры HashMap / HashMap для N элементов?

В ArrayList эффективное число равно N (N уже предполагает рост в будущем). Какими должны быть параметры для HashMap? ((int) (N * 0,75d), 0,75d)? Больше? Меньше? Как влияет изменение коэффициента загрузки?

Answer 1

Что касается коэффициента загрузки, я просто приведу цитату из HashMap javadoc :

Как правило, коэффициент загрузки по умолчанию (0,75) обеспечивает хороший компромисс между временными и пространственными затратами. Более высокие значения уменьшают затраты пространства, но увеличивают стоимость поиска (отражается в большинстве операций класса HashMap, включая get и put). Ожидаемое количество записей на карте и коэффициент загрузки должны учитываться при настройке начальной емкости, чтобы минимизировать количество операций перефразировки. Если начальная емкость превышает максимальное количество записей, деленное на коэффициент загрузки, операции перефразирования никогда не будут выполняться.

Это означает, что коэффициент загрузки не должен изменяться с .75, если только у вас нет какой-либо конкретной оптимизации, которую вы собираетесь выполнить. Первоначальная емкость - это единственное, что вы хотите изменить, и установите ее в соответствии со своим значением N, то есть (N / 0.75) + 1, или чем-то в этой области. Это гарантирует, что таблица всегда будет достаточно большой, и перефразировка не произойдет.

Answer 2

Я провел несколько модульных тестов , чтобы проверить правильность этих ответов, и оказалось, что с помощью:

(int) Math.ceil(requiredCapacity / loadFactor);

в качестве начальной емкости дает то, что вы хотите для HashMap или Hashtable. Под «тем, что вы хотите» я подразумеваю, что добавление requiredCapacity элементов на карту не приведет к изменению размера массива, который он упаковывает, и массив не будет больше, чем требуется. Поскольку нагрузочная способность по умолчанию равна 0,75, инициализация HashMap работает следующим образом:

... = new HashMap<KeyType, ValueType>((int) Math.ceil(requiredCapacity / 0.75));

Поскольку HashSet фактически является просто оболочкой для HashMap, там применяется та же логика, т. Е. Вы можете эффективно создать HashSet следующим образом:

.... = new HashSet<TypeToStore>((int) Math.ceil(requiredCapacity / 0.75));

@ Ювал Адам отвечает правильно во всех случаях, кроме случаев, когда (requiredCapacity / 0.75) - это степень 2, и в этом случае он выделяет слишком много памяти.
Ответ @ NotEdible во многих случаях использует слишком много памяти, поскольку сам конструктор HashMap решает проблемы, для которых массив массивов карт должен иметь размер, равный 2.

Answer 3

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

из документов:

Создает экземпляр HashMap с достаточно высокой «начальной емкостью», чтобы он мог содержать элементы ожидаемого размера без роста ...

Answer 4

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

HashMap<Foo> myMap = new HashMap<Foo>(numberOfElements * 2);

Не стесняйтесь не соглашаться, на самом деле я бы очень хотел, чтобы эта идея была подтверждена или отброшена.

Answer 5

Ответ, который дал Ювал, верен только для Hashtable. В HashMap используются блоки двух степеней, поэтому для HashMap Zarkonnen действительно верен. Вы можете проверить это из исходного кода:

  // Find a power of 2 >= initialCapacity
  int capacity = 1;
  while (capacity < initialCapacity)
  capacity <<= 1;

Таким образом, хотя коэффициент загрузки 0,75f остается одинаковым для Hashtable и HashMap, вы должны использовать начальную емкость n * 2, где n - это количество элементов, которые вы планируете хранить в HashMap. Это обеспечит максимальную скорость получения / сдачи.

Answer 6

В большинстве случаев при инициализации List и Map безопасно создавать List или Map со следующими параметрами размера.

List<T>(numElements + (numElements / 2));
Map<T,T>(numElements + (numElements / 2));

это следует правилу .75 , а также немного экономит накладные расходы на операцию * 2, описанную выше.

Answer 7

Ссылка на исходный код HashMap поможет.

Если количество записей достигает порогового значения (емкость * коэффициент загрузки), перефразировка выполняется автоматически. Это означает, что слишком маленький коэффициент загрузки может вызывать частую перефразировку при увеличении количества записей.

Answer 8

В ArrayList эффективное число равно N (N уже предполагает рост в будущем).

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

Если, с другой стороны, вы говорите о своем значении N с учетом роста - тогда да, если вы можете гарантировать, что значение никогда не превысит это значение, тогда целесообразно вызвать такой конструктор Arraylist. И в этом случае, как указал Хэнк, аналогичным конструктором для карты будет N и 1.0f. Это должно работать разумно, даже если вы действительно превышаете N (хотя, если вы ожидаете, что это произойдет на регулярной основе, вы можете передать большее число для первоначального размера).

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

Редактировать : Юваль, вероятно, прав, что лучше оставить коэффициент загрузки около 0,75 для карты общего назначения. Коэффициент загрузки 1,0 работал бы блестяще, если бы у ваших ключей были последовательные хеш-коды (например, последовательные целочисленные ключи), но для всего остального вы, скорее всего, столкнетесь с хэш-корзинами, что означает, что поиск для некоторых элементов занимает больше времени. Создание большего количества сегментов, чем это строго необходимо, уменьшит вероятность столкновения, а это означает, что существует большая вероятность того, что элементы окажутся в своих собственных контейнерах и, следовательно, будут найдены в кратчайшие сроки. Как говорят доктора, это время против космического компромисса. Если любой из них особенно важен для вас (как показано профилировщиком, а не преждевременно оптимизирует!), Вы можете подчеркнуть это; в противном случае придерживайтесь значения по умолчанию.

Answer 9

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

CollectionSpy ( collectionpy.com ) - это новый профилировщик Java, который позволяет в мгновение ока увидеть, что HashMaps близки к необходимости перефразирования, сколько раз они были перефразированы в прошлом, и Больше. Идеальный инструмент для определения безопасных начальных аргументов емкости для конструкторов контейнеров на основе емкости.