Анализ исходного кода HashMap (2): после прочтения полного понимания HashMap

Java

Способ добавления HashMap указан выше, теперь продолжимссылка выше

В предыдущей статье об анализе исходного кода HashMap, если количество элементов превышает пороговое значение при использовании put, будет вызвано изменение размера для увеличения емкости.

1. Механизм расширения

Чтобы понять механизм расширения HashMap, у вас должны быть эти два вопроса.

  • 1. Когда вам нужно расширяться
  • 2. Что такое расширение HashMap?

При добавлении элементов, если пороговая точка, установленная порогом, будет превышена, емкость будет расширена.Короче, емкость чайника составляет два литра, а затем он в это время полный, но вы должны продолжать добавлять воду , Что я должен делать? Получите больший. Таким образом, расширение HashMap такое же, как у вашего чайника.Если вода будет полной, я поменяю чайник на больший и продолжу добавлять воду. Однако есть много условий, когда вы меняете чайник.

Я когда посмотрел исходники этого ресайза тоже растерялся.Напоследок спросил у начальника и ответ был,что хлопотно добавить красно-черное дерево в 1.8.Можно глянуть на 1.7,а потом Я пошел в Интернет, чтобы прочитать, что написали другие.Статьи в основном основаны на ресайзе 1.7. Итак, здесь мы смотрим на изменение размера 1.7 для анализа.

Посмотрите на реализацию изменения размера в JDK1.7.

Операция копирования заключается в вызове метода передачи

Изменение размера в 1,7 в сочетании с нашим небольшим примером можно понять так: идите в супермаркет, чтобы купить чайник побольше, а затем перелейте воду из предыдущего чайника в новый чайник. Тогда замени емкость нашего нынешнего чайника и скажи другим, что у меня емкость больше. (Вынужденная метафора хахахахаха)

Изменение размера в версии 1.7 очень простое, поэтому давайте взглянем на функцию resize() в версии 1.8, чтобы не запутаться при повторном рассмотрении.

Здесь я разделил метод изменения размера 1.8 на две части.

  • 1. Рассчитайте new newCap (новая мощность) и newThr (новая пороговая точка).
  • 2. Скопируйте новый массив

первая часть

Вторая часть

Сравните 1.7

  • 1.7 элементы не нужно менять местами. 1.8 Положение элемента либо в исходной позиции, либо он перемещен в степени 2 в исходной позиции
  • Нет необходимости пересчитывать хеш, как 1.7

2. Удалить

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

Метод удаления:

Вызовите removeNode:

3. Найдите элементы

Метод поиска, найдите значение по ключу элемента.

Вызвать метод getNode()

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

4. Траверс

Давайте продемонстрируем, как HashMap проходит через следующие примеры.

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

 		for (String key:map.keySet()){
            System.out.println(key);
        }
        for (Object value : map.values()) {
            System.out.println(value);
        }

2. Итерация

 		Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Object> mapEntry = iterator.next();
            System.out.println(mapEntry.getKey() + "====" + mapEntry.getValue());
        }

3. Получите коллекцию ключей

 	Set<String> keySet = map.keySet();
        for (String str : keySet) {
            System.out.println(str + "====" + map.get(str));
        }

4. Получите коллекцию Entry и просмотрите коллекцию Entry.

	Set<Map.Entry<String, Object>> entrySet = map.entrySet();
        for (Map.Entry<String, Object> entry : entrySet) {
            System.out.println(entry.getKey() + "====" + entry.getValue());
        }

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

Суммировать

HashMap на основе JDK1.8 состоит из массива+связного списка+красно-черного дерева.Когда длина связанного списка превышает 8, он будет автоматически преобразован в красно-черное дерево, а когда количество узлов в красном -черное дерево меньше 6, оно будет преобразовано в связанный список. По сравнению с более ранней версией реализации JDK HashMap в качестве базовой структуры данных добавлено красно-черное дерево, что может значительно повысить эффективность извлечения при большом объеме данных и большом количестве коллизий хэшей. HashMap не является потокобезопасным, он поддерживает значения K и V равными нулю, повторение k будет перезаписано, повторение V может быть повторено,Другой момент заключается в том, что данные, пройденные HashMap, не упорядочены и не упорядочены.

Категории