HashMap серии Java Collection

Java

HashMap серии Java Collection

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

  1. Базовая структура данных HashMap
  2. Основной API
  3. Взаимное расширение (мощность, коэффициент загрузки, кратный 2)
  4. Не потокобезопасный

1. Базовая структура данных HashMap

Нижний слой HashMap представляет собой структуру данных массива плюс связанный список.Каждый элемент массива ведет к связанному списку через указатель.Хвостовой указатель связанного списка указывает на NULL.Структура этого элемента следующая :

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
        ....
        }

Как видите, K и V сохраняются, а затем следующий указатель указывает на следующий элемент.

2. Основной API

Знать структуру хранения недостаточно, как элементы попадают в эту коллекцию? Давайте взглянем на основной API, поставим и получим.

положить () объяснение:

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
        //key为null时，直接丢到table[0]这个数组位置上
            return putForNullKey(value);
        //自己封装的hash方法，对key做完hash后加了高位运算，尽量避免Hash碰撞
        int hash = hash(key);
        //根据hash值`对数组长度取模`,算出应该放入索引为几的数组格子里
        int i = indexFor(hash, table.length);
        //如果这个格子里已经有元素了，那么就遍历执行equals方法，如果equals也一样，就用value替换掉oldValue。返回oldValue
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //如果这个数组隔离里没有equals一样的，把这个元素加入到链表的头部。
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

Когда мы помещаем элемент в HashMap, сначала пересчитываем хеш-значение в соответствии с хэш-кодом ключа и получаем позицию (т.е. индекс) этого элемента в массиве в соответствии с хэш-значением.Если в нем уже хранятся другие элементы позицию массива, то элементы в этой позиции будут храниться в виде связанного списка, вновь добавленные элементы помещаются в начало цепочки, а первые добавленные элементы помещаются в конец цепочки. Если в этой позиции в массиве нет элемента, элемент непосредственно помещается в эту позицию в этом массиве. Также видно, что когда пара ключ-значение,Не учитывает значение в Entry вообще, просто по ключу для расчета и определения места хранения каждой записи. Мы можем полностью рассматривать значение в наборе карт как дочернюю часть ключа.Когда система определяет место хранения ключа, значение(может быть NULL), а затем сохраните его там.

Вот, кстати, почему длина массива HashMap должна быть кратна 2 (по умолчанию 16) при расширении, на самом деле это связано с методом indexFor(), который вычисляет соответствующий индекс в массиве по хеш-значение ключа, вы можете подумать, что прямое использование длины массива hash% может гарантировать, что элементы будут распределены в массиве как можно более равномерно, чтобы избежать меньшего количества коллизий? Однако эффективность взятия по модулю относительно невысока, поэтому реализация этого API выглядит следующим образом:

static int indexFor(int h, int length) {  
    return h & (length-1);
}

Чтобы иметь тот же эффект, что и h%length, h&(length-1) должен гарантировать, что длина длины кратна 2. А почему, младший брат не знает, таков алгоритм. Символ & гораздо более эффективен, чем символ %. Так все знают. Почему длина массива должна быть кратна 2. В целом, когда длина массива равна n-й степени числа 2, вероятность того, что разные ключи будут вычислены с одинаковым индексом, относительно мала, тогда данные распределяются по массиву равномерно, т. е. вероятность коллизий невелико Относительно запроса Когда нет необходимости обхода связанного списка в определенной позиции, эффективность запроса будет выше.

Подводя итог put() немного:Когда программа пытается поместить пару ключ-значение в HashMap, программа сначала определяет место хранения Entry в соответствии с возвращаемым значением hashCode() ключа: если возвращаемое значение hashCode() Ключи двух записей одинаковы, то и место их хранения одинаковое. Если ключи этих двух Записей возвращают значение true при сравнении на равенство, значение вновь добавленной Записи перезапишет значение исходной Записи в коллекции, а ключ — нет. Если ключи этих двух Записей возвращают false при сравнении на равенство, вновь добавленная Запись образует цепочку Записей с исходной Записью в коллекции, а вновь добавленная Запись находится во главе цепочки Записей..

получить () объяснение:

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
    
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

На самом деле каждый должен понимать это сам, это относительно просто, получая элемент из HashMap, сначала вычислить hashCode ключа, найти элемент в соответствующей позиции в массиве, а затем использовать равенство метод ключа, чтобы найти потребность в связанном списке соответствующей позиции.Элементы.

Хорошо, сводка по хранению и чтению элементов:Проще говоря, HashMap обрабатывает ключ-значение как единое целое внизу, и это целое является объектом Entry. Нижний слой HashMap использует массив Entry[] для хранения всех пар ключ-значение.Когда объект Entry необходимо сохранить, его место хранения в массиве будет определено в соответствии с алгоритмом хеширования, а его местоположение в массиве будет определяется по методу equals.Место хранения в связанном списке, когда Запись нужно вынуть, она также найдет место хранения в массиве по алгоритму хеширования, а затем вынет Запись из связанного список в этом месте в соответствии с методом equals.

3. Связано с расширением мощностей (мощность, коэффициент загрузки, кратный 2)

Когда элементов в HashMap становится все больше и больше, вероятность коллизии хэшей все выше и выше, потому что длина массива по умолчанию равна 16. Поэтому для повышения эффективности запроса необходимо расширить массив HashMap.Операция расширения массива появится и в ArrayList.Это обычная операция.После расширения массива HashMap наибольшая производительность появляется точка потребления:Данные в исходном массиве должны пересчитать свое положение в новом массиве и вставить его, что является изменением размера.

Итак, когда HashMap расширится? Когда количество элементов в HashMap превышает (размер массива XloadFactor), массив будет расширен.Значение loadFactor по умолчанию равно 0,75, что является компромиссным значением. То есть по умолчанию размер массива равен 16, затем, когда количество элементов в HashMap превышает 16X0,75=12, размер массива расширяется до 2X16=32, то есть удваивается (подумайте о том, что я говорил ранее о кратности 2), а затем пересчитать позицию каждого элемента в массиве, что является очень затратной операцией, поэтому, если мы уже знаем количество элементов в HashMap, предустановленное количество элементов может быть эффективным Улучшить производительность HashMap.

Далее, кстати, упоминаются несколько методов построения HashMap:

  • HashMap(): создает HashMap с начальной емкостью 16 и коэффициентом загрузки 0,75.
  • HashMap(int initialCapacity): создает HashMap с начальной емкостью initialCapacity и коэффициентом загрузки 0,75.
  • HashMap(int initialCapacity, float loadFactor): создайте HashMap с указанной начальной емкостью и указанным коэффициентом загрузки.

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

4. Не потокобезопасный

Чтобы упомянуть немного, HashMap не является потокобезопасным, Когда используется многопоточный одновременный доступ, расширение может привести к тому, что связанный список после элемента массива образует замкнутый цикл, поэтому запрос всегда находится в бесконечном цикле, получается 100% утилизация. Поэтому ConcurrentHashMap следует использовать вместо этого в многопоточной среде. ConcurrentHashMap объясню позже.Кроме того, почему HashMap вызывает такой бесконечный цикл, ведь статей в интернете больше, не буду лишним, и приведу несколько порталов:

Эпилог

Что ж, HashMap закончен для всех, и я продолжу делиться с вами базовыми знаниями о коллекциях Java в будущем.Кончено, хорошего дня!

Категории