Вопрос по java, hashmap, load-factor – Какое значение имеет коэффициент загрузки в HashMap?

204

HashMap имеет два важных свойства:size а такжеload factor, Я просмотрел документацию по Java и там написано0.75f это начальный коэффициент загрузки. Но я не могу найти фактическое использование этого.

Может ли кто-нибудь описать, каковы различные сценарии, в которых нам нужно установить коэффициент загрузки, и каковы некоторые примерные идеальные значения для разных случаев?

Ваш Ответ

7   ответов
17

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

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased

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

В документации также говорится; "Как правило, коэффициент загрузки по умолчанию (0,75) обеспечивает хороший компромисс между временными и пространственными затратами". Так что для тех, кто не уверен, по умолчанию это хорошее правило.
24
What is load factor ?

который должен быть исчерпан для HashMap, чтобы увеличить его емкость?

Why load factor ?

Коэффициент загрузки по умолчанию составляет 0,75 от первоначальной емкости (16), поэтому 25% сегментов будут свободными до того, как произойдет увеличение емкости и усилителя; это создает много новых блоков с новыми хэш-кодами, указывающими на них, после их увеличения.

Now why should you keep many free buckets & what is the impact of keeping free buckets on the performance ?

Если вы установите коэффициент загрузки равным 1,0, то может произойти что-то очень интересное.

Допустим, вы добавляете объект x в свою хэш-карту, чей hashCode равен 888 & amp; в вашем hashmap корзина, представляющая хеш-код, свободна, поэтомуobject x добавляется в корзину, но теперь снова скажем, если вы добавляете другой объект y, чей hashCode также равен 888, тогда ваш объект y будет добавлен наверняка, НО в конце корзины (because the buckets are nothing but linkedList implementation storing key,value & next) теперь это влияет на производительность! Так как вашobject y больше не присутствует в головке ведра, если вы выполняете поиск, время не будетO(1) на этот раз это зависит от того, сколько предметов находится в одном ведре. Кстати, это называется коллизией хэшей & amp; это даже происходит, когда ваш коэффициент загрузки меньше 1.

Correlation between performance , hash collision & loading factor ?

Lower load factor = больше свободных ведер =less chances of collision = высокая производительность = высокие требования к пространству.

Correct me if i am wrong somewhere.

Я думаю, что время поиска для объекта изLinkedList упоминается какAmortized Constant Execution Time и обозначается+ какO(1)+
Вы можете добавить немного о том, как хэш-код сокращается до числа с диапазоном 1- {count bucket}, и, таким образом, это не само число блоков, а тот конечный результат алгоритма хеширования, который охватывает больший диапазон. HashCode не является полным алгоритмом хеширования, он достаточно мал, чтобы его можно было легко перерабатывать. Таким образом, не существует понятия «свободные корзины», но «минимальное количество свободных групп», поскольку вы можете хранить все свои элементы в одной корзине. Скорее, это пространство ключей вашего хеш-кода, которое равно емкости * (1 / load_factor). 40 элементов, коэффициент нагрузки 0,25 = 160 ковшей.
30

по моим расчетам, "идеальный" коэффициент загрузки ближе к log 2 (~ 0,7). Хотя любой коэффициент загрузки меньше этого, вы получите лучшую производительность. Я думаю, что .75 был, вероятно, вытащил из шляпы.

Доказательство:

Цепочки можно избежать, а предсказание ветвления можно использовать, прогнозируя, если ведро пустое или нет. Ведро, вероятно, пусто, если вероятность этого пустота превышает .5.

Пусть s представляет размер, а n количество добавленных ключей. Использование бинома Теорема, вероятность того, что ведро будет пустым:

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)

Таким образом, ведро, вероятно, пусто, если есть меньше, чем

log(2)/log(s/(s - 1)) keys

Когда s достигает бесконечности и если количество добавленных ключей таково, что P (0) = .5, тогда n / s быстро приближается к log (2):

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...
Мне очень нравится этот ответ, но я разработчик JavaEE, что означает, что математика никогда не была моей сильной стороной, поэтому я очень мало понимаю из того, что вы написали.
Математические ботаники FTW! Скорее всего.75 была округлена до ближайшей легкой для понимания дроби доlog(2)и выглядит меньше магического числа. Мне бы очень хотелось увидеть обновление значения JDK по умолчанию с указанным комментарием над его реализацией: D
133

HashMap take - 16, а коэффициент загрузки - 0,75f (т.е. 75% от текущего размера карты). Коэффициент загрузки показывает, на каком уровнеHashMap емкость должна быть удвоена.

For example произведение емкости и коэффициента нагрузки на16 * 0.75 = 12, Это означает, что после сохранения 12-го ключа & # x2013; пара значений вHashMap , его емкость становится 32.

Означает ли это, что количество ведер увеличивается на 2?
Хотя ваш ответ ясен, не могли бы вы сказать, будет ли после сохранения 12 пар ключ-значение емкость становиться равной 32 или, если добавляется 13-я запись, в это время емкость изменяется, а затем вставляется запись.
1

& gt; 1), это дало бы коэффициент загрузки 0,6666 без деления, что является медленным в большинстве систем, особенно в переносных системах, где нет разделение на оборудование.

2

очень длинный связанный список.

И это своего рода победа над этим вопросом.

Итак, вот пример, где у меня есть четыре ведра.

Пока в моем HashSet есть слон и барсук.

Это довольно хорошая ситуация, верно?

Каждый элемент имеет ноль или один элемент.

Теперь мы добавили еще два элемента в наш HashSet.

     buckets      elements
      -------      -------
        0          elephant
        1          otter
         2          badger
         3           cat

Это тоже не так уж плохо.

Every bucket only has one element . So if I wanna know, does this contain panda?

Я могу очень быстро посмотреть на ведро № 1, и это не так

там и

Я знал, что это не в нашей коллекции.

Если я хочу знать, содержит ли это кошку, я смотрю на ведро

номер 3,

Я нахожу кошку, я очень быстро знаю, есть ли она в нашем

коллекция.

Что, если я добавлю коалу, это не так уж и плохо.

             buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala 
         2          badger
         3           cat

Может быть, теперь вместо того, чтобы в ведро № 1, только глядя на

один элемент,

Мне нужно взглянуть на два.

Но, по крайней мере, мне не нужно смотреть на слона, барсука и

кошка.

Если я снова ищу панду, она может быть только в ведре

№ 1 и

Мне не нужно смотреть на что-либо, кроме выдры и

коала.

Но теперь я положил аллигатора в ведро № 1, и вы можете

Может быть, увидеть, где это происходит.

Что если ведро № 1 будет становиться все больше и больше а также

чем больше, тем больше мне нужно просматривать все

эти элементы, чтобы найти

то, что должно быть в ведре № 1.

            buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala ->alligator
         2          badger
         3           cat

Если я начну добавлять строки в другие сегменты,

Да, проблема становится все больше и больше в каждом

одно ведро.

Как мы можем остановить наши ведра от переполнения?

Решение здесь в том, что

          "the HashSet can automatically

        resize the number of buckets."

Там HashSet понимает, что ведра получают

слишком полный.

Это теряет это преимущество этого единого поиска для

элементы.

И он просто создаст больше сегментов (как правило, вдвое больше, чем раньше) и

затем поместите элементы в правильное ведро.

Итак, вот наша основная реализация HashSet с отдельным

цепочки. Теперь я собираюсь создать «HashSet» с самоизменяющимся размером.

Этот HashSet собирается понять, что ведра

становится слишком полным и

это нуждается в большем количестве ведер.

loadFactor - это еще одно поле в нашем классе HashSet.

loadFactor представляет среднее количество элементов на

ведро,

выше которого мы хотим изменить размер.

loadFactor - это баланс между пространством и временем.

Если ведра переполнены, мы изменяем размеры.

Это требует времени, конечно, но

это может сэкономить нам время в будущем, если ведра

немного больше пусто.

Давайте посмотрим на пример.

Здесь HashSet, мы добавили четыре элемента.

Слон, собака, кошка и рыба.

          buckets      elements
      -------      -------
        0          
        1          elephant
         2          cat ->dog
         3           fish
          4         
           5

В этот момент я решил, что loadFactor,

порог,

среднее количество элементов на ведро, которое я в порядке

с 0,75.

Количество ведер равно buckets.length, которое равно 6, и

на данный момент наш HashSet имеет четыре элемента, поэтому

текущий размер 4.

Мы изменим размер нашего HashSet, то есть добавим больше сегментов,

когда среднее количество элементов в ведре превышает

loadFactor.

Это когда текущий размер делится на buckets.length

больше, чем loadFactor.

На данный момент среднее количество элементов на ведро

4 делится на 6.

4 элемента, 6 ведер, что составляет 0,67.

Это меньше, чем пороговое значение, которое я установил в 0,75, поэтому мы

Хорошо.

Нам не нужно изменять размер.

Но теперь давайте скажем, что мы добавляем сурка.

                  buckets      elements
      -------      -------
        0          
        1          elephant
         2        woodchuck-> cat ->dog
         3           fish
          4         
           5

Вудчак окажется в ведре № 3.

На данный момент currentSize равен 5.

А теперь среднее количество элементов в ведре

является текущим размером, деленным на buckets.length.

То есть 5 элементов, разделенных на 6 сегментов, составл ют 0,83.

И это превышает loadFactor, который был 0,75.

Для решения этой проблемы, чтобы сделать

ведра, возможно, немного

более пустой, так что такие операции, как определение того, является ли

ведро содержит

элемент будет немного менее сложным, я хочу изменить размер

мой хэшсет

Изменение размера HashSet занимает два шага.

Сначала я удвою количество ведер, у меня было 6 ведер,

теперь у меня будет 12 ведер.

Обратите внимание, что loadFactor, который я установил на 0,75, остается прежним.

Но количество ковшей изменилось 12,

количество элементов осталось прежним, равно 5.

5, деленное на 12, составляет около 0,42, что значительно ниже нашего

коэффициент нагрузки,

так что теперь мы в порядке.

Но мы не сделали, потому что некоторые из этих элементов находятся в

неправильное ведро сейчас.

Например, слон.

Слон был в ведре № 2, потому что количество

персонажи в слоне

было 8.

У нас 6 ведер, 8 минус 6 - это 2.

Вот почему он оказался в числе 2.

Но теперь, когда у нас есть 12 ведер, 8 мод 12 это 8, так

Слон больше не принадлежит к ведру № 2.

Слон принадлежит в ведро № 8.

Как насчет сурка?

Вудчак был тем, кто начал всю эту проблему.

Сурок оказался в ведре № 3.

Потому что 9 мод 6 это 3.

Но сейчас мы делаем 9 мод 12.

9 мод 12 - 9, сурок идет к ведру № 9.

И вы видите преимущество всего этого.

Теперь ведро № 3 имеет только два элемента, тогда как раньше это было 3.

Так вот наш код,

где у нас был наш HashSet с отдельной цепочкой, что

не делали изменения размеров.

Теперь вот новая реализация, в которой мы используем изменение размера.

Большая часть этого кода одинакова,

мы все еще собираемся определить, содержит ли он

значение уже.

Если это не так, то мы выясним, какое ведро

должен идти в и

затем добавьте это к этому ведру, добавьте это к тому LinkedList.

Но теперь мы увеличиваем поле currentSize.

currentSize был полем, которое отслеживало число

элементов в нашем HashSet.

Мы собираемся увеличивать его, а затем мы будем смотреть

при средней нагрузке,

среднее количество элементов в ведре.

Мы сделаем это разделение здесь.

Мы должны сделать немного кастинга здесь, чтобы убедиться,

что мы получаем двойной.

Затем мы сравним эту среднюю нагрузку с полем.

что я установил как

0,75, когда я создал этот HashSet, например, который был

loadFactor.

Если средняя нагрузка больше, чем loadFactor,

это означает, что в каждом сегменте слишком много элементов

средний, и мне нужно заново вставить.

Итак, наша реализация метода повторной вставки

все элементы.

Во-первых, я создам локальную переменную с именем oldBuckets.

Что относится к ведрам, как они в настоящее время стоят

прежде чем я начну изменять все.

Обратите внимание, что я пока не создаю новый массив связанных списков.

Я просто переименовываю ведра как старые.

Теперь вспомните, что ведра были полем в нашем классе, я собираюсь

чтобы сейчас создать новый массив

связанных списков, но это будет иметь в два раза больше элементов

как это было в первый раз.

Теперь мне нужно сделать переустановку,

Я собираюсь пройтись по всем старым сегментам.

Каждый элемент в oldBuckets представляет собой LinkedList строк

это ведро.

Я пройду через это ведро и получу каждый элемент в этом

ведро.

А теперь я собираюсь вставить его в новые букеты.

Я получу свой хэш-код.

Я выясню, какой это индекс.

И теперь я получаю новое ведро, новый LinkedList

струны и

Я добавлю его в это новое ведро.

Напомним, что HashSets, как мы видели, являются массивами Linked.

Списки или ведра.

Самоизменяющийся размер HashSet можно реализовать с использованием некоторого соотношения или

235

документация объясняет это довольно хорошо:

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

Как и при любой оптимизации производительности, рекомендуется избегать преждевременной оптимизации (т. Е. Без точных данных о узких местах).

Другие ответы предлагают уточнитьcapacity = N/0.75 чтобы избежать перефразировки, но моя первоначальная мысль была просто поставленаload factor = 1, Будут ли недостатки этого подхода? Почему коэффициент нагрузки влияетget() а такжеput() эксплуатационные расходы?
почему более высокие значения & quot; увеличить стоимость поиска & quot ;, вы можете объяснить?
Вероятность столкновения хеша меньше, если размер карты больше. Например, элементы с хэш-кодами 4, 8, 16 и 32 будут помещены в одно и то же ведро, если размер карты равен 4, но каждый элемент получит свое собственное ведро, если размер карты больше 32. Карта с начальным размером 4 и коэффициентом загрузки 1,0 (4 сегмента, но все 4 элемента в одном сегменте) будет в этом примере в среднем в два раза медленнее, чем другой, с коэффициентом загрузки 0,75 (8 блоков, два заполненных блока - с элементом «4» и с элементами «8», «16», «32»).
Коэффициент загрузки = 1 хэш-карта с числом записей = емкость будет статистически иметь значительное количество коллизий (= когда несколько ключей создают один и тот же хэш). Когда происходит столкновение, время поиска увеличивается, так как в одном сегменте будет> 1 подходящих записей, для которых ключ должен быть индивидуально проверен на равенство. Некоторая подробная математика:preshing.com/20110504/hash-collision-probabilities
Я не слежу за тобой @atimb; Свойство loadset используется только для определения, когда увеличивать размер хранилища, верно? Как увеличение нагрузки на единицу увеличило бы вероятность коллизий хешей? - Алгоритм хеширования не знает, сколько элементов находится на карте или как часто он получает новое хранилище «корзины» и т. Д. Для любого набора объектов одинакового размера, независимо от того, как они хранятся, вы должны иметь та же вероятность повторных значений хеша ...

Похожие вопросы