существует"Те понятия, которые тупо неясны в HashMap«В статье мы представили несколько концепций, связанных с пропускной способностью в HashMap, и кратко представили механизм расширения HashMap.
В статье мы упоминали, что емкость HashMap по умолчанию равна 16, но если пользователь укажет число в качестве емкости через конструктор, то Hash выберетбольше первой степени числа 2 числакак емкость. (3->4, 7->8, 9->16)
В этой статье, продолжая предыдущую статью, давайте подробно изучим, должны ли мы устанавливать емкость HashMap по умолчанию? Если мы действительно хотим установить начальную емкость HashMap, сколько мы должны установить?
Зачем устанавливать инициализирующую способность HashMap
Как мы упоминали ранее, в «Руководстве по разработке Java для Alibaba» рекомендуется установить инициализирующую емкость HashMap.
Итак, почему это предлагается? Вы когда-нибудь думали об этом?
Давайте сначала напишем кусок кода под JDK 1.7 (jdk1.7.0_79) для проверки производительности без указания емкости инициализации и указания емкости инициализации. (результаты jdk 8 будут другими, я проанализирую в следующей статье)
public static void main(String[] args) {
int aHundredMillion = 10000000;
Map<Integer, Integer> map = new HashMap<>();
long s1 = System.currentTimeMillis();
for (int i = 0; i < aHundredMillion; i++) {
map.put(i, i);
}
long s2 = System.currentTimeMillis();
System.out.println("未初始化容量，耗时 ： " + (s2 - s1));
Map<Integer, Integer> map1 = new HashMap<>(aHundredMillion / 2);
long s5 = System.currentTimeMillis();
for (int i = 0; i < aHundredMillion; i++) {
map1.put(i, i);
}
long s6 = System.currentTimeMillis();
System.out.println("初始化容量5000000，耗时 ： " + (s6 - s5));
Map<Integer, Integer> map2 = new HashMap<>(aHundredMillion);
long s3 = System.currentTimeMillis();
for (int i = 0; i < aHundredMillion; i++) {
map2.put(i, i);
}
long s4 = System.currentTimeMillis();
System.out.println("初始化容量为10000000，耗时 ： " + (s4 - s3));
}
Приведенный выше код несложно понять, мы создали 3 HashMaps, которые были инициализированы с емкостью по умолчанию (16), половиной количества элементов (50 миллионов) в качестве исходной емкости и количеством элементов (100 миллионов) в качестве исходной емкости. начальная мощность.. Тогда вложите в них 100 миллионов KV соответственно.
Выходной результат:
未初始化容量，耗时 ： 14419
初始化容量5000000，耗时 ： 11916
初始化容量为10000000，耗时 ： 7984
Из результатов мы можем узнать, что, когда известно количество KV, которые должны быть сохранены в HashMap, установка разумной емкости инициализации может эффективно повысить производительность.
Разумеется, приведенные выше выводы также подтверждаются теорией. мыПредыдущийКак упоминалось в статье, HashMap имеет механизм расширения, то есть он будет расширяться при выполнении условий расширения. Условие расширения HashMap заключается в том, что когда количество элементов (размер) в HashMap превышает критическое значение (порог), оно автоматически расширяется. В HashMap,threshold = loadFactor * capacity.
Поэтому, если мы не зададим начальный размер емкости, по мере увеличения элементов HashMap будет многократно расширяться, а механизм расширения в HashMap определяет, что при каждом расширении необходимо перестраивать хеш-таблицу, что сильно влияет на производительность. (О изменении размера у меня будет отдельная статья позже)
Из приведенного выше примера кода мы также обнаружили, что начальная емкость также установлена, и установленное значение также повлияет на производительность.Итак, когда мы знаем количество KV, которое должно храниться в HashMap, какую емкость следует установить?
Инициализация емкости в HashMap
В предыдущей статье мы на самом деле представили примеры кода.По умолчанию, когда мы устанавливаем инициализирующую емкость HashMap, HashMap фактически будет использовать первую степень 2, превышающую значение, в качестве инициализационной емкости.
В предыдущей статье есть пример
Map<String, String> map = new HashMap<String, String>(1);
map.put("hahaha", "hollischuang");
Class<?> mapType = map.getClass();
Method capacity = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
System.out.println("capacity : " + capacity.invoke(map));
Когда начальная емкость установлена на 1, выходной результат равен 2. В jdk1.8, если инициализированная емкость, которую мы передаем, равна 1, результат установки фактически равен 1. Причина, по которой приведенный выше код выводит результат 2, заключается в том, что map.put("hahaha", "hollischuang"); Код вызывает Для расширения емкости емкость была увеличена с 1 до 2.
Итак, вернемся к теме, когда мы задаем начальную емкость через HashMap (int initialCapacity), HashMap не обязательно напрямую использует переданное нами значение, а получает новое значение после расчета, для повышения эффективности хеширования . (1->1, 3->4, 7->8, 9->16)
В Jdk 1.7 и Jdk 1.8 время инициализации HashMap этой емкости отличается. В jdk1.8 при вызове конструктора HashMap для определения HashMap устанавливается емкость. В Jdk 1.7 эта операция не выполняется до первой операции размещения.
Будь то Jdk 1.7 или Jdk 1.8, алгоритм расчета емкости инициализации фактически один и тот же, основной код выглядит следующим образом:
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;
Приведенный выше код довольно интересен, простая инициализация емкости, Java-инженеры также имеют в нем много соображений.
Цель вышеописанного алгоритма достаточно проста, а именно: по переданному пользователем значению емкости (шапка в коде) путем вычисления получить первую степень двойки, которая больше его, и вернуть ее.
Умные читатели, если бы вас попросили разработать этот алгоритм, как бы вы его рассчитали? Если вы думаете о двоичном коде, это довольно просто. Взгляните на несколько примеров:
Пожалуйста, обратите внимание на изменения синих шрифтов в приведенных выше примерах, возможно, вы найдете какие-то закономерности. 5->8, 9->16, 19->32, 37->64 в основном прошли два этапа.
Шаг 1, 5->7
Шаг 2, 7->8
Шаг 1, 9->15
Шаг 2, 15->16
Шаг 1, 19->31
Шаг 2, 31->32
В соответствии с приведенным выше кодом, Шаг 1:
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
В соответствии с приведенным выше кодом, Шаг 2:
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
Шаг 2 относительно прост, то есть оценить предельное значение, а затем добавить 1 к значению, полученному на шаге 1.
Шаг 1 Как это понять? ** На самом деле, он поочередно сдвигает двоичное число вправо, а затем выполняет операцию ИЛИ с исходным значением. **Назначение Для двоичного числа начните с первого бита, отличного от 0, и установите все последующие биты в 1.
Просто возьмите двоичное число и примените приведенную выше формулу, чтобы найти его назначение:
1100 1100 1100 >>>1 = 0110 0110 0110
1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
1110 1110 1110 >>>2 = 0011 1011 1011
1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
1111 1111 1111 >>>4 = 1111 1111 1111
1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
через несколько раз无符号右移и按位或Операция: мы преобразуем 1100 1100 1100 в 1111 1111 1111, а затем добавляем 1111 1111 1111, чтобы получить 1 0000 0000 0000, что является первой степенью числа 2 больше, чем 1100 1100 1100.
Итак, мы объяснили код Шага 1 и Шага 2. Это преобразование числа в первую степень двойки, большей, чем оно само. (Вы можете начать восхищаться Java-инженерами, использовать无符号右移и按位或Операция значительно повышает эффективность. )
Но есть особый случай, когда вышеуказанная формула неприменима, и эти числа сами являются степенями двойки. Если число 4 применяется формула. что приведет к 8 :
Step 1:
0100 >>>1 = 0010
0100 | 0010 = 0110
0110 >>>1 = 0011
0110 | 0011 = 0111
Step 2:
0111 + 0001 = 1000
Чтобы решить эту проблему, инженеры JDK присвоили всем числам, переданным пользователями, значение -1 перед вычислением, что является первой строкой исходного кода:
int n = cap - 1;
На этом этапе давайте вернемся и посмотрим на код для установки начальной емкости.Ясна ли цель с первого взгляда:
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
когда мы используемHashMap(int initialCapacity)При инициализации емкости jdk поможет нам рассчитать относительно разумное значение в качестве начальной емкости по умолчанию. Итак, нам просто нужно напрямую передать количество элементов, которые будут храниться в известном HashMap, в initialCapacity?
Что касается настройки этого значения, в «Руководстве по разработке Java для Alibaba» есть следующие предложения:
Это значение изначально не создавалось инженерами Alibaba, а также используется в гуаве (версия 21.0).
public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
return new HashMap<K, V>(capacity(expectedSize));
}
/**
* Returns a capacity that is sufficient to keep the map from being resized as long as it grows no
* larger than expectedSize and the load factor is ≥ its default (0.75).
*/
static int capacity(int expectedSize) {
if (expectedSize < 3) {
checkNonnegative(expectedSize, "expectedSize");
return expectedSize + 1;
}
if (expectedSize < Ints.MAX_POWER_OF_TWO) {
// This is the calculation used in JDK8 to resize when a putAll
// happens; it seems to be the most conservative calculation we
// can make. 0.75 is the default load factor.
return (int) ((float) expectedSize / 0.75F + 1.0F);
}
return Integer.MAX_VALUE; // any large value
}
существуетreturn (int) ((float) expectedSize / 0.75F + 1.0F);Выше есть строка комментариев, указывающая, что эта формула не является оригинальной для гуавы и относится к реализации в методе putAll в JDK8. Заинтересованные читатели могут посмотреть на реализацию метода putAll, который также является приведенной выше формулой.
Хотя, когда мы используемHashMap(int initialCapacity)При инициализации емкости jdk поможет нам рассчитать относительно разумное значение в качестве начальной емкости по умолчанию. Но это значение не относится к значению loadFactor.
То есть, если значение по умолчанию, которое мы установили, равно 7, оно будет установлено на 8 после обработки Jdk, но этот HashMap будет расширен, как только количество элементов достигнет 8 * 0,75 = 6, чего, очевидно, мы не ожидаем. видеть.
если мы пройдемexpectedSize / 0.75F + 1.0FРасчет, 7/0,75 + 1 = 10, после обработки Jdk 10 будет установлено значение 16, что сильно снижает вероятность расширения.
Когда емкость хеш-таблицы, поддерживаемой HashMap, достигает 75% (по умолчанию), запускается повторный хэш, а процесс повторного хеширования занимает много времени. Таким образом, если для емкости инициализации задано значение expectSize/0,75 + 1, это может эффективно уменьшить количество конфликтов и ошибок.
Таким образом, я могу думать, что установка емкости по умолчанию на ожидаемый размер / 0,75F + 1,0F является относительно хорошим выбором с точки зрения производительности, когда мы явно знаем количество элементов в HashMap, но в то же время это принесет в жертву часть памяти. .
Суммировать
Когда мы хотим создать HashMap в коде, если мы знаем количество элементов, которые будут храниться в Map, установка начальной емкости HashMap может в определенной степени повысить эффективность.
Однако JDK не будет напрямую принимать число, переданное пользователем, в качестве емкости по умолчанию, но выполнит некоторые операции и, наконец, получит степень двойки. Причина в том(Во всей сети нет другой статьи, в которой бы анализировался hash() в Map.), алгоритм для получения этого числа фактически использует беззнаковый сдвиг вправо и операцию побитового ИЛИ для повышения эффективности.
Однако, чтобы в наибольшей степени избежать потребления производительности, вызванного расширением, мы предлагаем установить число емкости по умолчанию равным ожидаемому размеру / 0,75F + 1,0F. В ежедневной разработке вы можете использовать
Map<String, String> map = Maps.newHashMapWithExpectedSize(10);
Чтобы создать HashMap, процесс расчета нам поможет выполнить гуава.
Однако описанная выше операция является способом обмена памяти на производительность, поэтому при ее фактическом использовании следует учитывать влияние памяти.
Напоследок оставим задуманный вопрос: почему в JDK 8 метод putAll использует эту формулу expectSize/0.75F + 1.0F, а put, конструкторы и т.д. не используют эту формулу по умолчанию?
Об авторе: Холлис, человек с уникальным увлечением кодированием, технический эксперт интернет-компании, блогер по персональным технологиям, технические статьи читают десятки миллионов человек по всей сети, соавтор «Трех курсов для программистов». ".