HashMap является обычным тестовым сайтом и, как правило, не запрашивает несколько классов реализации List (простой). Следующий анализ основан на JDK1.8.0_102.

внутренняя память

Внутреннее хранилище HashMap представляет собой массив (bucket), элемент Node массива реализует интерфейс Map.Entry (хеш, ключ, значение, next), когда next не пуст, он указывает на другой Entry с таким же позиционированием, как показано на рисунке:

Вместимость (capacity) и коэффициент загрузки (loadFactor)

Проще говоря, емкость — это размер корзины, а loadFactor — максимальная доля полной корзины. когда ведроколичество записей(а не количество занятых позиций), когда вместимость больше, чем вместимость*коэффициент загрузки, емкость необходимо увеличить, а размер корзины следует отрегулировать так, чтобы он удвоился по сравнению с текущим размером. При этом размер инициализируемой емкости также является степенью 2 (больше или равен минимальной мощности установленной емкости), тогда размер ведра будет степенью 2 до и после расширения (очень важно, это может принести большое удобство при изменении размера).

Tips:
Емкость по умолчанию — 16, а loadFactor — 0,75, но если вам нужно оптимизировать, вы должны учитывать конкретный сценарий использования.

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

Если требования к производительности для произвольного доступа очень высоки, не устанавливайте loadFactor слишком большим, иначе это вызовет частые коллизии во время доступа, а временная сложность уменьшится до O(n).

Если данные быстро растут или размер данных предсказуем, вы можете активно установить емкость при создании HashMap.

хэш и позиционирование

Как разработчик API, вы не можете предполагать, что пользователь реализует хороший метод hashCode, поэтому обычно для hashCode снова вычисляется хэш:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

метод hashCode

Уведомлениеkey.hashCode()полиморфное употребление. Дело в методе хеширования.

Реализация и позиционирование метода хеширования

Как упоминалось ранее, когда get и put вычисляют индекс, сначала выполните операцию хеширования над hashCode, а затем вычислите индекс через хеш-значение, как показано на следующем рисунке:

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

В javadoc написано следующее:

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed(так что не пользуйтесь распространением), и потому чтоwe use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

При разработке хеш-функции, поскольку текущая длина таблицы n является степенью числа 2, при вычислении индекса можно использовать побитовое И&вместо модуля%:

(n - 1) & hash

Конструкторы посчитали этот метод склонным к коллизиям. Почему ты это сказал? Подумайте об этом, когда n - 1 равно 15 (0x1111), только эффективные биты младших 4 битов действительно эффективны, и, конечно, легко столкнуться.

Поэтому разработчик придумал способ учесть общую ситуацию (принимая во внимание скорость, функциональность и качество), то есть XOR для старших 16 бит и младших 16 бит. Дизайнер также объяснил, что, поскольку большинство дистрибутивов hashCode сейчас довольно хороши, даже если возникает коллизия, это делается с помощью дерева O (logn). Просто XOR не только снизит нагрузку на систему, но и не вызовет коллизий, возникающих, когда старшие биты не участвуют в вычислении индекса (длина таблицы относительно небольшая).

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

столкновение

При вызове метода put могут возникать коллизии, хотя мы стараемся избегать коллизий, чтобы повысить производительность HashMap. Говорят, что частота столкновений довольно высока, и столкновение начнется, когда средняя скорость загрузки достигнет 10%. Мы используем开放散列法для обработки коллизий узлов.

Присвоить ссылку старой записи следующему атрибуту новой записи, а новую запись поместить в эту позицию — то есть сохранить связанный список в этой позиции, а конфликтный узел вставляется из головы связанного списка, так что при вставке новой записи нет необходимости перемещаться по связанному списку. Временная сложность составляет O (1). Но если связанный список слишком длинный, производительность запроса все равно упадет до O(n). В Java 8 к длине связанного списка добавляется пороговое значение.Если связанный список превышает пороговое значение, связанный список будет преобразован в красно-черное дерево, а сложность запроса снижается до O(logn), что повышает производительность, когда связанный список слишком длинный.

Ошибки: друг в Интернете связался со мной и указал на ошибку здесь.В Java8, когда происходит коллизия, она переходит в конец связанного списка.

Когда писалась эта статья, умение читать исходный код было относительно шлаковым.Оно было основано на моем раннем анализе исходного кода Java7.Я думал, что в основном то же самое, за исключением красно-черной части дерева. HashMap в Java7 также неверен, и окончательный метод вставки правильный, но все равно требуется время O(n) для обхода перед вставкой. Однако другие статьи, содержащие исходный код, написаны честно, следуя исходному коду, поэтому вы можете читать его с уверенностью.Увещевай себя оставаться устойчивым и сомневающимся. Ниже приводится скорректированный анализ.

Начиная с записи в этой позиции, переходим до тех пор, пока не будет найден такой же ключ (замена), или в конце еще не будет такого же ключа (подключен к следующему хвостовому узлу). Процесс тот же, что и при запросе. Независимо от какой-либо оптимизации производительность вставки и запроса составляет O(n). В Java8 к длине связанного списка добавляется пороговое значение.Если связанный список превышает пороговое значение, связанный список будет преобразован в красно-черное дерево.Временная сложность вставки и запроса снижена до O(logn) , что повышает производительность, когда связанный список слишком длинный.

При вызове метода get найдите позицию, затем пройдитесь по красно-черному дереву, сравните значение ключа, чтобы найти нужный элемент:

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

Схема оценки равенства элементов более классическая, с использованием характеристик короткого замыкания логических выражений: сначала сравнить хэш-значения; если хэш-значения равны, пройти==сравнить; если==Не равно, а затем сравнить с помощью метода equals. Хеш вычисляется заранее, без перегрузки оператора (что вообще не рекомендуется),==Как правило, эталонные значения сравниваются напрямую; метод equals, скорее всего, потребляет производительность.Например, метод equals для String требует O(n) времени, где n — длина строки. Обязательно запомните порядок суждения здесь, и очень возможно изучить понимание исходного кода обработки коллизий.

При использовании HashMap необходимо учитывать два важных момента при переопределении методов hashCode и equals:

После перезаписи обязательноЕсли гарантируется, что equals равно, возвращаемое значение hashCode также равно.

Для класса, выбранного в качестве ключа,Убедитесь, что возвращаемое значение hashCode при вызове put и get равно, а свойства равных одинаковы..

resize

изменение размера - самая сложная часть HashMap для понимания.

При вызове метода put, если будет обнаружено, что текущая занятость корзины превысила loadFactor, произойдет изменение размера. Проще говоря, бакет расширяется в 2 раза, а потом индекс пересчитывается, и узлы помещаются в новый бакет.

В javadoc написано следующее:

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

То есть, когда предел будет превышен, он будет изменен, и поскольку мы используем степень двойки, положение элемента либо в исходной позиции, либо перемещено в положение степени 2 в исходной позиции. .

Как понять это? Например, когда мы расширяемся с 16 до 32, конкретные изменения заключаются в следующем:

Предполагаемый размер ковшаn=2^k, после того как элемент пересчитает хэш, поскольку n удваивается, новая позиция(2^(k+1)-1)&hash. и2^(k+1)-1=2^k+2^k-1, диапазон маски, эквивалентный 2^k-1, на 1 бит больше (красный) в старшем разряде (еще раз напомним, исходная длина n также является степенью числа 2),Этот 1 бит равен либо 1, либо 0. Как показано на рисунке:

Поэтому, когда мы изменяем размер, нам не нужно изменять положение, нам просто нужно посмотреть, равен ли новый бит исходного хеш-значения 1 или 0. Если он равен 0, позиция не изменилась, а если он равен 1, позиция станет "исходной позицией". +oldCap". Код слишком длинный и не будет опубликован. Ниже приведена схема изменения размера, увеличенного с 16 до 32:

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

Ссылаться на:

Принцип работы и реализация Java HashMap | Yikun

Ссылка на эту статью:Принцип реализации HashMap
автор:обезьяна 007
Источник:monkeysayhi.github.io
Эта статья основана наCreative Commons Attribution-ShareAlike 4.0Выпущено по международному лицензионному соглашению, приветствуется перепечатка, вывод или использование в коммерческих целях, но авторство и ссылка на эту статью должны быть сохранены.