————————————
Как мы все знаем, HashMap — это коллекция, используемая для хранения пар ключ-значение, каждая пара ключ-значение также называетсяEntry. Эти пары ключ-значение (Entry) разбросаны и хранятся в массиве, который является основой HashMap.
Начальное значение каждого элемента массива HashMap равно Null.
Для HashMap мы чаще всего используем два метода:Get иPut.
1. Принцип метода Put
Что происходит, когда вызывается метод Put?
Например, вызов hashMap.put("apple", 0) вставляет элемент с ключом "apple". На данный момент нам нужно использовать хеш-функцию для определения позиции вставки (индекса) записи:
индекс = Хэш ("яблоко")
Предполагая, что последний рассчитанный индекс равен 2, результат будет следующим:
Однако, поскольку длина HashMap ограничена, когда вставляется все больше и больше записей, даже идеальная хэш-функция неизбежно будет иметь конфликты индексов. Например следующее:
Что нам делать в это время? мы можем использоватьсвязанный списокрешать.
Каждый элемент массива HashMap является не только объектом Entry, но и головным узлом связанного списка. Каждый объект Entry указывает на свой следующий узел Entry через указатель Next. Когда новая запись сопоставляется с конфликтующей позицией массива, ее нужно только вставить в соответствующий связанный список:
Следует отметить, что когда новый узел Entry вставляется в связанный список, используется «метод вставки заголовка». А почему он не вставляется в конец связанного списка, будет пояснение позже.
2. Принцип метода Get
Что происходит, когда вы используете метод Get для поиска значения на основе ключа?
Сначала выполните сопоставление хэша входного ключа, чтобы получить соответствующий индекс:
индекс = Хэш ("яблоко")
Из-за только что упомянутого конфликта хэшей одно и то же местоположение может соответствовать нескольким записям.В настоящее время необходимо выполнять поиск по одному по головному узлу соответствующего связанного списка. Предположим, что ключ, который мы ищем, — это «яблоко»:
На первом этапе мы смотрим на головной узел Entry 6. Ключ Entry 6 — это банан, что, очевидно, не является тем результатом, который мы ищем.
На втором этапе мы смотрим на следующий узел Entry1.Ключом Entry1 является яблоко, что является результатом, который мы ищем.
Причина, по которой Entry6 помещается в головной узел, заключается в том, что изобретатель HashMap считает, чтоПост-вставленная запись с большей вероятностью будет найдена.
————————————
Как упоминалось ранее, хеш-функция используется для сопоставления ключа с соответствующей позицией массива HashMap:
индекс = Хэш ("яблоко")
Как реализовать хеш-функцию, которая будет максимально равномерно распределена? Мы выполняем какую-то операцию, используя значение HashCode ключа.
индекс = хэш-код (Key) % Длина ?
Как выполнять битовые операции? Существует следующая формула (длина — это длина HashMap):
индекс = хэш-код (Key) & (Length - 1)
Ниже мы демонстрируем весь процесс со значением ключа «book»:
1. Вычислить хэш-код книги, результат 3029737 в десятичном виде и 101110001110101110 1001 в двоичном.
2. Предполагая, что длина HashMap по умолчанию равна 16, результат вычисления Length-1 равен 15 в десятичном формате и 1111 в двоичном.
3. Сделайте два вышеуказанных результатаИ операция, 101110001110101110 1001 и 1111 = 1001, десятичное число равно 9, поэтому индекс = 9.
Можно сказать, что окончательный результат индекса, полученный алгоритмом хеширования, полностью зависит от последних нескольких цифр значения хэш-кода ключа.
Предполагая, что длина HashMap равна 10, повторите шаги операции прямо сейчас:
Глядя только на этот результат, на поверхности нет никаких проблем. Давайте попробуем новый HashCode 1011100011101011101011 :
Давайте изменим другой HashCode 1011100011101011101111 пытаться:
Да, хотя предпоследняя и третья цифры HashCode изменились с 0 на 1, результат операции — все 1001. То есть, когда длина HashMap равна 10, некоторые результаты индекса появятся с большей вероятностью, а некоторые результаты индекса никогда не появятся (например, 0111)!
Таким образом, это явно не соответствует принципу равномерного распределения алгоритма Hash.
В отличие от длины 16 или других степеней двойки, значение Length-1 состоит в том, что все двоичные биты равны 1. В этом случае результат index эквивалентен значению последних нескольких битов HashCode. Пока сам входной хэш-код распределен равномерно, результат алгоритма хеширования является однородным.
Друзья, которым понравилась эта статья, можете долго нажимать на картинку, чтобы следить за номером подписки.программист маленький серый, смотрите больше захватывающего контента