HashMap имеет два важных свойства: size и load factor. Я просмотрел документацию по Java, и там написано, что 0.75f - начальный коэффициент загрузки. Но я не могу найти фактическое использование этого.
Может ли кто-нибудь описать, каковы различные сценарии, в которых нам нужно установить коэффициент загрузки, и каковы некоторые примерные идеальные значения для разных случаев?
Документация объясняет это довольно хорошо:
У экземпляра HashMap есть два параметра, которые влияют на его производительность: начальная емкость и коэффициент загрузки. Емкость - это количество ведер в хэш-таблице, а начальная емкость - это просто емкость на момент создания хеш-таблицы. Фактор нагрузки - это показатель того, насколько полная хэш-таблица может быть получена до того, как ее мощность будет автоматически увеличена. Когда количество записей в хэш-таблице превышает произведение коэффициента загрузки и текущей емкости, хеш-таблица повторно отображается (то есть внутренние структуры данных перестраиваются), так что хэш-таблица имеет примерно вдвое больше количества ковшей.
Как правило, коэффициент загрузки по умолчанию (.75) обеспечивает хороший компромисс между затратами времени и пространства. Более высокие значения уменьшают объем служебных данных, но увеличивают стоимость поиска (отражается в большинстве операций класса HashMap, включая get и put). Ожидаемое количество записей на карте и коэффициент загрузки должны учитываться при настройке начальной емкости, чтобы минимизировать количество операций перефразирования. Если начальная емкость больше максимального количества записей, деленная на коэффициент нагрузки, никаких операций перефразирования никогда не произойдет.
Как и во всех оптимизациях производительности, рекомендуется избегать преждевременной оптимизации (т.е. без жестких данных о том, где узкие места).
Начальная емкость по умолчанию для HashMap составляет 16, а коэффициент загрузки - 0,75f (т.е. 75% от текущего размера карты). Коэффициент загрузки показывает, на каком уровне емкость HashMap должна быть удвоена.
Например, продукт емкости и коэффициента загрузки как 16 * 0.75 = 12. Это означает, что после сохранения 12-й пары ключ-значение в HashMap его емкость становится 32.
Фактически, по моим расчетам, "идеальный" коэффициент нагрузки ближе к 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...
Объем мощности, который должен быть исчерпан для HashMap, чтобы увеличить его емкость?
Коэффициент нагрузки по умолчанию равен 0.75 от начальной емкости (16), поэтому 25% ковшей будут свободны до того, как произойдет увеличение емкости, и это приведет к тому, что многие новые ковши с новыми хэш-кодами, указывающие на то, что они будут существовать сразу после увеличение количества ведер.
Если вы установите коэффициент загрузки 1.0, то может произойти что-то очень интересное.
Предположим, что вы добавляете объект x в свой хэш файл, чей хэш-код равен 888, а в вашем хэш файле ведро, представляющее хэш-код, является бесплатным, поэтому объект x добавляется в ведро, но теперь снова скажу если вы добавляете еще один объект y, чей hashCode также является 888, тогда ваш объект y будет добавлен наверняка, но в конце ведра (поскольку ведра - это ничего, кроме ссылки на сохранение ключей, значение и следующий), теперь это влияет на производительность! Поскольку ваш объект y больше не присутствует в голове ведра, если вы выполняете поиск, время, которое не будет O (1), на этот раз зависит от сколько предметов находится в одном ковше. Это называется хеш-столкновением, и это даже происходит, когда ваш коэффициент загрузки меньше 1.
Более низкий коэффициент нагрузки= более свободные ковши = меньше шансов столкновения= высокая производительность = высокая потребность в пространстве.
Исправьте меня, если я где-то не прав.
В документации :
Коэффициент загрузки является мерой того, насколько полная хэш-таблица может быть получена до того, как ее емкость будет автоматически увеличена.
Это действительно зависит от ваших конкретных требований, нет "эмпирического правила" для указания начального коэффициента загрузки.
Если ведра переполнены, мы должны просмотреть
очень длинный связанный список.
И это своего рода победа.
Итак, вот пример, где у меня есть четыре ведра.
Пока в моем 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 можно реализовать с использованием некоторого соотношения или
Я бы выбрал размер таблицы n * 1.5 или n + (n → 1), это дало бы коэффициент загрузки .66666 ~ без деления, что в большинстве систем медленнее, особенно на портативных системах, где есть нет разделения на аппаратное обеспечение.
Для 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
Полное понимание коэффициента загрузки и перефразирования здесь