Коллекции часто используются в повседневной разработке Java-разработки, и как типичная структура данных K-V, HashMap должна быть знакома Java-разработчикам.
В повседневной разработке мы часто создаем HashMap следующим образом:
Map<String, String> map = new HashMap<String, String>();
Однако задумывались ли вы когда-нибудь о том, что в приведенном выше коде мы не указали емкость для HashMap, тогда какова емкость по умолчанию для вновь созданной HashMap в настоящее время? Зачем?
В этой статье будет проанализирована эта проблема.
что такое емкость
В Java есть две относительно простые структуры данных для хранения данных: массивы и связанные списки. Характеристики массива: простая адресация, сложность вставки и удаления и характеристики связанного списка: сложность адресации, легкость вставки и удаления. HashMap представляет собой комбинацию массива и связанного списка, используя преимущества обоих, мы можем понимать его как массив связанного списка.
В HashMap есть два ключевых поля, которые легко спутать: размер и емкость, где емкость — это емкость Карты, а размером мы называем количество элементов в Карте.
Простая аналогия облегчает понимание: HashMap — это «ведро», тогда емкость (capacity) — это максимальное количество элементов, которое в данный момент может вместить ведро, а количество элементов (размер) указывает, сколько элементов содержит ведро. заполненный.
Например, следующий код:
Map<String, String> map = new HashMap<String, String>();
map.put("hollis", "hollischuang");
Class<?> mapType = map.getClass();
Method capacity = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
System.out.println("capacity : " + capacity.invoke(map));
Field size = mapType.getDeclaredField("size");
size.setAccessible(true);
System.out.println("size : " + size.get(map));
Выходной результат:
capacity : 16、size : 1
Выше мы определили новый HashMap, и хотели поместить в него элемент, а затем через отражение напечатали емкость и размер, его емкость равна 16, а количество хранимых элементов равно 1.
В предыдущем примере мы обнаружили, что при создании HashMap, если мы не укажем его емкость, мы получим карту с емкостью по умолчанию, равной 16. Откуда же берется эта емкость? И почему этот номер?
Емкость и хэш
Чтобы объяснить причину этой емкости по умолчанию, мы должны сначала узнать, для чего эта емкость используется?
Мы знаем, что емкость — это количество «сегментов» в HashMap. Затем, когда мы хотим поместить элемент в HashMap, нам нужно вычислить, в какое ведро его поместить с помощью определенного алгоритма. Этот процесс называется hash, который соответствует методу hash в HashMap.
Мы знаем, что функция хеш-метода состоит в том, чтобы найти позицию этого K-V в массиве связанных списков в соответствии с Ключом. То есть на входе хеш-метода должен быть ключ типа Object, а на выходе должен быть индекс массива типа int. Если бы вас попросили разработать этот метод, что бы вы сделали?
На самом деле это просто, нам нужно только вызвать метод hashCode() объекта Object, который вернет целое число, а затем использовать это число для определения по модулю емкости HashMap.
Если это так просто, то настройка емкости HashMap будет намного проще, но, учитывая эффективность и другие вопросы, реализация хеш-метода HashMap все еще сложна.
Реализация хэша
Далее мы представим принцип реализации хеш-метода в HashMap. (Следующая часть контента основана на моей собственной статье:Во всей сети нет другой статьи, в которой бы анализировался hash() в Map.. PS: Многие статьи в интернете про анализ хеш-метода HashMap "выведены" на основе этой статьи. )
С точки зрения конкретной реализации, это реализовано двумя методами int hash(Object k) и int indexFor(int h, int length).
hash : этот метод в основном преобразует Object в целое число.
indexFor : этот метод в основном преобразует целое число, сгенерированное хэшем, в нижний индекс в массиве связанного списка.
Чтобы сосредоточиться на главном в этой статье, давайте просто рассмотрим метод indexFor. Давайте сначала посмотрим на детали реализации в Java 7 (хотя в Java 8 нет такого отдельного метода, алгоритм запроса индексов такой же, как в Java 7):
static int indexFor(int h, int length) {
return h & (length-1);
}
Метод indexFor на самом деле предназначен в основном для замены хэш-кода индексом в массиве связанного списка. Два параметра h представляют значение хэш-кода элемента, а длина представляет емкость HashMap. Так что же означает return h & (length-1)?
На самом деле он берет модель. Все использование в Java битовых операций (&) вместо операций по модулю (%), главным соображением является эффективность.
Эффективность побитовой операции (&) намного выше, чем у операции замены по модулю (%). Основная причина в том, что побитовая операция напрямую работает с данными памяти, и ее не нужно преобразовывать в десятичную, поэтому скорость обработки очень высока. быстрый.
Итак, почему вы можете использовать побитовые операции (&) для реализации операции по модулю (%)? В основе этого лежит следующий принцип:
X % 2^n = X & (2^n – 1)
Предположим, что n равно 3, тогда 2^3 = 8, что в двоичном формате равно 1000. 2^3 -1 = 7, что равно 0111.
В настоящее время X & (2 ^ 3 - 1) эквивалентно взятию последних трех цифр двоичной системы X.
С двоичной точки зрения X/8 эквивалентно X >> 3, то есть сдвигая X вправо на 3 бита, в это время получается частное X/8, а удаленная часть (последняя три цифры) равно X % 8, что является остатком.
Я не знаю, понимаете ли вы приведенное выше объяснение, если вы его не понимаете, это не имеет значения, вам просто нужно запомнить этот навык. Или вы можете найти несколько примеров, чтобы попробовать.
6 % 8 = 6 ，6 & 7 = 6
10 % 8 = 2 ，10 & 7 = 2
Следовательно, верните h & (length-1); Пока длина длины гарантированно равна 2 ^ n, операция по модулю может быть реализована.
так,Поскольку битовые операции напрямую работают с данными памяти и их не нужно преобразовывать в десятичные числа, битовые операции более эффективны, чем операции по модулю, поэтому HashMap использует битовые операции вместо того, чтобы брать индекс при вычислении индекса элементов, которые должны быть сохранены в массиве. Модульная операция. Причина, по которой его можно эквивалентно заменить, заключается в том, что емкость HashMap должна быть 2 ^ n.
Итак, если это 2^n, то почему должно быть 16? Почему не может быть 4, 8 или 32?
Относительно выбора этой дефолтной емкости JDK не дал официального объяснения, и автор не нашел никакой ценной информации по этому поводу в Интернете. (Если у кого-то есть соответствующая авторитетная информация или идеи, вы можете оставить сообщение для обмена)
Согласно заключению автора, это должно быть значение опыта (Значение опыта).Поскольку в качестве начального значения должно быть установлено значение по умолчанию 2^n, то необходимо найти компромисс между эффективностью и использованием памяти. Это значение не может быть ни слишком маленьким, ни слишком большим.
Если он слишком мал, расширение емкости может происходить часто, что влияет на эффективность. Слишком большой и пустая трата места, не стоит.
Поэтому в качестве значения опыта было принято 16.
В JDK 8 определение емкости по умолчанию: static final int DEFAULT_INITIAL_CAPACITY = 1 aka 16Также новое в 1.8,
Итак, давайте поговорим об этом дальше, как HashMap гарантирует, что его емкость должна быть 2 ^ n? А если пользователь настроит его сам?
Что касается этой части, HashMap сделал обработку совместимости в двух местах, которые могут изменить его емкость, а именно, когда указанная емкость инициализируется и когда она расширяется.
Инициализировать указанную емкость
Когда мы устанавливаем начальную емкость через HashMap (int initialCapacity), HashMap не обязательно напрямую использует значение, которое мы передаем, но получает новое значение после вычисления, чтобы повысить эффективность хеширования. (1->1, 3->4, 7->8, 9->16)
В JDK 1.7 и JDK 1.8 время инициализации HashMap этой емкости отличается. В JDK 1.8 при вызове конструктора HashMap для определения HashMap задается емкость. В JDK 1.7 эта операция не выполняется до первой операции размещения.
Взгляните, как JDK находит первую степень числа 2, большую, чем указанное переданное значение:
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;
Цель вышеописанного алгоритма достаточно проста, а именно: по переданному пользователем значению емкости (шапка в коде) путем вычисления получить первую степень двойки, которая больше его, и вернуть ее.
Пожалуйста, обратите внимание на изменения синих шрифтов в приведенных выше примерах, возможно, вы найдете какие-то закономерности. 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 Как это понять? На самом деле, двоичное число поочередно сдвигается вправо, а затем объединяется с исходным значением по операции ИЛИ. Его цель состоит в том, чтобы установить все последующие биты в 1, начиная с первого бита, который не равен 0, для двоичного числа.
Просто возьмите двоичное число и примените приведенную выше формулу, чтобы найти его назначение:
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 , а затем прибавляем 1 к 1111 1111 1111, чтобы получить 1 0000 0000 0000, что является первым числом, большим 1100 1100 1100 в степени 2.
Что ж, теперь мы объясним код шага 1 и шага 2. Это преобразование числа в первую степень двойки, большей, чем оно само.
Но есть особый случай, когда вышеуказанная формула неприменима, и эти числа сами являются степенями двойки. Если число 4 применяется формула. Результатом будет 8, но на самом деле и эта проблема решена Конкретные методы проверки и решения JDK см.Во всей сети нет другой статьи, в которой бы анализировался hash() в Map., здесь не будет распространяться.
Короче говоря, HashMap вычисляет первую степень двойки, превышающую число, с помощью беззнакового сдвига вправо и операции побитового ИЛИ в соответствии с емкостью инициализации, переданной пользователем.
Расширение
Помимо указания емкости HashMap во время инициализации, ее емкость также может изменяться при расширении.
HashMap имеет механизм расширения, то есть он будет расширяться при достижении условий расширения. Условие расширения HashMap заключается в том, что когда количество элементов (размер) в HashMap превышает критическое значение (порог), оно автоматически расширяется.
В HashMap порог = коэффициент нагрузки * емкость.
loadFactor — это коэффициент загрузки, который указывает на заполненность HashMap. Значение по умолчанию — 0,75f. Установка его на 0,75 имеет преимущество, то есть 0,75 — это ровно 3/4, а емкость — это степень двойки. Следовательно, произведение двух чисел является целым числом.
Для HashMap по умолчанию расширение по умолчанию будет запускаться, когда его размер превышает 12 (16 * 0,75).
Ниже приведен раздел метода расширения (изменения размера) в HashMap:
if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
Из приведенного выше кода видно, что размер расширенной таблицы становится в два раза больше исходного размера.После выполнения этого шага будет выполнена корректировка расширенной таблицы.Эта часть не является предметом этой статьи и будет опущена. .
Видно, что когда количество элементов (размер) в HashMap превысит критическое значение (порог), емкость будет автоматически расширена, причем емкость будет увеличена до удвоенной исходной емкости, то есть с 16 до 32. , 64, 128...
Таким образом, гарантируя, что начальная емкость равна степени 2, а расширение также удваивается по сравнению с предыдущей емкостью, гарантируется, что емкость HashMap всегда будет степенью 2.
Суммировать
HashMap — это структура данных, элементы необходимо хэшировать в процессе размещения, цель — вычислить конкретное местоположение элемента, хранящегося в hashMap.
Процесс хэш-операции на самом деле хэш-код ключа целевого элемента, а затем по модулю емкости Карты.Чтобы повысить эффективность по модулю, инженеры JDK используют битовую операцию вместо операции по модулю, которая требует определенного емкость Карты. Должна быть степенью 2.
В качестве емкости по умолчанию слишком большая и слишком маленькая не подходят, поэтому 16 используется как более подходящее значение опыта.
Чтобы в любом случае емкость Map была степенью двойки, HashMap имеет ограничения в двух местах.
Во-первых, если пользователь укажет начальную емкость, то HashMap рассчитает первую степень числа 2, которая больше этого числа, в качестве начальной емкости.
Кроме того, при расширении емкости она еще и удваивается, то есть 4 становится 8, а 8 становится 16.
В этой статье, анализируя, почему емкость HashMap по умолчанию равна 16, мы углубляемся в принцип HashMap и анализируем принцип, лежащий в его основе.Из кода мы можем обнаружить, что инженеры JDK использовали различные битовые операции до крайности и пытались все возможные способы оптимизации эффективности. стоит поучиться!
Об авторе: Холлис, человек с уникальным увлечением кодированием, в настоящее время является техническим экспертом Alibaba, блоггером по персональным технологиям, технические статьи читают десятки миллионов человек по всей сети и соавтор «Трех курсов для программистов».