HashMap, который должен знать каждый Java-программист

Node.js Java задняя часть Безопасность

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

Но почему вы хотите объяснить java8 HashMap? Все мы знаем, что в Java8 есть много больших изменений и изменений, таких как функциональное программирование, и HashMap также имеет относительно большое изменение.

Сначала узнайте о карте

Общие типы карт следующие:

ХэшКарта:
  • беспорядок
  • Быстрый доступ
  • Ключ не может быть повторен (разрешен только один нулевой ключ)
LinkedHashMap:
  • аккуратный
  • Подкласс HashMap
Карта дерева:
  • Записи, сохраненные в TreeMap, будут отсортированы по ключу (по умолчанию — в порядке возрастания), поэтому записи, полученные при обходе с помощью Iterator, будут отсортированы.
  • Поскольку требуется сортировка, ключ в TreeMap должен реализовывать интерфейс Comparable, иначе будет сообщено об исключении ClassCastException.
  • TreeMap будет судить, повторяется ли ключ в соответствии с методом compareTo его ключа.

В дополнение к вышесказанному мы могли видеть класс под названием Hashtable:

Хеш-таблица:
  • Унаследованный класс, потокобезопасный, аналогичный HashMap.
  • Если потокобезопасность не требуется, вместо этого выберите HashMap.
  • Когда вам нужен поточно-ориентированный подход вместо использования ConcurrentHashMap

HashMap

Теперь давайте формально взглянем на HashMap.

Во-первых, давайте взглянем на некоторые из основных функций HashMap:

  • Используйте хеш-таблицу (хеш-таблицу) для хранения данных, а для разрешения конфликтов используйте метод цепочек адресов.
  • Когда длина связанного списка больше или равна 8, преобразуйте связанный список в красно-черное дерево для хранения.
  • Каждый раз осуществляется расширение второй мощности, то есть расширение в два раза превышает первоначальную мощность

поле

Hashmap имеет следующие поля:

  • Node[] table: хэш-таблица для хранения данных, начальная длина Length = 16 (DEFAULT_INITIAL_CAPACITY), емкость удваивается (n * 2) при расширении
  • final float loadFactor: коэффициент загрузки, который определяет соотношение между длиной массива и максимальным значением пары ключ-значение, которое может быть сохранено в данный момент; не рекомендуется легко изменять его, если нет особых обстоятельств
  • int threshold: предел допустимых пар ключ-значение; порог = длина * коэффициент загрузки, когда существующие пары ключ-значение превышают это значение, емкость будет расширена
  • int modCount: количество модификаций структуры HashMap (например, каждый раз, когда ставится новое значение, оно будет увеличиваться на 1)
  • int size: текущее количество ключей-значений

Стоит отметить, что начальный размер массива в HashMap равен 16, почему так? Я расскажу об этом позже, когда буду говорить о методе put.

метод

hash(Object key)

Все мы знаем, что метод hashCode класса Object тесно связан с HashMap, поскольку HashMap использует hashCode для определения места хранения ключа в массиве. (Каждый должен понимать взаимосвязь и соглашение между методами hashCode и equals, поэтому я не буду говорить об этом здесь)

Это было по-другому до Java 8, а теперь Java 8 улучшает это и оптимизирует алгоритм.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Стоит отметить, что HashMap не использует hashCode напрямую в качестве значения хеш-функции, а выполняет ряд операций сдвига и XOR над хэш-кодом с помощью хеш-метода. Цель этой обработки — эффективно избежать коллизий хэшей.

Мы можем видеть, что с помощью этого метода расчета старшие 16 бит хеш-значения ключа остаются неизменными, а младшие 16 бит и старшие 16 бит подвергаются операции XOR в качестве окончательного хэш-значения ключа; позже мы узнаем, что HashMap проходит(n - 1) & hashдля определения позиции элемента (где n - текущий размер массива)

Очевидно, что этот метод расчета определяет, что положение элемента связано только с младшим значением, что увеличит вероятность коллизии хэшей, поэтому мы используем обработку XOR старших и младших битов хэш-значение, чтобы уменьшить вероятность столкновения.Сделайте положение элемента не только зависящим от младшего порядка

put(K key, V value)

Метод помещается внутрь HashMap, в самом ядре метода, проблема связана с хранением данных HashMap.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

Метод put напрямую вызывает метод putVal.Здесь я добавил комментарий для всех, вы можете почувствовать это шаг за шагом с помощью следующей блок-схемы:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K, V>[] tab;
    HashMap.Node<K, V> p;
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        //初始化哈希表
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        //通过哈希值找到对应的位置，如果该位置还没有元素存在，直接插入
        tab[i] = newNode(hash, key, value, null);
    else {
        HashMap.Node<K, V> e;
        K k;
        //如果该位置的元素的 key 与之相等，则直接到后面重新赋值
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof HashMap.TreeNode)
            //如果当前节点为树节点，则将元素插入红黑树中
            e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
        else {
            //否则一步步遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //插入元素到链尾
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        //元素个数大于等于 8，改造为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                //如果该位置的元素的 key 与之相等，则重新赋值
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //前面当哈希表中存在当前key时对e进行了赋值，这里统一对该key重新赋值更新
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //检查是否超出 threshold 限制，是则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Основные логические шаги здесь:

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

(1) Почему начальный размер HashMap 16

Всякий раз, когда элемент вставляется, нам нужно вычислить позицию значения в массиве, т.е.p = tab[i = (n - 1) & hash].

Когда n = 16, n - 1 = 15, а двоичный - 1111. В это время при выполнении и работе с хешем положение элемента полностью зависит от размера хеша

Если это не 16, например, n = 10, n - 1 = 9, двоичное значение равно 1001, что легко повторить значение, например, 1101 и 1001, 1011 и 1001, 1111 и 1001, и результат тот же , Таким образом, выбор 16 и каждого расширения также известен по двум причинам.

(2) Ленивая загрузка

Мы можем найти в конструкторе HashMap, что хеш-таблица Node[] table не инициализирована в начале; наблюдая за методом put, мы можем найти:

if ((tab = table) == null || (n = tab.length) == 0)
      n = (tab = resize()).length;

Когда хеш-таблица окажется пустой или длина равна 0, она будет инициализирована методом resize, очевидно, здесь используется принцип ленивой загрузки, при первом использовании хэш-таблицы она будет инициализирована. .

(3) Древовидность

В Java8 самым большим изменением HASHMAP является добавление обработки дерева. Когда элементы в связанном списке больше или равны 8, можно преобразовать связанный список в структуру данных красно-черных деревьев. Почему я Скажи, что можно здесь?

final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) {
    int n, index; HashMap.Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        //......
}

Мы можем наблюдать, что метод лечения деревьев, обнаружил, что когдаtab == null || (n = tab.length) < MIN_TREEIFY_CAPACITYКогда это правда, будет выполняться только обработка раскрытия без дерева; MIN_TREEIFY_CAPACITY указывает, что минимальная емкость таблицы, которую HashMap может разбить на деревья, равна 64, потому что, когда емкость хеш-таблицы в начале мала, вероятность коллизии хешей будет выше. , Он относительно велик, и в настоящее время вероятность длинного связанного списка будет немного больше.Для длинного связанного списка, созданного по этой причине, мы должны отдавать приоритет расширению, чтобы избежать такого ненужного дерева.

Итак, зачем нужно дерево HashMap? Все мы знаем, что эффективность запроса связанного списка намного ниже, чем у массива, и когда слишком много элементов связано в связанный список, производительность доступа к запросу будет сильно снижена; в то же время это также связано с проблема безопасности, некоторые коды могут использоваться для создания хэша. Конфликтующие данные будут атаковать систему, что вызовет большую загрузку ЦП сервера.

resize()

Метод расширения также является очень важным методом в HashMap, а также является относительно интенсивной операцией.

Все мы знаем, что массивы не могут быть автоматически расширены, поэтому нам нужно пересчитать новую емкость, создать новый массив, скопировать все элементы в новый массив и освободить данные старого массива.

В отличие от прошлого, Java8 предусматривает, что каждое расширение HashMap в два раза больше предыдущего (n * 2), и из-за этого новая позиция индекса каждого элемента в массиве может быть только в двух случаях, один - один и тот же, другой — исходная позиция + длина расширения (то есть значение смещения — это длина расширения); с другой стороны, до Java8 каждое расширение должно пересчитывать позицию индекса каждого значения в массиве, что увеличивает потребление производительности .

Позвольте мне кратко объяснить вам, что означает предыдущий абзац: Когда мы говорили о размещении ранее, мы знаем, что позиция каждого элемента в массиве хеш-таблицы равна (n - 1) & hash, где n — размер текущего массива, а hash — значение хеш-функции, вычисленное методом метод hash, упомянутый ранее.

Как мы видим на рисунке, позиции в итоговом вычисляемом массиве двух хеш-значений 0001 0101 и 0000 0101 до расширения равны 0000 0101, что равно 5, а размер массива равен 0000 1111 + 1. , то есть 16

После расширения массив удваивается с 16 до 32 (0001 1111).В это время вычисленные результаты двух исходных хеш-значений равны 0001 0101 и 0000 0101 соответственно, а именно 21 и 5. Разница между двумя числа ровно 16, то есть размер расширения массива

Это на самом деле очень легко понять.После того, как массив расширится до удвоенного исходного размера, n - 1 изменится на 2n - 1, то есть изменился старший бит исходного двоичного файла.

Следовательно, после операции & результатом может быть только два случая, один - отсутствие эффекта, а другой - исходное положение + длина расширения.

Так как же исходный код определяет, какой из этих двух случаев именно он? Как мы упоминали ранее, размер массива в HashMap всегда кратен 16, поэтому старшие биты значений, вычисляемых hash&n и hash&(2n - 1), равны.

Поэтому в исходниках используется очень простой метод (Oldcap - это размер исходного массива, а именно n)

if ((e.hash & oldCap) == 0) {
    ...
} else {
    ...
}

Когда e.hash & oldCap равен 0, позиция элемента не меняется, когда она не равна 0, позиция является исходной позицией + длина расширения

get(Object key)

После понимания механизма хранения HashMap метод get также хорошо понятен.

final HashMap.Node<K,V> getNode(int hash, Object key) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        //检查当前位置的第一个元素，如果正好是该元素，则直接返回
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            //否则检查是否为树节点，则调用 getTreeNode 方法获取树节点
            if (first instanceof HashMap.TreeNode)
                return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
            //遍历整个链表，寻找目标元素
            do {
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

Есть четыре основных шага:

  1. Является ли хеш-таблица пустой или есть элемент в целевом местоположении
  2. это первый элемент
  3. Если это узел дерева, найдите целевой узел дерева.
  4. Если это узел связанного списка, пройдите по связанному списку, чтобы найти целевой узел.
Категории