У меня есть HashMap, хранящий миллионы записей. Теперь, чтобы избежать повторного обращения каждый раз, когда он достигает порога, я хочу дать пользователю определенное значение начальной емкости и коэффициента нагрузки, чтобы повторная регистрация была минимальной. Какими должны быть мои значения для начальной емкости и коэффициента нагрузки в этом случае?Пользовательское значение Начальной емкости и LoadFactor для большой HashMap?
В общем, если вы знаете максимальное количество записей n, которые у вас есть на вашей карте, чтобы избежать изменения размера, вы можете установить capacity в n/loadFactor. Вы устанавливаете коэффициент нагрузки на некоторое значение, которое отражает ваши особые желания в пространстве компромисс пространства/времени. Если вы не знаете, какой коэффициент загрузки лучше, по умолчанию 0.75, вероятно, прекрасное место для начала.
Ключ вынос в том, что capacity является не число элементов, хэш-карта будет принимать до того, как изменение размера, а размер основного массива. Хеш-карта примет loadFactor * capacity элементов перед изменением размера. Поэтому вам нужно включить loadFactor в свои расчеты по емкости.
Чтобы быть конкретным, если вы используете по умолчанию loadFactor из 0.75 и вы знаете, ваша карта будет содержать 1,000,000 элементы, вы должны установить способность 1e6/0.75 = ~1,333,334 элементов, чтобы избежать изменения размера. Если вы не уверены в размере точного размера, это может иметь смысл включить буфер, чтобы вы могли быть разумным, избегая изменения размера.
Возможно лучше API был бы непосредственно определить параметр capacity как число элементов, которые могут быть добавлены к набору перед изменением размера, а затем конструктор делает то, что расчет необходимо установить его внутренний порог член правильно , Это будет соответствовать значению «емкости» для других структур, таких как ArrayList.
Чтобы быть более точным, если вы знаете * точное * количество записей вверх и сохраняете коэффициент загрузки по умолчанию «0.75», вы вычисляете мощность с использованием целочисленной математики, защищая от усечения, следующим образом: 'capacity = size * 4/3 + 1' – Andreas
Да, я замаскировал эту часть. Текущая реализация округляется до следующей мощности в два раза, так что выключение на 1 или 2 (или даже 100k для таблицы элементов размером 10 м) вряд ли вызовет проблему с текущей реализацией, но, конечно, вы, вероятно, не должны полагаться на том. @Andreas – BeeOnRope
@ user7487304 - это звучит как хороший (отдельный) вопрос! Почему бы тебе не спросить об этом и не ссылку на него здесь, и я выстрелю в него? – BeeOnRope
Это зависит от того, как клавиши ввода отличаются друг от друга. Может быть, они из небольшого интервала [1, ..., n], тогда это будет сложно. –
Вы будете удивлены, как мало переосмысливает. Протестируйте и измерьте значения по умолчанию, чтобы установить, действительно ли у вас проблема. – EJP
@ EJP - да, перезагрузка, как правило, является быстрой операцией, и, в частности, если вам нужно «положить» все эти значения на карте в первую очередь, это, скорее всего, будет небольшой частью общей продолжительности (просто генерируя что многие объекты занимают больше времени). Тем не менее, существуют прецеденты, в которых «среднее время« put »или« общая продолжительность выполнения »не являются правильными метриками: вы можете быть заинтересованы в более длительном времени отклика, а переименование гигантских массивов может быть большим источником выбросы, особенно. если они настроили другие причины латентности ... но java не кажется отличным языком для этого случая использования – BeeOnRope