Github 2.1k Star.Путь к тому, чтобы стать Java-инженером, почему бы тебе не прийти и не узнать?
GitHub 2.1k ЗвездаПуть к тому, чтобы стать Java-инженером, ты правда не хочешь узнать?
GitHub 2.1k ЗвездаПуть к тому, чтобы стать Java-инженером, ты действительно уверен, что не хочешь узнать?
Коллекции часто используются в повседневной разработке Java-разработки. В некоторых предыдущих статьях мы представили некоторые вопросы, на которые следует обратить внимание при использовании классов коллекций, например, «Почему Alibaba запрещает операцию удаления/добавления элементов в цикле foreach».
Что касается классов коллекций, на самом деле в «Руководстве по разработке 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 превышает критическое значение (порог), оно автоматически расширяется. В 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));
В jdk1.7, когда емкость инициализации установлена на 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, не так ли?
Что касается установки этого значения, существуют следующие предложения в «Руководстве по развитию Alibaba Java»:
Это значение изначально не создавалось инженерами 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, конструкторы и т.д. не используют эту формулу по умолчанию?