Коллекция Java (2) - Карта

Это 13-й день моего участия в августовском испытании обновлений. Узнайте подробности события:Испытание августовского обновления

1. Карта

ХэшКарта:
- До JDK 1.8HashMapЗависит от数组+链表состоит, массивHashMapОсновная часть связанного списка в основном предназначена для разрешения конфликта хэшей («метод застежки-молнии» для решения конфликта);
- После JDK 1.8 произошли серьезные изменения в разрешении конфликтов хэшей: когда длина связанного списка больше или равна порогу (по умолчанию 8), связанный список преобразуется в красно-черное дерево (о нем будет судить перед преобразованием связанного списка в красно-черное дерево, если текущий массив Если длина меньше 64, массив будет сначала расширен, а не преобразован в красно-черное дерево) для сокращения времени поиска.
LinkedHashMap:LinkedHashMapунаследовано отHashMap, поэтому его нижний слой по-прежнему основан на хеш-структуре молнии, то есть состоит из массивов и связанных списков или красно-черных деревьев. Кроме тогоLinkedHashMapНа основе вышеизложенного добавляется двусвязный список, чтобы вышеуказанная структура могла поддерживать порядок вставки пар ключ-значение. В то же время, выполняя соответствующие операции над связанным списком, реализуется логика, связанная с последовательностью доступа;
HashTable (потокобезопасный):
- Состав массив + связанный список, массивHashTableОсновное тело и связанный список существуют в основном для разрешения коллизий хэшей;
- не может быть сохраненnullизключ или значение, иначе будет сообщено об ошибкеNullPointException;
- Начиная с JDK 1.0, чемHashMap(JDK 1.2) ранний;
- его подклассыPropertiesболее широко используется
TreeMap: красно-черное дерево (самобалансирующееся отсортированное бинарное дерево)
ConcurrentHashMap: потокобезопасныйHashMap, основная структураHashMapто же самое, ноHashMapне его родительский класс.

1.1 Разница между HashMap и Hashtable

потокобезопасность:HashMapне является потокобезопасным,Hashtableявляется потокобезопасным, потому чтоHashtableВнутренние методы в основном проходят черезsynchronizedМодификация; (если вы хотите обеспечить безопасность потоков, вы можете использоватьConcurrentHashMap)
эффективность: из-за проблем с безопасностью потоковHashMapСравниватьHashtableболее эффективным.Кроме того, Hashtable в основном исключен, а его подклассы используются больше: Свойства ;
поддержка нуля:Hashmapможно хранитьnullключ и значение, ноnullКлюч может быть только один, и он хранится в фиксированной позиции массива (индекс массива равен 0);Hashtableне положеноnullключ и значение, иначе выдать исключениеNullPointerException;
Начальная емкость и размер расширения:
1. Создайте начальное значение емкости:HashMapНачальная емкость по умолчанию 16, после каждого 2-кратного расширения оригинала;HashtableНачальная емкость по умолчанию равна 11, и каждый раз она увеличивается до исходной 2n+1;
2. Создайте начальное значение указанной емкости: если указанная емкость не является степенью числа 2,HashMapуказанная мощность не будет использоваться,HashMapрасширится до степени 2 (tableSizeFor()метод), т.HashMapРазмер емкости всегда равен степени числа 2, что является основным моментом, который будет объяснен ниже;HashtableИспользуйте указанное начальное значение размера напрямую.
базовая структура данных: После JDK 1.8HashMapВ некоторых случаях связанный список будет преобразован в красно-черное дерево;HashtableСтруктура по-прежнему представляет собой массив + связанный список.

2. Анализ основного исходного кода HashMap

Ссылка на ссылку: (Настоятельно рекомендуется посмотреть это видео, чтобы узнать, и область комментариев также великий бог)

воооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооооо

Question

HashMapСвязь между расширением и порядком вставленных элементов?
- JDK 1.7 сначала расширяет, а затем вставляет; JDK 1.8 сначала вставляет, а затем расширяет
HashMapКак вставить узел в связанный список
- До JDK 1.7 использовался метод вставки головы, и нужно было только указать следующий из новых узлов на исходный элемент головы.Для проверки дубликатов нужно написать другой метод;
- После JDK 1.8 - это метод вставки хвоста, который необходимо перейти на весь связанный список. После введения красных черных деревьев в JDK 1.8 необходимо определить количество узлов в одновременно связанном списке (более 8 до красно-черных деревьев), и необходимо провести по одному списку и прочитать Количество узлов. Следовательно, метод интерполяции хвоста используется для определения того, есть ли какие-то дубликаты узлов, в отличие от JDK 1.7, есть другой способ.

2.1 JDK 1.7

Q1: почемуHashMapЯвляется ли размер расширения экспоненциально кратным 2?

indexFor(int hash,int length)Расчет и сохранение по хеш-значению и емкости массиваHashMapИндекс позиции массива: хэш & (длина - 1),

В общем, мы хотим вычислить позицию нижнего индекса, хранящуюся в массиве, используя数组长度-1Возьмите остаток. а теперь замените его на&运算Эффективность вычислений может быть значительно улучшена. Такие как:

Например: когда емкость равна 16, вычислить хэш и 15

Предположим, хеш = 0101 0101

hash & 15

Двоичная длина должна быть 32 бита, сокращенно здесь, например

=> 0101 0101

& 0000 1111

Результат 0101 = 5, индекс массива элемента в позиции контейнера равен 5;

1. Повышение вычислительной эффективности: этот алгоритм, основанный наlength=16Например: вы можете контролировать, чтобы результат находился в диапазоне емкости контейнера, потому что максимальный индекс массива в контейнере равенlength - 1двоичный, а размер контейнера должен быть ограничен степенью 2, что可以Настолько высокие двоичные 0, 1 низкие, то hashCode& 运算,hashСтаршие 28 бит двоичного кода не имеют смысла, &0 равен 0, поэтому окончательный результат все еще находится в памяти.hashМладшие 4 бита двоичного иlength - 1Расчет младшего порядка должен превалировать, а диапазон значений равен [0,length-1], так как хранение данных в хеш-таблице занимает остаток ее емкости, а при использовании механизма экспоненциального кратного емкости из 2, вы можете использовать&运算Вместо операции остатка улучшите вычислительную эффективность;

ЗачемHashMapЯвляется ли размер расширения экспоненциально кратным 2? Это и причина и следствие, гениальность алгоритма

2. Удобно распределять элементы равномерно при пересчете позиции хеша после динамического расширения: Q5 (обнаружен и используется только в JDK 1.8)
Q2:HashMapПри сохранении значения вычисляйте хеш-значение: после получения хэш-кода ключа зачем вам нужно выполнять операцию сдвига вправо и операцию XOR для получения хэш-значения?

Такие какQ1Вывод такой, что при вычислении индекса массива места хранения результат только тот же, что иhashнизкий уровень,hashНет смысла участия в высокой позиции , что приведет к высокой частоте повторения вычисляемых индексов массива (больше хеш-конфликтов), а связанный список, сгенерированный одним узлом, имеет долгий процесс.getПри получении значения приходится обходить длинный связанный список, что снижает эффективность.

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

Например: хэш=>0011 1101 0101 (аббревиатура)

сдвиг вправо >>> 4 => 0000 0011 1101

Исключающее ИЛИ ^ 0011 1101 0101

Улучшение хэшируемости HashMap

В приведенном выше примере не используетсяHashMapНастоящий сдвиг вправо, метод операции XOR, смысл именно в этом.
Q3:HashMapизsize()метод

возвращаться напрямуюsizeНедвижимость, потому что каждый разputновые элементы,sizeоба +1;

не звонитsize()метод, пройдите по длине связанного списка под каждым узлом всего массива.
Q4:HashMapсуществуетputПри добавлении элементов оценка покрытия будет сделана, когдаhashравны, и значения ключей равны (суждение здесь включает==,а такжеequals()суждение), почему сначалаhashсудить?
Положение о hashCode: (хэш также рассчитывается по hashCode)
- Два объекта равны, хэш-код должен быть равен
- Два объекта не равны, и хэш-код не обязательно равен
- хэш-код равен, два объекта не обязательно равны
- Хэш-код не равен, два объекта должны быть разными
а также,equals()Как правило, это нужно переписать пользователю, и логика внутри более сложная.Тогда, согласно приведенным выше спецификациям, сначала судитеhash, эффективность намного выше.
Q5:HashMapПосле расширения положение исходного элемента в массиве может не измениться, а может измениться

Метод вычисления нижнего индекса массива: hash & (длина - 1), который связан с длиной массива, заимствованQ1пример

Например: когда емкость равна 16, вычислить хэш и 15

Предположим, хеш = 0101 0101

hash & 15

Двоичная длина должна быть 32 бита, сокращенно здесь, например

=> 0101 0101

& 0000 1111

Результат 0101 = 5, индекс массива элемента в позиции контейнера равен 5;

Теперь контейнер расширен до 32

Такие как: когда емкость 32, рассчитано Hash & 31

Предположим, хеш = 0101 0101

hash & 31

Двоичная длина должна быть 32 бита, сокращенно здесь, например

=> 0101 0101 (На самом деле 5-я цифра здесь определяет, будет ли меняться ее нижний индекс: когда он равен 0, нижний индекс такой же, как и раньше; когда он равен 1, нижний индекс меняется на предыдущий нижний индекс + предыдущую разрядность)

& 0001 1111

Результат 1 0101 = 21, индекс массива элемента в позиции контейнера равен 21;

В это время вы можете видеть, что 21 = 5 + 16, 5 — это нижний индекс до расширения, а 16 — емкость до расширения.

Положение элемента не меняется в зависимости отlength-1Позиция самой левой 1 в двоичном формате в этой позицииhashЯвляется ли двоичный файл 1. Когда он равен 0, нижний индекс такой же, как и раньше; когда он равен 1, нижний индекс меняется на предыдущий нижний индекс + предыдущая емкость (это более популярное понимание).
Q6:HashMapизkeyзначениеnullЭлемент , хранящийся в фиксированной позиции массива, индекс равен 0

2.2 JDK 1.8

Метод реализации аналогичен JDK 1.7.

Q1: Зачем вводить красно-черные деревья вместо других структур данных, таких как完全平衡二叉树

гарантироватьputэффективность, но и обеспечиватьgetэффективность.

Красно-черные деревья хороши для поиска, вставки и удаления элементов Это сравнение таких соображений.
Q2: По сравнению с JDK 1.7, в JDK 1.8 внесены некоторые изменения в метод вычисления хэша для упрощения алгоритма, но суть не изменилась.Улучшение хэшируемости HashMap
Q3: Каковы условия преобразования связанного списка в красно-черное дерево? Состояние красно-черного дерева в связном списке

Когда длина связанного списка >= 8, а длина массива >= 64, он будет преобразован в красно-черное дерево;

Если длина связанного списка >= 8, а длина массива

При количестве красно-черных элементов дерева

2.3 Резюме

HashMapВажные свойства: (JDK 1.8)

 // 默认初始容量 16 - 必须是2的幂
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 // 最大容量
 static final int MAXIMUM_CAPACITY = 1 << 30;
 // 默认加载因子
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 // 链表转变为红黑树的阈值，当前节点元素个数 > 8 是链表变为红黑树
 static final int TREEIFY_THRESHOLD = 8;
 // 红黑树转变为链表的阈值，当前节点元素个数 < 6
 static final int UNTREEIFY_THRESHOLD = 6;    
 // 桶中结构转化为红黑树对应的table的最小大小
 static final int MIN_TREEIFY_CAPACITY = 64;
 /** 存储元素的数组，长度总是2的幂次倍
   *包括属性：
       int hash;         // key 的hash值
       K key;            // 要存入的key
       V value;          // 要存入的值
       Node<K,V> next;   // 指向下一个元素
 */
 transient Node<k,v>[] table;
 // 存放具体元素的集
 transient Set<map.entry<k,v>> entrySet;
 // 容器中元素的个数
 transient int size;
 // 加载因子
 final float loadFactor;
 // 临界值， = table.length * loadFactor.大于这个值，会进行扩容
 int threshold;

2.4 `HashMap`передача`put`Метод, выполняемый процесс: (JDK 1.8)

Возьмите пустой конструктор в качестве примера

HashMapпусто, звониresize()инициализировать контейнер,resize()Способ также включает механизм расширения контейнера;
(table.length - 1) & hash [(hash=key.hashCode()) ^ (hash >>> 16)] Вычислить индекс элемента, вставленного в массив, и определить, пуста ли эта позиция:
- Если пусто, вставьте элемент напрямую;
```
 table[i] = newNode(hash,key,value,null);
```
- Если он не пустой, продолжайте судить:
  - ifРавны ли хэш и ключ элемента и элемента текущей позиции (здесь решение включает==,а такжеequals()Суждение), если они равны, заменить исходное значение и вернуть исходное значение;
  - else ifЯвляется ли класс, к которому принадлежит элемент в этой позиции?TreeNode(древовидная структура), если да, то действуйте в соответствии с древовидной структурой;
  - elseЭтот элемент используется как новый элемент для обхода всех элементов текущего списка узлов.
    - Проверяем, есть ли повторяющиеся элементы: если да, выпрыгиваем из обхода, больше добавлять не надо;
    - Вставьте хвост в конец связанного списка и оцените, нужно ли преобразовать связанный список в красно-черное дерево (длина связанного списка >= 8, длина массива >= 64; если длина массива = 8, а длина массива >= 64, он действительно будет преобразован в красно-черное дерево, потому что при дальнейшем расширении использование памяти будет быть уменьшена. больше)

3. Параллельная хеш-карта

потокобезопасныйHashMap, но не передается по наследствуHashMap

структура данных
- JDK 1.7: Нижний слой принимаетСегментированный массив + реализация связанного списка;
- JKD 1.8:а такжеHashMapСтруктура та же, массив + связанный список/красно-черное дерево
потокобезопасность
- JDK 1.7:ConcurrentHashMapиспользоватьблокировка сегментаТехнология, вся корзина Hash сегментированаsegment, то есть большой массив разбивается на несколько маленьких кусковsegment, И каждый меньший фрагментsegmentНа вышеперечисленном стоят замки, поэтому при вставке элемента нужно найти какой фрагмент нужно вставить первымsegment,Получатьsegmentзаблокировать, а затем вставить в этот фрагмент;ConcurrentHashMapУлучшите детализацию блокировки и улучшите производительность параллелизма.;
- JDK 1.8:использоватьsynchronizedа такжеCASДля работы. (JDK1.6 позжеsynchronizedблокировки делают много оптимизаций) все выглядит так, как будто оно оптимизировано и потокобезопасноHashMap, хотя его все еще можно увидеть в JDK1.8Segmentструктура данных, но свойства были упрощены, просто для совместимости со старыми версиями;

Разница между ConcurrentHahsMap и Hahtable

1. Структура данных:

ConcurrentHashMap:JDK 1.7использоватьСегментированный массив + реализация связанного списка;JDK 1.8Принять массив + связанный список/красно-черное дерево;
Hashtable: Массив + связанный список, массив является основным телом, а связанный список в основном существует для решения конфликта хэшей.

2. Способ достижения потокобезопасности (важно):

ConcurrentHashMap:
- JDK1.7когда,ConcurrentHashMap (блокировка сегмента)Весь массив бакетов разбит на сегменты (Segment), каждая блокировка блокирует только часть данных в контейнере, многопоточный доступ к данным разных сегментов данных в контейнере, не будет конкуренции блокировок и улучшится скорость одновременного доступа;ConcurrentHashMapУлучшите детализацию блокировки и улучшите производительность параллелизма.;
- JDK1.8был заброшен, когдаSegmentпонятие, но непосредственное использованиеNodeРеализована структура данных массив + связанный список + красно-черное дерево, используется контроль параллелизмаsynchronizedа такжеCASработать. (После JDK1.6 даsynchronizedблокировки делают много оптимизаций) все выглядит так, как будто оно оптимизировано и потокобезопасноHashMap, хотя его все еще можно увидеть в JDK1.8Segmentструктура данных, но свойства были упрощены только для совместимости со старыми версиями.
Hashtable(тот же замок): использоватьsynchronizedЧтобы обеспечить безопасность потоков, по мере того, как массив становится все больше и больше, эффективность также снижается. Когда один поток обращается к методу синхронизации, а другие потоки также обращаются к методу синхронизации, он может войти в состояние блокировки или опроса, например, добавить элементы с помощью put, другой поток не может использовать put для добавления элементов или использовать get, конкуренция станет больше и больше яростнее Чем ниже эффективность.

1. Карта

1.1 Разница между HashMap и Hashtable

2. Анализ основного исходного кода HashMap

2.1 JDK 1.7

2.2 JDK 1.8

2.3 Резюме

2.4 HashMapпередачаputМетод, выполняемый процесс: (JDK 1.8)

3. Параллельная хеш-карта

Разница между ConcurrentHahsMap и Hahtable

1. Структура данных:

2. Способ достижения потокобезопасности (важно):

2.4 `HashMap`передача`put`Метод, выполняемый процесс: (JDK 1.8)