Какие значения следует передать для создания эффективных структур на основе HashMap/HashMap для N элементов?
В ArrayList эффективное число N (N уже предполагает рост будущего). Какими должны быть параметры для HashMap? ((int) (N * 0,75d), 0,75d)? Больше? Меньше? Каков эффект изменения коэффициента загрузки?
Что касается коэффициента загрузки, я просто приведу из HashMap javadoc:
Как правило, коэффициент загрузки по умолчанию (.75) обеспечивает хороший компромисс между затратами времени и пространства. Более высокие значения уменьшают объем служебных данных, но увеличивают стоимость поиска (отражается в большинстве операций класса HashMap, включая get и put). Ожидаемое количество записей на карте и коэффициент загрузки должны учитываться при настройке начальной емкости, чтобы минимизировать количество операций перефразирования. Если начальная емкость больше максимального количества записей, деленная на коэффициент нагрузки, никаких операций перефразирования никогда не произойдет.
Значение, коэффициент загрузки не должен изменяться с .75, если у вас нет определенной оптимизации, которую вы собираетесь делать. Первоначальная емкость - это единственное, что вы хотите изменить, и установите ее в соответствии с вашим значением N - значением (N / 0.75) + 1 или чем-то в этой области. Это гарантирует, что таблица всегда будет достаточно большой, и переименование не произойдет.
Я провел несколько тегов чтобы узнать, были ли эти ответы правильными, и оказалось, что используя:
(int) Math.ceil(requiredCapacity / loadFactor);
поскольку начальная емкость дает то, что вы хотите для a 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 Adam правильный для всех случаев, кроме тех случаев, когда (requiredCapacity / 0.75) является степенью 2, и в этом случае он выделяет слишком много памяти.
Ответ @NotEdible использует слишком много памяти во многих случаях, поскольку сам конструктор HashMap имеет дело с проблемами, требующими, чтобы массив карт имел размер, равный 2.
В guava libraries от Google есть функция, которая создает HashMap, оптимизированную для ожидаемого количества элементов: newHashMapWithExpectedSize
из документов:
Создает экземпляр HashMap с достаточно высокой "начальной емкостью", чтобы он удерживал ожидаемые элементы без роста...
Также примечательно, что наличие HashMap на малой стороне делает более вероятным хэш-коллизии, что может замедлить поиск. Следовательно, если вы действительно беспокоитесь о скорости работы карты и меньше о ее размере, возможно, стоит сделать ее слишком большой для данных, которые необходимо сохранить. Поскольку память дешевая, я обычно инициализирую HashMaps для известного количества элементов с помощью
HashMap<Foo> myMap = new HashMap<Foo>(numberOfElements * 2);
Не стесняйтесь не соглашаться, на самом деле мне очень хотелось бы, чтобы эта идея была проверена или выброшена.
Ответ, полученный Ювалем, справедлив только для 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, вы должны использовать начальную емкость n * 2, где n - количество элементов, которые вы планируете хранить в HashMap. Это обеспечит самую быструю скорость ввода/вывода.
В ArrayList эффективное число N (N уже предполагает, что будущее растет).
Эмм, нет, это не так, если я не понимаю, что вы здесь говорите. Когда вы передадите целое число в конструктор Arraylist, он создаст базовый массив точно такого размера. Если окажется, что вам нужен еще один дополнительный элемент, ArrayList должен будет изменить размер базового массива при следующем вызове add(), в результате чего этот вызов займет намного больше времени, чем обычно.
Если, с другой стороны, вы говорите о своем значении N с учетом роста - тогда да, если вы можете гарантировать, что значение никогда не будет превышать это, тогда вызов такого конструктора Arraylist является подходящим. И в этом случае, как указал Хэнк, аналогичным конструктором для карты будет N и 1.0f. Это должно выполняться разумно, даже если вы превысите N (хотя, если вы ожидаете, что это произойдет на регулярной основе, вы можете захотеть передать большее количество для начального размера).
Коэффициент загрузки, если вы не знали, является точкой, в которой карта будет увеличивать свою емкость, в виде доли от общей емкости.
Изменить: Юваль, вероятно, прав, что лучше оставить фактор нагрузки около 0,75 для карты общего назначения. Коэффициент загрузки 1,0 будет блестящим образом выполняться, если ваши ключи имеют последовательные хэш-коды (такие как последовательные целочисленные ключи), но для чего-либо еще вы, скорее всего, столкнетесь с конфликтами с хэш-ковши, что означает, что поисковые запросы занимают больше времени для некоторых элементов. Создание большего количества ведер, чем это строго необходимо, уменьшит вероятность столкновения, а это означает, что у них больше шансов на то, что элементы будут в своих ведрах и, следовательно, будут восстановлены в кратчайшие сроки. Как говорят документы, это время против космического компромисса. Если это особенно важно для вас (как показано профилировщиком, а не преждевременной оптимизации!), Вы можете подчеркнуть это; в противном случае придерживайтесь значения по умолчанию.
Обращение к исходному коду HashMap поможет.
Если количество записей достигает порогового значения (коэффициент загрузки * мощности), повторная обработка выполняется автоматически. Это означает, что слишком малый коэффициент загрузки может часто повторяться при увеличении количества записей.
В большинстве случаев безопасно инициализировать List и Map, чтобы сделать List или Map со следующими параметрами размера.
List<T>(numElements + (numElements / 2));
Map<T,T>(numElements + (numElements / 2));
это следует за правилом .75, а также сэкономит немного накладных расходов над операцией * 2, описанной выше.
Для очень больших HashMaps в критических системах, где неправильная ошибка начальной загрузки может быть очень проблематичной, вам может понадобиться эмпирическая информация, чтобы определить, как наилучшим образом инициализировать вашу карту.
CollectionSpy (collectionspy.com) - это новый профилировщик Java, который позволяет вам мгновенно увидеть, что HashMaps близок к необходимости перефразирование, сколько раз они были перефразированы в прошлом и многое другое. Идеальный инструмент для определения безопасных аргументов начальной емкости для конструкторов контейнеров на основе емкости.