Выбор начальной емкости HashSet с ожидаемым количеством уникальных значений и вставок

Question

Хорошо, вот моя ситуация:

У меня есть массив состояний, который может содержать дубликаты. Чтобы избавиться от дубликатов, я могу добавить их в набор.

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

По поиску, я придумал:

String[] allStates = getAllStates();
Set<String> uniqueStates = new HashSet<String>(allStates.length, 0.75);

Проблема в том, что все состояния могут содержать от 1 до 5000 состояний. Таким образом, набор будет иметь емкость более 5000, но не более 50.

Таким образом, в качестве альтернативы установите максимальный размер набора, который может быть установлен как максимальное количество состояний, а коэффициент загрузки равен 1.

Полагаю, мои вопросы действительно таковы:

• Какой должна быть начальная вместимость, если вы не знаете, сколько предметов должно быть в наборе?
• Действительно ли имеет значение, к чему он настроен, когда максимум может содержать 50?
• Должен ли я беспокоиться об этом?

Answer 1

Если вы знаете, что не будет более 50 штатов (вы имеете в виду штаты США?),

Set<String> uniqueStates = new HashSet<String>(allStates.length, 0.75);

цитируется, безусловно, неправильно. Я бы посоветовал вам перейти на начальную емкость 50 / 0,75 = 67 или, возможно, 68, чтобы быть в безопасности.

Я также чувствую необходимость указать, что вы, вероятно, слишком обдумываете это. Изменение двойного размера массива с 16 до 64 не даст вам заметного снижения производительности, если только это не подходит для наиболее критичной к производительности части программы.

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

new HashSet<String>();

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

Answer 2

Используйте конструктор , где вам не нужно указывать эти значения, тогда выбираются разумные значения по умолчанию.

Answer 3

Во-первых, я хочу сказать, что в вашем случае вы определенно задумывались над этим. Однако, возможно, есть ситуации, когда кто-то захочет сделать это правильно. Итак, вот что я понимаю:

1) Количество элементов, которые вы можете хранить в своем HashSet = начальная емкость x коэффициент загрузки. Поэтому, если вы хотите иметь возможность удерживать n элементов, вам нужно сделать то, что сделал Zarkonnen , и разделить n на коэффициент загрузки.

2) Под прикрытием начальная емкость округляется до степени 2 за урок Oracle .

3) Коэффициент нагрузки должен быть не более 0,80, чтобы предотвратить чрезмерные столкновения, как отмечает Том Хоутин - tackline .

Если вы просто примете значения по умолчанию (начальная емкость = 16, коэффициент нагрузки = 0,75), вы в конечном итоге удвоите свой набор в 3 раза. (Начальный максимальный размер = 12, первое увеличение - емкость 32 и максимальный размер 24 (32 * .75), второе увеличение - емкость 64 и максимальный размер 48 (64 * .75), третье увеличение - емкость 128 и максимальный размер 96 (128). * .75).)

Чтобы приблизить ваш максимальный размер к 50, но при этом держать набор как можно меньше, рассмотрите начальную емкость 64 (мощность двух) и коэффициент загрузки 0,79 или более. 64 * .79 = 50,56, так что вы можете получить все 50 штатов. Если указать 32 <начальная емкость <64, начальная емкость будет округлена до 64, так что это то же самое, что указать 64 заранее. Указание начальной емкости <= 32 приведет к увеличению размера. Использование коэффициента загрузки <0,79 также приведет к увеличению размера, если ваша начальная емкость> 64.

Поэтому я рекомендую указать начальную емкость = 64 и коэффициент загрузки = .79.

Answer 4

Безопасная ставка - пойти на слишком маленький размер.

Поскольку изменение размера улучшается алгоритмом экспоненциального роста (см. Подкаст stackoverflow, выпущенный несколько недель назад), переход на малый размер никогда не будет стоить вам так дорого. Если у вас много наборов (вам повезло), то производительность будет иметь значение, если они слишком большого размера.

Коэффициент загрузки довольно сложный. Я предлагаю оставить его по умолчанию. Я понимаю: ниже 0,70f вы делаете массив слишком большим и, следовательно, медленнее. Выше 0.80f, и вы начнете сталкиваться со многими ключевыми столкновениями. Предположительно, алгоритмы зондирования потребуют более низких коэффициентов загрузки, чем алгоритмы сегмента.

Также обратите внимание, что «начальная емкость» означает нечто немного иное, чем кажется большинству людей. Это относится к количеству записей в массиве. Чтобы получить точную емкость для ряда элементов, разделите на требуемый коэффициент нагрузки (и округлите соответственно).

Answer 5

Если вы хотите оптимизировать это - и это может быть уместно, - некоторые из ваших решений будут зависеть от того, сколько дубликатов вы ожидаете получить в массиве.

• Если дубликатов очень много, вам понадобится начальная буква поменьше вместимость. Большие, разреженные хеш-таблицы плохи при итерации.

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

Полагаю, вы хотите последнее, но стоит подумать об этом, если вы продолжите это.

Answer 6

Я второй Зарконнен. Ваш последний вопрос самый важный. Если это происходит в горячей точке вашего приложения, возможно, стоит потратить усилия на то, чтобы взглянуть на него и попытаться оптимизировать, иначе циклы ЦП дешевле, чем сжигание собственных нейронов.

Answer 7

Сделай правильное предположение. Там нет жесткого правила. Если вы знаете, что, скорее всего, будет 10-20 штатов, я бы начал с этого числа (20).