Какое значение имеет коэффициент загрузки в HashMap?

233

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

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

Приянк Доши
источник

Ответы:

267

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

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

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

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

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

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

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

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

На самом деле, по моим расчетам, «идеальный» коэффициент загрузки ближе к 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...
Привет мир
источник
4
Математические ботаники FTW! Вероятно, .75округление до ближайшей легкой для понимания дробной части log(2)и выглядит как меньшее магическое число. Я хотел бы увидеть обновление значения JDK по умолчанию с указанным комментарием над его реализацией: D
Декодирован
2
Мне очень нравится этот ответ, но я являюсь разработчиком JavaEE, что означает, что математика никогда не была моей сильной стороной, поэтому я очень мало понимаю из того, что вы написали lol
searchengine27
28

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

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

Почему коэффициент загрузки?

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

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

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

Допустим, вы добавляете объект x в свою хэш-карту, чей hashCode равен 888, и в вашей хэш-карте корзина, представляющая хеш-код, свободна, поэтому объект x добавляется в корзину, но теперь снова скажите, добавляете ли вы еще один объект y, чей hashCode равен также 888, тогда ваш объект y будет добавлен наверняка, НО в конце сегмента ( потому что сегменты - это не что иное, как реализация, хранящая ключ, значение и следующее для реализации linkList ), теперь это влияет на производительность! Так как ваш объект y больше не присутствует в начале сегмента, если вы выполняете поиск, то время не будет равно O (1)на этот раз это зависит от того, сколько предметов находится в одном ведре. Кстати, это называется коллизией хэшей, и это даже происходит, когда ваш коэффициент загрузки меньше 1.

Корреляция между производительностью, хэш-коллизиями и коэффициентом загрузки?

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

Поправь меня, если я где-то не прав.

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

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

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

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

Оскар Лопес
источник
В документации также говорится; «Как правило, коэффициент загрузки по умолчанию (0,75) предлагает хороший компромисс между временными и пространственными затратами». Так что для тех, кто не уверен, по умолчанию это хорошее правило.
ferekdoley
4

Для HashMap DEFAULT_INITIAL_CAPACITY = 16 и DEFAULT_LOAD_FACTOR = 0.75f это означает, что МАКС. Число ВСЕХ записей в HashMap = 16 * 0,75 = 12 . При добавлении тринадцатого элемента емкость (размер массива) HashMap будет удвоена! Прекрасная иллюстрация ответила на этот вопрос: введите описание изображения здесь изображение взято отсюда:

https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html

provisota
источник
2

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

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

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

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

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

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

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

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

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

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

Каждое ведро имеет только один элемент. Так что, если я хочу знать, содержит ли это панда?

Я могу очень быстро посмотреть на ведро № 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.

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

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

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

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

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

Я собираюсь перебрать все старые ведра.

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

это ведро.

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

ведро.

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

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

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

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

струны и

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

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

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

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

Ганеш Чоудхари Саданала
источник
1

Я бы выбрал размер таблицы n * 1,5 или n + (n >> 1), это дало бы коэффициент загрузки .66666 ~ без деления, что является медленным в большинстве систем, особенно в переносных системах, где в нем нет деления. аппаратное обеспечение.

Бретт Гринфилд
источник