HashMap
имеет два важных свойства: size
а load factor
. Я просмотрел документацию по Java, и там говорится, 0.75f
что это начальный коэффициент загрузки. Но я не могу найти фактическое использование этого.
Может ли кто-нибудь описать, каковы различные сценарии, в которых нам нужно установить коэффициент загрузки, и каковы некоторые примерные идеальные значения для разных случаев?
источник
capacity = N/0.75
чтобы избежать перефразировки, но моя первоначальная мысль была только что установленаload factor = 1
. Будут ли недостатки этого подхода? Почему бы нагрузить фактор влияетget()
иput()
эксплуатационные расходы?Начальная емкость
HashMap
дублей по умолчанию равна 16, а коэффициент загрузки равен 0,75f (т. Е. 75% от текущего размера карты). Коэффициент загрузки показывает, на каком уровнеHashMap
мощность должна быть удвоена.Например, произведение емкости и коэффициент загрузки как
16 * 0.75 = 12
. Это означает, что после сохранения 12-й пары ключ-значение вHashMap
, его емкость становится 32.источник
На самом деле, по моим расчетам, «идеальный» коэффициент загрузки ближе к log 2 (~ 0,7). Хотя любой коэффициент загрузки меньше этого, вы получите лучшую производительность. Я думаю, что .75 был, вероятно, вытащил из шляпы.
Доказательство:
Цепочки можно избежать, а предсказание ветвления можно использовать, предсказывая, пустая корзина или нет. Ведро, вероятно, пусто, если вероятность его пустоты превышает .5.
Пусть s представляет размер, а n количество добавленных ключей. Используя биномиальную теорему, вероятность того, что ведро будет пустым, равна:
Таким образом, ведро, вероятно, пусто, если есть меньше, чем
Когда s достигает бесконечности и если количество добавленных ключей таково, что P (0) = .5, то n / s быстро приближается к log (2):
источник
.75
округление до ближайшей легкой для понимания дробной частиlog(2)
и выглядит как меньшее магическое число. Я хотел бы увидеть обновление значения JDK по умолчанию с указанным комментарием над его реализацией: DЧто такое коэффициент загрузки?
Объем емкости, который должен быть исчерпан для HashMap, чтобы увеличить его емкость?
Почему коэффициент загрузки?
Коэффициент загрузки по умолчанию равен 0,75 от начальной емкости (16), поэтому 25% сегментов будут свободными до того, как произойдет увеличение емкости, и это создаст много новых блоков с новыми хэш-кодами, указывающими на них, сразу после увеличения количество ведер
Теперь, почему вы должны хранить много бесплатных корзин и как это влияет на производительность?
Если вы установите коэффициент загрузки равным 1,0, тогда может произойти что-то очень интересное.
Допустим, вы добавляете объект x в свою хэш-карту, чей hashCode равен 888, и в вашей хэш-карте корзина, представляющая хеш-код, свободна, поэтому объект x добавляется в корзину, но теперь снова скажите, добавляете ли вы еще один объект y, чей hashCode равен также 888, тогда ваш объект y будет добавлен наверняка, НО в конце сегмента ( потому что сегменты - это не что иное, как реализация, хранящая ключ, значение и следующее для реализации linkList ), теперь это влияет на производительность! Так как ваш объект y больше не присутствует в начале сегмента, если вы выполняете поиск, то время не будет равно O (1)на этот раз это зависит от того, сколько предметов находится в одном ведре. Кстати, это называется коллизией хэшей, и это даже происходит, когда ваш коэффициент загрузки меньше 1.
Корреляция между производительностью, хэш-коллизиями и коэффициентом загрузки?
Меньший коэффициент нагрузки = больше свободных ковшей = меньше шансов столкновения = высокая производительность = высокие требования к пространству.
Поправь меня, если я где-то не прав.
источник
LinkedList
называетсяAmortized Constant Execution Time
и обозначается+
какO(1)+
Из документации :
Это действительно зависит от ваших конкретных требований, для определения начального коэффициента загрузки не существует «практического правила».
источник
Для 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
источник
Если ведра переполнены, мы должны просмотреть
очень длинный связанный список.
И это своего рода победа.
Итак, вот пример, где у меня есть четыре ведра.
Пока в моем HashSet есть слон и барсук.
Это довольно хорошая ситуация, верно?
Каждый элемент имеет ноль или один элемент.
Теперь мы добавили еще два элемента в наш HashSet.
Это тоже не так уж плохо.
Каждое ведро имеет только один элемент. Так что, если я хочу знать, содержит ли это панда?
Я могу очень быстро посмотреть на ведро № 1, и это не
там и
Я знал, что это не в нашей коллекции.
Если я хочу знать, содержит ли это кошку, я смотрю на ведро
номер 3,
Я нахожу кошку, я очень быстро знаю, если это в нашем
коллекция.
Что, если я добавлю коалу, ну, это не так плохо.
Может быть, теперь вместо того, чтобы в ведро № 1, только глядя на
один элемент,
Мне нужно взглянуть на два.
Но, по крайней мере, мне не нужно смотреть на слона, барсука и
кошка.
Если я снова ищу панду, она может быть только в ведре
№ 1 и
Мне не нужно смотреть на что-то другое, кроме выдры и
коала.
Но теперь я положил аллигатора в ведро № 1, и вы можете
Может быть, увидеть, где это происходит.
Что если ведро № 1 будет становиться все больше и больше и
больше, то я в основном должен просмотреть все
эти элементы, чтобы найти
то, что должно быть в ведре № 1.
Если я начну добавлять строки в другие сегменты,
Да, проблема становится все больше и больше в каждом
одно ведро.
Как мы можем остановить наши ведра от переполнения?
Решение здесь в том, что
Там HashSet понимает, что ведра получают
слишком полный.
Это теряет это преимущество всего этого поиска
элементы.
И это просто создаст больше сегментов (как правило, вдвое больше, чем раньше) и
затем поместите элементы в правильное ведро.
Итак, вот наша основная реализация HashSet с отдельным
цепочки. Теперь я собираюсь создать «HashSet с самоизменяющимся размером».
Этот HashSet собирается понять, что ведра
становится слишком полным и
это нуждается в большем количестве ведер.
loadFactor - это еще одно поле в нашем классе HashSet.
loadFactor представляет среднее количество элементов на
ведро,
выше которого мы хотим изменить размер.
loadFactor - это баланс между пространством и временем.
Если ведра переполнены, мы изменим размер.
Это требует времени, конечно, но
это может сэкономить нам время в будущем, если ведра
немного больше пусто.
Давайте посмотрим на пример.
Вот HashSet, мы добавили четыре элемента.
Слон, собака, кошка и рыба.
На данный момент я решил, что loadFactor,
порог,
среднее количество элементов в ведре, что я в порядке
с 0,75.
Количество ведер равно buckets.length, которое равно 6, и
на данный момент наш HashSet имеет четыре элемента, поэтому
текущий размер 4.
Мы изменим размер нашего HashSet, то есть добавим больше блоков,
когда среднее количество элементов в ведре превышает
loadFactor.
Это когда текущий размер делится на buckets.length
больше, чем loadFactor.
На данный момент среднее количество элементов на ведро
4 делится на 6.
4 элемента, 6 ведер, это 0,67.
Это меньше, чем порог, который я установил в 0,75, поэтому мы
Ладно.
Нам не нужно изменять размер.
Но теперь, скажем, мы добавляем сурка.
Вудчак окажется в ведре № 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 ~ без деления, что является медленным в большинстве систем, особенно в переносных системах, где в нем нет деления. аппаратное обеспечение.
источник