Те понятия, которые тупо неясны в HashMap

Java

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

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

Давайте сначала посмотрим, какие переменные-члены определены в HashMap.

[paramInMap][1]

Выше приведена диаграмма основных переменных-членов в HashMap, одной из которых посвящена эта статья:size,loadFactor,threshold,DEFAULT_LOAD_FACTORиDEFAULT_INITIAL_CAPACITY.

Мы сначала кратко объясним значение этих параметров, а затем проанализируем их роль.

В классе HashMap есть следующие основные переменные-члены:

  • transient int size;
    • Записывает количество пар KV на карте
  • loadFactor
    • Загрузка Индии, используемая для измерения степени заполнения HashMap. Значение loadFactor по умолчанию равно 0,75f (static final float DEFAULT_LOAD_FACTOR = 0.75f;).
  • int threshold;
    • Критическое значение, когда фактическое количество KV превышает порог, HashMap расширит емкость, порог = емкость * коэффициент загрузки.
  • В дополнение к вышеупомянутым важным переменным-членам, в HashMap есть еще одна концепция, тесно связанная с ними: емкость.
    • емкость, если она не указана, емкость по умолчанию равна 16 (static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;)

Возможно, после прочтения вы все еще немного запутались.Какова связь между размером и емкостью? Зачем определять эти две переменные. Что делают loadFactor и порог?

размер и вместимость

Разницу между размером и емкостью в HashMap объяснить довольно просто. Мы знаем, что HashMap похож на «ведро», поэтому вместимость — это максимальное количество элементов, которое «ведро» может вместить в данный момент, а размер указывает, сколько элементов уже заполнено ведро. Взгляните на следующий код:

    Map<String, String> map = new HashMap<String, String>();
    map.put("hollis", "hollischuang");

    Class<?> mapType = map.getClass();
    Method capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map));

    Field size = mapType.getDeclaredField("size");
    size.setAccessible(true);
    System.out.println("size : " + size.get(map));

Мы определяем новый HashMap, помещаем в него элемент, а затем печатаем емкость и размер посредством отражения. Результат:вместимость: 16, размер: 1

По умолчанию емкость (емкость) HashMap равна 16, а преимущества проектирования 16 описаны в "Во всей сети нет другой статьи, в которой бы анализировался hash() в Map.Также кратко представлено, что в основном можно использовать побитовый и альтернативный модуль для повышения эффективности хеширования.

Почему я только что сказал, что емкость — это максимальное количество элементов, которое ведро может вместить «в настоящее время»? Как вы это понимаете сейчас. На самом деле HashMap имеет механизм расширения. Когда HashMap инициализируется в первый раз, его емкость по умолчанию составляет 16. Когда достигается условие расширения, его необходимо расширить, и он будет расширен с 16 до 32.

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

    Map<String, String> map = new HashMap<String, String>(1);

    Class<?> mapType = map.getClass();
    Method capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map));

    Map<String, String> map = new HashMap<String, String>(7);

    Class<?> mapType = map.getClass();
    Method capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map));


    Map<String, String> map = new HashMap<String, String>(9);

    Class<?> mapType = map.getClass();
    Method capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map));

Выполните указанные выше три фрагмента кода соответственно и выведите:вместимость: 2, вместимость: 8, вместимость: 16.

То есть емкость HashMap по умолчанию равна 16, но если пользователь укажет число в качестве емкости через конструктор, Hash выберет в качестве емкости первую степень 2, большую, чем число. (1->1, 7->8, 9->16)

Вот небольшое предложение: при инициализации HashMap вы должны попытаться указать его размер. Особенно, когда вы знаете количество элементов, хранящихся на карте. («Протокол разработки Java Alibaba»)

loadFactor и порог

Как мы упоминали ранее, HashMap имеет механизм расширения, то есть при достижении условий расширения он будет расширяться с 16 до 32, 64, 128...

Итак, к чему относится это условие расширения?

На самом деле условие расширения HashMap заключается в том, что когда количество элементов (размер) в HashMap превышает пороговое значение (threshold), оно автоматически расширяется.

В HashMap порог = коэффициент нагрузки * емкость.

loadFactor — это коэффициент загрузки, который указывает на заполненность HashMap. Значение по умолчанию — 0,75f. Установка его на 0,75 имеет преимущество, то есть 0,75 — это ровно 3/4, а емкость — это степень двойки. Следовательно, произведение двух чисел является целым числом.

Для HashMap по умолчанию расширение по умолчанию будет запускаться, когда его размер превышает 12 (16 * 0,75).

Код подтверждения выглядит следующим образом:

    Map<String, String> map = new HashMap<>();
    map.put("hollis1", "hollischuang");
    map.put("hollis2", "hollischuang");
    map.put("hollis3", "hollischuang");
    map.put("hollis4", "hollischuang");
    map.put("hollis5", "hollischuang");
    map.put("hollis6", "hollischuang");
    map.put("hollis7", "hollischuang");
    map.put("hollis8", "hollischuang");
    map.put("hollis9", "hollischuang");
    map.put("hollis10", "hollischuang");
    map.put("hollis11", "hollischuang");
    map.put("hollis12", "hollischuang");
    Class<?> mapType = map.getClass();

    Method capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map));

    Field size = mapType.getDeclaredField("size");
    size.setAccessible(true);
    System.out.println("size : " + size.get(map));

    Field threshold = mapType.getDeclaredField("threshold");
    threshold.setAccessible(true);
    System.out.println("threshold : " + threshold.get(map));

    Field loadFactor = mapType.getDeclaredField("loadFactor");
    loadFactor.setAccessible(true);
    System.out.println("loadFactor : " + loadFactor.get(map));

    map.put("hollis13", "hollischuang");
    Method capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("capacity : " + capacity.invoke(map));

    Field size = mapType.getDeclaredField("size");
    size.setAccessible(true);
    System.out.println("size : " + size.get(map));

    Field threshold = mapType.getDeclaredField("threshold");
    threshold.setAccessible(true);
    System.out.println("threshold : " + threshold.get(map));

    Field loadFactor = mapType.getDeclaredField("loadFactor");
    loadFactor.setAccessible(true);
    System.out.println("loadFactor : " + loadFactor.get(map));

Выходной результат:

capacity : 16
size : 12
threshold : 12
loadFactor : 0.75

capacity : 32
size : 13
threshold : 24
loadFactor : 0.75

Когда количество элементов в HashMap достигает 13, емкость увеличивается с 16 до 32.

HashMap также предоставляет метод, поддерживающий передачу initialCapacity и loadFactor для инициализации емкости и коэффициента загрузки. Однако обычно не рекомендуется изменять значение loadFactor.

Суммировать

Размер в HashMap указывает, сколько пар KV существует в настоящее время, а емкость указывает емкость текущей HashMap.Значение по умолчанию — 16, и каждое расширение удваивается. loadFactor — коэффициент загрузки, когда количество элементов на Карте превышаетloadFactor* capacityзначение, расширение будет запущено.loadFactor* capacityЕго можно представить порогом.

PS: анализ в тексте основан на JDK1.8.0_73

Категории