Бонусный элемент интервью — назначение этих констант в исходном коде HashMap.

предисловие

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

Почему размер инициализации по умолчанию для HashMap 1

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

Почему размер инициализации HashMap по умолчанию равен 16? Вот двухмерный анализ, почему это степень 2, и почему это 16 вместо 8 или 32.

Почему размер инициализации по умолчанию определяется как степень двойки?

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; 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);

Мы знаем, что базовая структура данных HashMap представляет собой массив + связанный список/массив + красно-черное дерево, Из приведенного выше метода можно обнаружить, что формула позиционирования индекса нижнего индекса массива:i = (n - 1) & hash, когда размер инициализации n кратен 2,(n - 1) & hashЭквивалентноn%hash. Индексы позиционирования обычно используют метод остатка, почему бы не взять остаток здесь?

• Поскольку операция И (&) более эффективна, чем операция остатка (%)
• Оставшаяся операция: a % b эквивалентна операции a-(a / b)*b.
• И операция: делается в одной инструкции

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

Почему размер инициализации по умолчанию равен 16 вместо 8 или 32?

Если слишком мало, 4 или 8,Расширение происходит чаще; если он слишком велик, 32 или 64 даже слишком велики, аЗанять место в памяти.

провести аналогию, Предположим, вы открываете кафе для пар, обычно 7 или 8 пар приходят попить кофе, а пик всего 10 пар. Итак, вы хотите установить 8 столов, и если людей больше, рассмотрите возможность добавления дополнительных столов. Если вы ставите 4 стола, то мест для добавления стола часто не хватает, если же вы ставите 10 столов и больше, то он точно будет занимать место.

Почему коэффициент загрузки по умолчанию равен 0,75?

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

коэффициент загрузкиУказывает на заполнение хеш-таблицы, тесно связанное с расширением. Почему не 0,5 или 1?

Если он равен 0,5, это означает, что хэш-таблица начнет расширяться при заполнении наполовину, что приведет кЧастое расширение, а коэффициент использования пространства относительно низок. Если он равен 1, это означает, что хеш-таблица полностью заполнена до того, как она начнет расширяться, поэтому, хотя использование пространства улучшается, нохэш-коллизияВозможность велика. Вы можете посмотреть объяснение документации исходного кода:

 * <p>As a general rule, the default load factor (.75) offers a good
 * tradeoff between time and space costs.  Higher values decrease the
 * space overhead but increase the lookup cost (reflected in most of
 * the operations of the <tt>HashMap</tt> class, including
 * <tt>get</tt> and <tt>put</tt>).  The expected number of entries in
 * the map and its load factor should be taken into account when
 * setting its initial capacity, so as to minimize the number of
 * rehash operations.  If the initial capacity is greater than the
 * maximum number of entries divided by the load factor, no rehash
 * operations will ever occur.

Перевод примерно означает:

Как правило, коэффициент загрузки по умолчанию (0,75) обеспечивает хороший компромисс между затратами времени и места. Чем больше значение коэффициента загрузки, тем меньше накладные расходы на пространство, но увеличивается стоимость поиска (отражено в большинстве операций класса HashMap, включая получение и размещение). При задании начального размера следует учитывать ожидаемое количество записей в карте и коэффициент ее загрузки, а также минимизировать количество операций перехеширования. Если начальная емкость больше, чем максимальное количество записей, деленное на коэффициент загрузки, операция повторного хеширования не будет выполняться.

Короче,Коэффициент нагрузки 0,75Сразувозможность для конфликтаиИспользование пространстваПоследним проявлением компромисса также является ценность эксперимента программиста.

В StackOverFlow есть ответ на этот вопрос:What is the significance of load factor in HashMap?

Этот ответ объясняет: Вероятность того, что ведро будет пустым и непустым, составляет 0,5.С помощью математических вычислений, таких как бином Ньютона, значение этого коэффициента загрузки равно log(2), что приблизительно равно0.693.

Наконец, выберите 0,75. Возможно, 0,75 — это одно из округленных чисел, близкое к 0,693, что легче понять, а размер емкости по умолчанию — 16 * 0,75 = 12, что является целым числом.

Почему порог преобразования связанного списка красно-черное дерево 8

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

В JDK8 и более поздних версиях базовая структура данных HashMap представляет красно-черное дерево. При добавлении элементов, если в ведре более 8 элементов связанного списка, он будет автоматически преобразован в красно-черное дерево. Так почему порог 8? См. этот комментарий в исходном коде HashMap:

* Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million

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

Из таблицы сравнения видно, что вероятность, когда количество элементов в связанном списке равно 8, очень и очень мала, поэтому пороговое значение преобразования красно-черного дерева связанного списка равно 8.

Почему порог восстановления связанного списка дерева равен 6?

/**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

Из анализа в предыдущем разделе мы можем узнать, что пороговое значение дерева для связанного списка равно 8, так почему же дерево восстанавливается в связанный список 6 вместо 7? это дляПредотвращение частых переходов между связанными списками и деревьями. Если оно равно 7, при условии, что HashMap продолжает вставлять и удалять элементы, а количество связанных списков всегда около 8, он будет часто переключаться с дерева на связанный список и со связанного списка на дерево, что очень неэффективно.

Почему максимальная вместимость 1

/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

Почему HashMap удовлетворяет n-й степени числа 2?

по первому разделу (Почему размер инициализации по умолчанию для HashMap 1 ) анализ показывает, что емкость HashMap должна соответствовать степени двойки, а операция остатка более эффективна, чем операция суммирования. Операция И равна операции остатка только тогда, когда емкость равна 2 в n-й степени.

tab[i = (n - 1) & hash]

Почему не 2 в 31-й степени?

Мы знаем, что int учитываетчетыре байта,Байт занимает 8 бит, так что это 32-битное целое число, то есть не более 32 бит. Само собой разумеется, что максимальное число можно сдвинуть влево на 31 бит, что является 31-й степенью числа 2. Почему оно здесь?Разве 2 не в 31-й степени??

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

        System.out.println(1<<30);
        System.out.println(1<<31);
        System.out.println(1<<32);
        System.out.println(1<<33);
        System.out.println(1<<34);

вывод:

1073741824
-2147483648
1
2
4

Следовательно, максимальная емкость HashMap составляет 1

Почему минимальный размер дерева хеш-таблицы равен 64?

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

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

Ссылка и спасибо

• Почему loadFactor HashMap равен 0,75?
• Почему коэффициент загрузки в java Hashmap по умолчанию равен 0,75
• Почему длина связанного списка в HashMap больше 8 преобразуется в красно-черное дерево
• What is the significance of load factor in HashMap?
• Почему максимальная емкость HashMap 2 в 30-й степени
• Java8 HashMap, который должен знать каждый Java-программист

Личный публичный аккаунт

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