Когда начальная емкость HashSet (т.е. 16) заполняется, как вычисляется новая емкость? Какова формула?

Question

Когда начальная емкость HashSet (т.е. 16) заполняется, как вычисляется новая емкость? Какова формула?

, например: как размер списка массива увеличивается по формуле Новые мощности = (текущая емкость * 3/2) + 1

и для векторов это Новые мощности = (текущая емкость 2 *)

Answer 1

A HashSet подставил HashMap. Согласно grepcode, размер увеличивается каждый раз, когда требуется увеличение. Вот код для метода addEntry, который является внутренним методом, призванным фактически добавить новую запись в таблицу.

void addEntry(int hash, K key, V value, int bucketIndex) { 
    Entry<K,V> e = table[bucketIndex]; 
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
    if (size++ >= threshold) 
     resize(2 * table.length); 
} 

Обратите внимание, что это деталь реализации и может быть изменена в любое время.

Обратите внимание, что если источник информации не нуждается в Javadoc (то есть деталь реализации), то, глядя на источник, ВСЕГДА должен быть вашим первым ресурсом.

Answer 2

Вместимость HashSet составляет doubled при достижении коэффициента нагрузки (0.75).

Как documentation объясняет:

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

Пример:

Первоначальная мощность HashSet является 16. Когда достигается коэффициент нагрузки (0.75), то есть 16 * 0.75 = 12; при вставке элемента 12th емкость составляет doubled, то есть она становится 32.

Answer 3

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

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; 

и изменяет его на коэффициент нагрузки

int capacity = roundUpToPowerOf2(toSize); 

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 
table = new Entry[capacity]; 

Answer 4

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

Начальная мощность HashSet = 16, коэффициент нагрузки = 0.75, Threshold = 75% мощности

Что означает, когда новое значение добавляется в HashSet, это размер проверяется на порог, и если размер превышает порог HashSet идет для изменения размера. Изменение размеров делает размер таблицы двойным текущего размера. Таким образом, емкость удваивается, а порог установлен на 75% от новой мощности.

Что указывает, когда размер HashSet равен или превышает 75% его емкости, происходит изменение размера.