Вы инициализировали емкость HashMap и ухудшили производительность?

Java

предисловие

В проекте очень приятно видеть, что все поняли, что начальный размер емкости Карты указывается при инициализации HashMap. Но при ближайшем рассмотрении показалось, что что-то не так. Хотя размер указан, это ухудшает производительность.

Может быть, вы такие же.После прочтения «Руководства по разработке Java для Alibaba» я чувствую, что многому научился, поэтому я начал пытаться указать начальный размер Карты на практике, и я почувствовал, что код, который я написал, был немного выше.

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

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

Спецификация разработки Али

Давайте сначала посмотрим, как спецификация начального значения Map описана в Спецификации разработки Java для Alibaba.

Глава 1 Спецификация программирования Руководства по разработке Java от Alibaba, раздел 6, статья 17, посвященная обработке коллекций, гласит следующее:

[Рекомендуется] При инициализации коллекции укажите начальный размер коллекции. Примечание: HashMap инициализируется с помощью HashMap(int initialCapacity).Если размер коллекции временно не может быть определен, то укажите значение по умолчанию (16).

Положительный пример: initialCapacity = (количество сохраняемых элементов / коэффициент загрузки) + 1. Обратите внимание, что коэффициент загрузки (то есть коэффициент загрузки) по умолчанию равен 0,75. Если начальное значение временно не может быть определено, установите его на 16 (то есть значение по умолчанию).

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

Из приведенного выше устава мы, вероятно, узнали несколько вещей:

  • Во-первых, емкость HashMap по умолчанию равна 16;
  • Во-вторых, расширение емкости связано с коэффициентом загрузки и количеством элементов хранения;
  • В-третьих, начальное значение устанавливается для уменьшения влияния расширения на производительность при восстановлении хэша.

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

Верны ли указанные вами начальные значения?

Перейдите непосредственно к предыдущему примеру кода и подумайте, есть ли проблема с этим кодом:

Map<String, String> map = new HashMap<>(4);
map.put("username","Tom");
map.put("address","Bei Jing");
map.put("age","28");
map.put("phone","15800000000");
System.out.println(map);

Подобный код не очень знаком, его тоже очень хорошо писать. HashMap использует 4 значения и инициализирует 4 размера. Полностью ли используется пространство и соответствует ли оно положениям руководства по разработке Ali? !

Верно ли приведенное выше написание? Это действительно нормально? Глядя на код напрямую, вы можете не увидеть проблему, давайте добавим некоторую информацию для печати.

Как проверить расширение

Многие друзья могут также хотеть проверить, когда Hashmap расширяется, но у них нет идей или методов. Вот простой способ получить и распечатать стоимость емкости на основе отражения.

Или приведенный выше пример, давайте изменим его.При добавлении данных в HashMap выводить значения соответствующих атрибутов емкости и размера.

public class MapTest {

    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>(4);
        map.put("username", "Tom");
        print(map);
        map.put("address", "Bei Jing");
        print(map);
        map.put("age", "28");
        print(map);
        map.put("phone", "15800000000");
        print(map);
    }

    public static void print(Map<String, String> map) {
        try {
            Class<?> mapType = map.getClass();
            Method capacity = mapType.getDeclaredMethod("capacity");
            capacity.setAccessible(true);
            System.out.println("capacity : " + capacity.invoke(map) + "    size : " + map.size());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

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

Результат печати следующий:

capacity : 4    size : 1
capacity : 4    size : 2
capacity : 4    size : 3
capacity : 8    size : 4

Нашел что? Когда вводятся четвертые данные, емкость HashMap увеличивается один раз.

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

Теперь, если вы удалите указанное начальное значение, используйте новый метод HashMap(), выполните программу и распечатайте результат следующим образом:

capacity : 16    size : 1
capacity : 16    size : 2
capacity : 16    size : 3
capacity : 16    size : 4

Установлено, что значение по умолчанию не расширено, теоретическая производительность выше. Это очень интересно? Вы тоже входите в это недоразумение?

Проанализируйте принцип

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

Механизм расширения HashMap заключается в расширении при достижении условий расширения. Условие расширения заключается в том, что когда количество элементов (размер) в HashMap превышает критическое значение (порог), оно автоматически расширяется. В HashMap порог = коэффициент нагрузки * емкость. где коэффициент нагрузки по умолчанию равен 0,75.

Рассчитаем его, подставив формулу Коэффициент загрузки равен 0,75, а значение емкости в примере равно 4. Критическое значение равно 4 * 0,75 = 3. То есть, когда фактический размер превысит 3, расширение будет запущено, и расширение напрямую удвоит емкость HashMap. Это согласуется с результатом, который мы напечатали.

Реализация JDK7 и JDK8 одинаковая, что касается анализа исходного кода реализации, то в этой статье мы его анализировать не будем. Все знают основной принцип и эффект теста.

Насколько уместна начальная емкость HashMap?

После приведенного выше анализа мы увидели неявную проблему. В настоящее время я не могу не спросить, насколько уместна начальная емкость HashMap? Можно ли написать большее число по желанию?

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

Когда мы используем HashMap(int initialCapacity) для инициализации емкости, HashMap не использует входящую начальную емкость напрямую в качестве начальной емкости.

JDK поможет рассчитать относительно разумное значение начальной емкости по умолчанию. Так называемое разумное значение на самом деле состоит в том, чтобы найти первое значение, большее или равное степени двойки, переданной пользователем. Исходный код реализации выглядит следующим образом:

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

То есть, когда создается HashMap и передается 7, инициализированная емкость равна 8; когда передается 18, инициализируется емкость 32.

На этом этапе мы приходим к первому выводу: при задании начальной емкости используйте значение 2 в n-й степени, даже если это не задано, JDK поможет взять ближайшую 2 в n-й степени.

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

Согласно формуле расширения, если начальная емкость установлена ​​равной 8, то 8 умножается на 0,75, что составляет 6 значений. При сохранении менее или равного 6 значениям расширение не будет запущено.

Так может ли это быть обращено формулой? Соответствующее значение рассчитывается следующим образом:

return (int) ((float) expectedSize / 0.75F + 1.0F);

Например, запланируйте поместить в HashMap 7 элементов, рассчитанных как ожидаемый размер/0,75F + 1,0F, 7/0,75 + 1 = 10, после обработки JDK для 10 будет установлено значение 16.

В настоящее время 16 является более разумным значением, и оно может значительно снизить вероятность расширения.

Следовательно, можно считать, что когда количество элементов в HashMap четко известно, установка емкости по умолчанию в expectSize / 0.75F + 1.0F является относительно хорошим выбором с точки зрения производительности, но в то же время принесет в жертву какая-то память.

Другие соответствующие знания

Поймите приведенные выше знания и, наконец, добавьте некоторые знания, связанные с HashMap:

  • HashMap не выделяет массив корзин сразу после нового;
  • Размер массива сегментов HashMap равен степени 2;
  • HashMap будет расширяться, когда количество помещаемых элементов больше, чем Capacity * LoadFactor (по умолчанию 16 * 0,75);
  • JDK8 преобразует связанный список в древовидную структуру после того, как длина связанного списка хэш-коллизий достигнет TREEIFY_THRESHOLD (по умолчанию 8) для повышения производительности;
  • JDK8 снижает потребление производительности повторного хеширования благодаря продуманному дизайну при изменении размера.

резюме

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

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

Категории