java: детальное объяснение расширения HashMap и пример кода

Расширение HashMap

Введение:

Размер HashMap больше или равен (Объем * коэффициент загрузкиКогда это происходит, запускается операция расширения, что является дорогой операцией.

Почему нужно расширяться? По умолчанию емкость HashMap составляет 16, с不断增加 элементов в HashMap вероятность возникновения hash-конфликтов выше, и链ка, соответствующая каждому бачку, становится дольше,

Это повлияет на производительность поиска, так как каждый раз нужно пройтись по списку, сравнить объекты на равенство, до тех пор, пока не найдете элемент.

Чтобы повысить производительность поиска, можно только расширять, уменьшать количество hash-конфликтов, чтобы ключ элементов был как можно более равномерно распределен.

Основные моменты расширения

Значение фактора загрузки по умолчанию составляет 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

Значение емкости по умолчанию составляет 16

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // равно 16

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

 public HashMap(int initialCapacity, float loadFactor)

По умолчанию, размер HashMap достигает 16 * 0.75 = 12,

Пока каждый Entry (или бачок) содержит хотя бы один элемент, выполняется расширение.

 if ((size >= threshold) && (null != table[bucketIndex])) {
      resize(2 * table.length);
      hash = (null != key) ? hash(key) : 0;
      bucketIndex = indexFor(hash, table.length);
}

При расширении емкость контейнера удваивается

 resize(2 * table.length);

При расширении необходимо пересчитать индекс элемента в массиве

1. Перераспределить новый массив Entry
2. Пересчитать индекс элемента в новом массиве(Затратно по ресурсам)

Спасибо за чтение, надеюсь, это поможет вам, спасибо за поддержку нашего сайта!