Параметры инициализации 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

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

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

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

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

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

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

Answer 8

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

(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)); 

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

Answer 9

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

из документации:

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