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

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

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

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

От googling я придумал:

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

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

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

Насколько я понимаю, мои вопросы:

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

Ответы

Ответ 1

Предполагая, что вы знаете, что не будет более 50 государств (вы имеете в виду государства США?),

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

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

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

Поэтому лучше всего использовать:

new HashSet<String>();

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

Ответ 3

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

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

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

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

Ответ 4

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

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

2) Под обложками начальная емкость округляется до двух для учебника Oracle.

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

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

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

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

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