HashMap часто посещает внутренние интервью, например, какова начальная емкость по умолчанию? Что такое коэффициент загрузки? Это небезопасно для потоков? Можете ли вы повторить процесс операции ввода? Операция получения повторяется? В чем разница между реализацией jdk 1.7 и 1.8? В ожидании серии вопросов, возможно, вы сможете гладко ответить на эти вопросы, показывая, что вы все еще хорошо понимаете HashMap, но недавно наши товарищи по команде сделали технический обмен, некоторые из которых я получил совсем немного, я поделюсь с вами .
Каждую пятницу мы будем делиться технологиями, и все будут делиться ими по очереди.На самом деле, этот механизм очень хорош.Все сидят вместе, чтобы глубоко обсудить какой-то вопрос знаний, столкнуться с мыслями и выиграть больше.
Задайте два вопроса и посмотрите, сможете ли вы на них ответить?
- Как найти наименьшую степень целого числа 2, превышающую начальное установленное значение емкости?
- Какая специальная операция выполняется при хешировании ключа в HashMap? Зачем это делать?
Сначала подумайте сами, а затем читайте дальше, чтобы получить лучшие результаты!
Следующий анализ для jdk 1.8
анализировать
Вопрос 1: Как найти наименьшее целое число степени 2, превышающее заданное значение начальной емкости?
Когда мы используем HashMap, если мы используем конструктор по умолчанию, мы создадим HashMap с начальной емкостью 16 и коэффициентом загрузки 0,75. У этого есть недостаток, то есть, когда объем данных относительно большой, будут выполняться частые операции расширения, и данные будут сдвигаться во время расширения.Создание браузера, посмотрите исходный код
public HashMap(int initialCapacity, float loadFactor) {
...
// 如果设置的初始容量大于最大容量就默认为最大容量 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
...
this.loadFactor = loadFactor;
// tableSizeFor 方法主要就是计算比给定的初始容量值大的最小的 2 的幂次方整数
this.threshold = tableSizeFor(initialCapacity);
}
Из исходного кода мы можем узнать, что максимальная емкость составляет 2 ^ 30, то есть длина части массива HashMap находится в диапазоне [0, 2 ^ 30], а затем вычислить наименьшую мощность. из-2 целое число больше, чем начальная емкость, гдеtableSizeForМетод является ключевым, давайте посмотрим на исходный код
// Returns a power of two size for the given target capacity
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 должен гарантировать, что емкость является целой степенью числа 2. Эффект этого метода заключается в том, что если введенное вами ограничение представляет собой целую степень числа 2, то возвращается само ограничение. input cap is not 2 Целая степень , возвращает наименьшую целочисленную степень 2, большую чем cap
Почему мощность равна степени двойки?
Поскольку соответствующий индекс ключа в массиве получается путем выполнения операции И между хеш-значением ключа и длиной массива -1, например: tab[i = (n - 1) & hash]
- n представляет собой целую степень числа 2, так что за битами, равными 1 перед n-1, следует 1, так что соответствующее количество цифр после (n-1) и хэша может быть либо 0, либо 1, в зависимости от значение хэша, это может обеспечить однородность хэша, и в то же время эффективность работы высока.
- Если n не является целой степенью числа 2, это вызовет больше коллизий хэшей.
Этот метод сначала выполняет операцию шапки - 1. Преимущество этого заключается в том, чтобы избежать ситуации, когда входная шапка представляет собой целую степень числа 2, а окончательное вычисляемое число в два раза превышает кепку, потому что установка кепки уже соответствует требованиям HashMap. , нет необходимости Инициализировать HashMap с 2-кратной емкостью, я не понимаю, пример анализа позже
Мы уже ввели, что максимальная емкость HashMap составляет 2 ^ 30, поэтому максимальная емкость представляет собой целое число битов 30. Мы будем использовать 30-битное число, чтобы продемонстрировать сдвиг или операцию в алгоритме, предполагая, что n = 001xxx xxxxxxxx xxxxxxxx xxxxxxxx (x представляет собой бит 0 или 1, нам все равно)
Первый сдвиг вправо n |= n >>> 1, операция состоит в том, чтобы использовать само n, а число после n сдвигается вправо на 1 бит для выполнения операции ИЛИ, так что число, следующее за 1 из числа также может быть помещен старший бит n.
n 001xxx xxxxxxxx xxxxxxxx xxxxxxxx
n >>> 1 0001xx xxxxxxxx xxxxxxxx xxxxxxxx
| 或操作 0011xx xxxxxxxx xxxxxxxx xxxxxxxx
结果就是把 n 的最高位为 1 的紧邻的右边的 1 位也置为了 1，这样高位中有连续两位都是 1
второй сдвиг вправо n |= n >>> 2
n 0011xx xxxxxxxx xxxxxxxx xxxxxxxx
n >>> 2 000011 xxxxxxxx xxxxxxxx xxxxxxxx
| 或操作 001111 xxxxxxxx xxxxxxxx xxxxxxxx
结果就是 n 的高位中有连续 4 个 1
третий сдвиг вправо n |= n >>> 4
n 001111 xxxxxxxx xxxxxxxx xxxxxxxx
n >>> 4 000000 1111xxxx xxxxxxxx xxxxxxxx
| 或操作 001111 1111xxxx xxxxxxxx xxxxxxxx
结果就是 n 的高位中有连续 8 个 1
Четвертый сдвиг вправо n |= n >>> 8
n 001111 1111xxxx xxxxxxxx xxxxxxxx
n >>> 8 000000 00001111 1111xxxx xxxxxxxx
| 或操作 001111 11111111 1111xxxx xxxxxxxx
结果就是 n 的高位中有连续 16 个 1
пятый сдвиг вправо n|n >>> 16
n 001111 11111111 1111xxxx xxxxxxxx
n >>> 16 000000 00000000 00001111 11111111
| 或操作 001111 11111111 11111111 11111111
结果就是 n 的高位1后面都置为 1
Наконец, n и максимальная емкость будут сравниваться. Если >= 2^30, будет взята максимальная емкость. Если
011111 11111111 11111111 11111111, это значение является наименьшей целой степенью числа 2, превышающей данное значение
Продемонстрируем на конкретном примере, например, cap = 18
Мы вводим 18 и выводим 32, что является наименьшей степенью числа 2, превышающей 18.
Если сама кепка является степенью числа 2, каков результат?
Из демонстрации видно, что сама шапка представляет собой целую степень числа 2, а выходной результат — это она сама.
Все еще остается проблема, оставленная выше, то есть сначала ограничить -1, я объяснил, что во избежание вывода четного числа окончательный результат вычисления равен 2 * cap, что является пустой тратой места.
На демонстрации мы видим, что ввод равен 16, но окончательный результат вычисления равен 32, что приведет к потере места, поэтому алгоритм очень хорош, сначала уменьшите ограничение на единицу.
Вопрос 2: Какие специальные операции выполняются при хешировании ключей в HashMap? Зачем это делать?
Прежде всего, мы знаем, что когда HashMap выполняет операцию размещения, он сначала выполняет операцию хеширования ключа и непосредственно определяет местонахождение исходного кода.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Видно, что когда хеш-операция снова выполняется с ключом, она выполняется.(h = key.hashCode()) ^ (h >>> 16)
原 hashCode 值: 10110101 01001100 10010101 11011111
右移 16 位后的值: 00000000 00000000 10110101 01001100
异或后的值： 10110101 01001100 00100000 10010011
Эта операция заключается в сдвиге значения hashCode ключа и значения hashCode вправо на 16 бит.XOR (1 для разных, 0 для одинаковых), который должен смешивать старшие и младшие биты хеш-значения вместе, чтобы сгенерированное хеш-значение могло быть более дискретным.
Мне нужно объяснить здесь. Из предыдущего введения мы знаем, что диапазон емкости массива составляет [0,2 ^ 30]. Это число все еще относительно велико, а емкость обычно используемого массива относительно мала, например размер по умолчанию 16. Предположим, значения hashCoe, сгенерированные тремя разными ключами, следующие:
19305951 00000001 00100110 10010101 11011111
128357855 00000111 10100110 10010101 11011111
38367 00000000 00000000 10010101 11011111
Общим для всех трех из них является то, что младшие 16 бит абсолютно одинаковы, а старшие 16 бит разные.При вычислении их индексов в массиве передайте (n-1)&hash, где n равно 16, n- 1=15 , двоичное представление 15
00000000 00000000 00000000 00001111
Используйте 19305951, 128357855, 38367 для выполнения & операции с 15, результат будет следующим
После расчета оказывается, что их результаты совпадают, то есть они будут помещены в связанный список или красно-черное дерево под одним и тем же индексом, что явно не соответствует нашим ожиданиям.
Таким образом, XOR хэша и его значения сдвигается вправо на 16 бит, а затем И с 15, чтобы увидеть конфликт хэшей.
Видно, что после сдвига на 16 бит вправо и последующего выполнения операции XOR, а затем вычисления соответствующего индекса массива, он разбивается на разные сегменты, что решает проблему коллизии хэшей.
Суммировать
На самом деле, в HashMap есть еще много моментов, которые стоит изучить.Поняв два вышеуказанных момента, вы вздохнете, что способности автора писать код действительно хороши.Нам нужно извлечь уроки из этих идей в нашей работе.Я надеюсь, что через мой объяснение, вы можете освоить эти два знания.Нажмите, если вы не понимаете, вы можете оставить сообщение или личное сообщение мне
Добро пожаловать в официальный аккаунт [Белые зубы каждый день], получайте свежие статьи, давайте общаться и добиваться успехов вместе!