В те годы HashMap мы любили и ненавидели (1)

1. Знакомство с коллекцией HashMap

Функции:

• HashMap — важный класс реализации интерфейса Map, основанный на хеш-таблице, он хранит данные в форме ключ-значение и не является потокобезопасным;
• В качестве ключа можно использовать Null, такой ключ может быть только один, и может быть один или несколько ключей, соответствующих значению null;
• Элементы доступа неупорядочены.

Базовая структура данных:

• До JDK1.8 он состоял из массива + связанный список, который является основным хранилищем данных, а связанный список существует для разрешения конфликтов хэшей;
• После JDK1.8 он состоит из массива + связанного списка + красно-черного дерева.Когда длина связанного списка больше порога (по умолчанию 8), а длина массива больше 64, связанный список будет преобразован в красно-черное дерево для разрешения хеш-конфликтов.

Уведомление:Решение будет принято до того, как связанный список будет преобразован в красно-черное дерево.Если порог больше 8, но длина массива меньше 64, то связанный список не будет преобразован в красно-черное дерево для хранить данные, но будет расширять массив.

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

HashMap хранит диаграмму структуры данных:

2. Процесс хранения данных внизу HashMap

1. Проанализируйте, как показано в следующем коде:

package hashmap_demo;
import java.util.HashMap;
public class HashMapTest {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("柳岩", 18);
        map.put("杨幂", 28);
        map.put("刘德华", 40);
        map.put("柳岩", 20);
        System.out.println(map);
    }
}
//输出结果：{杨幂=28, 柳岩=20, 刘德华=40}

2. Схема хранимой процедуры HashMap:

3. Анализ хранимых процедур:

1. При выполненииHashMap<String, Integer> map = new HashMap<>();Когда эта строка кода создает объект экземпляра HashMap; до JDK1.8 в конструкторе создается массив таблиц Entry[] длиной 16 для хранения пар ключ-значение; после JDK1.8 время создания массива изменилось, вместо создания массива в конструкторе первый вызовput()метод (то есть добавление элемента в HashMap в первый раз) для создания массива таблиц Node[].

Уведомление:Создание объектов экземпляра HashMap изменилось до и после JDK1.8.Есть два основных момента: изменилось время создания, изменился тип массива, по сравнению с исходнымEntry[]тип становитсяNode[]тип.

2. Сохранить в хеш-таблице柳岩-18, будет основываться на柳岩перечислитьStringПереопределено в классеhashCode()метод расчета柳岩Соответствующее хэш-значение, а затем в сочетании с длиной массива для расчета с использованием определенного алгоритма柳岩Значение индекса в массиве Node[]. Если в этой позиции индекса нет данных, непосредственно柳岩-18Вставьте в эту индексную позицию. такие как расчет柳岩Соответствующий индекс равен 3, как показано на рисунке выше.

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

Ответ. Вычислите хеш-значение, используя метод hashCode() ключа, а затем выполните сдвиг вправо без знака (>>>), побитовое исключающее ИЛИ (^) и побитовое И (&) в сочетании с длиной массива для рассчитать значение индекса; Вы можете использовать метод квадрата, остаток и метод псевдослучайных чисел.

Возьмем остаток: 10%8=2 11%8=3, битовая операция наиболее эффективна, а другие методы менее эффективны.

3. Сохранить в хеш-таблице杨幂-28, считается, что в позиции индекса нет данных, и он вставляется напрямую.

4. Сохранить в хеш-таблице刘德华-40, предполагая刘德华Вычисленный индекс также равен 3, тогда позиция индекса в это время не равна нулю, и нижний слой будет сравнивать柳岩и刘德华Согласовано ли хеш-значение, если нет, нарисуйте узел в этой позиции индекса для хранения刘德华-40, этот метод называется методом застежки-молнии.

Дополнение: Исходный код расчета индексаp = tab[i = (n - 1) & hash], то есть индекс = хэш-значение & (длина массива - 1), операция побитового И эквивалентна операции остатка, т.к. 51%16=3, 19%16=3, поэтому появится тот же массив с тем же индексом value, Но значение хеш-функции другое.

5. Наконец сохранить в хеш-таблице柳岩-20,柳岩Соответствующее значение индекса равно 3. Поскольку в позиции индекса уже есть данные, в это время они будут сравниваться.柳岩Равно ли оно хэш-значению других данных в этой позиции индекса, если оно равно, происходит коллизия хэшей. В этот момент нижний слой вызовет柳岩принадлежатьStringв классе строкequals()метод сравнивает, является ли содержимое двух объектов одинаковым:

То же самое: значение добавленных позже данных перезапишет предыдущее значение, т.е.柳岩-20перезаписывать柳岩-18.

Не идентичны: продолжайте сравнивать с другими объектами в позиции индекса.Если они не идентичны, нарисуйте узел для хранения (метод застежки-молнии).

Примечание. Если позиция индекса заархивирована, то есть длина связанного списка больше порогового значения 8, а длина массива больше 64, связанный список будет преобразован в красно-черное дерево. Поскольку временная сложность связанного списка равна O(N), временная сложность красно-черного дерева равна O(logN) и O(N)>O(logN), когда длина связанного списка велика.

В-третьих, механизм расширения HashMap.

1. Когда HashMap будет расширен?

Первый взгляд на добавление элементовput()Поток метода:

инструкция:

• на картинке вышеsizeвыражатьHashMapсерединаK-VКоличество в реальном времени, не равное длине массива;
• threshold(критическое значение) =capacity(емкость массива)*loadFactory(коэффициент загрузки), критическое значение представляет собой максимальное значение занятого в данный момент массива.sizeЕсли этот порог превышен, вызовresize()способ расширения, емкость после расширения в два раза превышает первоначальную;
• по умолчанию,16*0.75=12,СейчасHashMapэлементы, хранящиеся более чем в12будет расширен.

2. Каков размер HashMap после расширения?

是原来容量的2倍，即HashMap是以2n进行扩容的。

3. Какова начальная емкость HashMap по умолчанию?

Конструкция HashMap без параметров, начальное значение по умолчанию равно 16, исходный код выглядит следующим образом:

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

Источник начального значения по умолчанию:

/**
 * The default initial capacity - MUST be a power of two.
 * 默认初始容量必须是2的幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

Как видно из исходного кода,HashMapНачальная емкость по умолчанию, равная 1, сдвинута влево на 4 бита, то есть 1*2 в 4-й степени равно 16. При инициализации с использованием конструктора HashMap без аргументов в первый разputэлемент, вызоветresize()метод (метод расширения), емкость после расширения 16. это иArrayListПроцесс инициализации аналогичен (с использованиемArrayListПри инициализации конструктора без аргументов создается пустой массив, который запускается при первом добавлении элемента в пустой массив.grow()Метод расширения, емкость после расширения 10).

4. Почему указанная начальная емкость должна быть степенью числа 2?

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

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

То есть создает пустое пространство с указанной вместимостью и коэффициентом загрузки по умолчанию (0,75).HashMap.

Из вышеизложенного мы знаем, что когдаHashMapПри добавлении элементов вkeyХэш-значение объединяется с длиной массива для вычисления позиции индекса.HashMapДля эффективного доступа необходимо уменьшить коллизии хешей и равномерно распределить данные.Для расчета значения индекса используется побитовое И **хеш&(длина-1)**.

HashMapИндекс рассчитывается с использованием алгоритма остатка, т.е.hash%length, но операция остатка не так эффективна, как битовая операция, поэтому нижний уровень использует операцию побитового И **хэш&(длина-1)**. Предпосылка, что два алгоритма эквивалентны, состоит в том, чтоlengthравно 2 в энной степени.

5. Почему это равномерно распределено?

Нам нужно знать два вывода:

• N-я степень 2 равна n 0 после 1. Например, 4-я степень 2 равна 16, а двоичное представление равно 10000;
• 2 в n-й степени -1 равно n единицам, например, 2 в 4-й степени -1 равно 15, а двоичное представление равно 1111.

Пример того, почему массив, длина которого равна 2 в степени n, может быть распределен равномерно:

按位与运算：相同二进制位上都是1，结果为1，否则为0。
假设数组长度为2的3次幂8，哈希值为3，即3&（8-1）=3，索引为3；
假设数组长度为2的3次幂8，哈希值为2，即2&（8-1）=2，索引为2；
运算过程如下：
3&（8-1）
0000 0011 -->3
0000 0111 -->7
----------------
0000 0011 -->3

2&（8-1）
0000 0010 -->2
0000 0111 -->7
----------------
0000 0010 -->2

结论：索引值不同，不同索引位置都有数据分布，分布均匀。

Предполагая, что длина массива не является n-й степенью числа 2, например, длина равна 9, процесс работы выглядит следующим образом:

假设数组长度为9，哈希值为3，即3&（9-1）=3，索引为0；
假设数组长度为9，哈希值为2，即2&（9-1）=2，索引为0；
运算过程如下：
3&（9-1）
0000 0011 -->3
0000 1000 -->8
----------------
0000 0000 -->0

2&（9-1）
0000 0010 -->2
0000 1000 -->8
----------------
0000 0000 -->0

结论：索引值都为0，导致同一索引位置上有很多数据，而其他索引位置没有数据，致使链表或红黑树过长，效率降低。

Уведомление: hash%lengthЭквивалентноhash&（length-1）Условием является то, что длина массива равна n-й степени числа 2. Поскольку нижний слой использует побитовую операцию И для вычисления значения индекса, необходимо убедиться, что длина массива должна быть n-й степенью числа 2.

6. Что делать, если указанная начальная емкость не равна 2 в n-й степени?

这时HashMap会通过位运算和或运算得到一个2的幂次方数，并且这个数是离指定容量最小的2的幂次数。比如初始容量为10，经过运算最后会得到16。

Исходный код, задействованный в этом процессе, выглядит следующим образом:

//创建HashMap集合对象，并指定容量为10，不是2的幂
HashMap<String, Integer> map = new HashMap<>(10);
//调用有参构造
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//this关键字继续调用
public HashMap(int initialCapacity, float loadFactor) {//initialCapacity=10
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10
}
//调用tableSizeFor()方法
/**
* Returns a power of two size for the given target capacity.
* 返回指定目标容量的2的幂。
*/
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;
}

Анализ нижеtableSizeFor()метод:

• int n = cap - 1;Зачем вычитать 1 операцию?

这是为了防止`cpa`已经是2的幂了。如果`cpa`已经是2的幂，又没有执行减1的操作，则执行完下面的无符号右移后，返回的将为`cap`的2倍。

• Когда n равно 0, возвращается 1. Случай, когда вы равны 0, здесь не обсуждается.
• |Указывает на операцию побитового ИЛИ: правило операции состоит в том, что все одинаковые двоичные биты равны 0, результат равен 0, иначе он равен 1.

1-я операция:

int n = cap - 1;//cap=10，n=9
n |= n >>> 1;//无符号右移1位，然后再与n进行或运算
00000000 00000000 00000000 00001001  //n=9
00000000 00000000 00000000 00000100  //9无符号右移1位变为4
-----------------------------------------------
00000000 00000000 00000000 00001101  //按位或运算结果为13，即此时n=13

2-я операция:

int n = 13
n |= n >>> 2;
00000000 00000000 00000000 00001101  //n=13
00000000 00000000 00000000 00000011  //13无符号右移2位变为3
------------------------------------------------
00000000 00000000 00000000 00001111  //按位或运算结果为15，即此时n=15

3-я операция:

int n = 15
n |= n >>> 4;
00000000 00000000 00000000 00001111  //n=15
00000000 00000000 00000000 00000000  //15无符号右移4位变为0
------------------------------------------------
00000000 00000000 00000000 00001111  //按位或运算结果为15，即此时n=15

Все результаты следующих операций равны n=15, потому что существуетn + 1операции, окончательный результат равен 16.

Суммировать:Из приведенного выше процесса операции видно, что если заданная начальная мощность не является n-й степенью числа 2, то после операции будет получена наименьшая степень числа 2 из начальной мощности.

В-четвертых, анализ исходного кода HashMap.

1. Переменные-члены

private static final long serialVersionUID = 362498820763181265L; //序列化版本号

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //初始化容量，必须是2的n次幂

static final int MAXIMUM_CAPACITY = 1 << 30; //集合最大容量：2的30次幂

static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的加载因子
/**1.加载因子是用来衡量HashMap的疏密程度，计算HashMap的实时加载因子的方法为：size/capacity；
  *2.加载因子太大导致查找元素效率低，太小导致数组的利用率低，默认值为0.75f是官方给出的一个较好的临界值；
  *3.当HashMap里面容纳的元素已经达到HashMap数组长度的75%时，表示HashMap太挤了，需要扩容，而扩容这个过程涉及到rehash、复制数据等操作，非常消耗性能，所以开发中尽量减少扩容的次数，可以通过创建HashMap集合对象时指定初始容量来尽量避免扩容；
  *4.同时在HashMap的构造方法中可以指定加载因子大小。
  */
HashMap(int initialCapacity, float loadFactor) //构造一个带指定初始容量和加载因子的空HashMap

static final int TREEIFY_THRESHOLD = 8; //链表转红黑树的第一个条件，链表长度大于阈值8

static final int UNTREEIFY_THRESHOLD = 6; //删除红黑树节点时，当红黑树节点小于6，转化为链表

static final int MIN_TREEIFY_CAPACITY = 64; //链表转红黑树的第二个条件，数组长度大于64

Пять, общие вопросы интервью

1. Каковы условия возникновения коллизии хэшей?

两个对象的索引相同，并且hashCode（即哈希值）相等时，会发生哈希碰撞。

2. Как разрешать коллизии хешей?

JDK1.8之前，采用链表解决；JDK1.8之后，采用链表+红黑树解决。

3. Если хэш-код двух ключей один и тот же, как их сохранить?

使用equals比较内容是否相同：

相同：后添加的value值会覆盖之前的value值；

不相同：划出一个节点存储（拉链法）。

4. Основная структура данных HashMap?

JDK1.8: массив + связанный список + красно-черное дерево. Массив является основным телом, а связанный список и красно-черное дерево существуют для разрешения коллизий хэшей, как показано на следующем рисунке:

5.Почему JDK1.8 представил красно-черное дерево? Не сложнее ли структура красно-черного дерева?

До JDK1.8 базовые данные HashMap представляли собой массив + связанный список.Мы знаем, что даже если хеш-функция выполнена хорошо, трудно добиться 100% равномерного распределения элементов в хеш-таблице. Когда большое количество элементов в HashMap существует в одном и том же сегменте (одинаковая позиция индекса), в этом сегменте будет создан очень длинный связанный список. В настоящее время HashMap эквивалентен структуре односвязного списка. n на односвязных элементах списка, временная сложность обхода составляет O(n), а эффективность обхода очень низкая. В ответ на эту ситуацию JDK1.8 ввел красно-черное дерево, а временная сложность обхода красно-черного дерева составляет O(logn).Так как O(n)>O(logn), эта задача была оптимизирована.

6. Почему он преобразуется в красно-черное дерево только тогда, когда длина связанного списка больше 8?

Мы знаем, что 8 — это порог преобразования связанного списка в красно-черное дерево, в исходниках есть такой комментарий:

/** Because TreeNodes are about twice the size of regular nodes, we use them only when     * bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they         * become too small (due to removal or resizing) they are converted back to plain bins.   * In usages with well-distributed user hashCodes, tree bins are rarely used.  Ideally,   * under random hashCodes, the frequency of nodes in bins follows a Poisson distribution
  * (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on   * average for the default resizing threshold of 0.75, although with a large variance     * because of resizing granularity. Ignoring variance, the expected occurrences of list   * size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
  *
  * 0:    0.60653066
  * 1:    0.30326533
  * 2:    0.07581633
  * 3:    0.01263606
  * 4:    0.00157952
  * 5:    0.00015795
  * 6:    0.00001316
  * 7:    0.00000094
  * 8:    0.00000006
  * more: less than 1 in ten million
  */

Переведенное значение означает:

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

Из вышеприведенного анализа можно сделать вывод, что:

• Если оно меньше порога 8, используется красно-черное дерево, что изначально сильно усложнит структуру;
• Если связанный список используется больше, чем пороговое значение 8, узлы связанного списка не будут использоваться полностью;
• Следовательно, пороговое значение 8 является научно обоснованным значением, которое является компромиссным значением между пространством и временем.

7. Почему коэффициент загрузки установлен равным 0,75? Граничное значение равно 12?

• Если коэффициент загрузки равен 0,4, то 16 * 0,4 = 6, что приводит к расширению массива, когда он заполнен на 6 пробелов, что приводит к низкой степени использования массива;

• Если коэффициент загрузки равен 0,9, то 16*0,9=14, что сделает массив слишком полным, и велика вероятность того, что связанный список под определенным узлом индекса будет слишком длинным, что приведет к низкой эффективности поиска элементов ;

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