что такое node в hashmap
Внутренняя работа HashMap в Java
В этой статье мы увидим, как изнутри работают методы get и put в коллекции HashMap. Какие операции выполняются. Как происходит хеширование. Как значение извлекается по ключу. Как хранятся пары ключ-значение.
Как и в предыдущей статье, HashMap содержит массив Node и Node может представлять класс, содержащий следующие объекты:
Теперь мы увидим, как все это работает. Для начала мы рассмотрим процесс хеширования.
Хэширование
Здесь я использую свой собственный класс Key и таким образом могу переопределить метод hashCode() для демонстрации различных сценариев. Мой класс Key:
Здесь переопределенный метод hashCode() возвращает ASCII код первого символа строки. Таким образом, если первые символы строки одинаковые, то и хэш коды будут одинаковыми. Не стоит использовать подобную логику в своих программах.
Этот код создан исключительно для демонстрации. Поскольку HashCode допускает ключ типа null, хэш код null всегда будет равен 0.
Метод hashCode()
Метод equals()
Метод equals используется для проверки двух объектов на равенство. Метод реализованн в классе Object. Вы можете переопределить его в своем собственном классе. В классе HashMap метод equals() используется для проверки равенства ключей. В случае, если ключи равны, метод equals() возвращает true, иначе false.
Корзины (Buckets)
Вычисление индекса в HashMap
Хэш код ключа может быть достаточно большим для создания массива. Сгенерированный хэш код может быть в диапазоне целочисленного типа и если мы создадим массив такого размера, то легко получим исключение outOfMemoryException. Потому мы генерируем индекс для минимизации размера массива. По сути для вычисления индекса выполняется следующая операция:
где n равна числу bucket или значению длины массива. В нашем примере я рассматриваю n, как значение по умолчанию равное 16.
HashMap: 
Вычислить значение ключа <"vishal">. Оно будет сгенерированно, как 118.
Создать объект node.
Поместить объект в позицию с индексом 6, если место свободно.
Теперь HashMap выглядит примерно так:
Вычислить значение ключа <"sachin">. Оно будет сгенерированно, как 115.
Создать объект node.
Поместить объект в позицию с индексом 3, если место свободно.
Теперь HashMap выглядит примерно так:
Вычислить значение ключа <"vaibhav">. Оно будет сгенерированно, как 118.
Создать объект node.
Поместить объект в позицию с индексом 6, если место свободно.
В данном случае в позиции с индексом 6 уже существует другой объект, этот случай называется коллизией.
В таком случае проверям с помощью методов hashCode() и equals(), что оба ключа одинаковы.
Если ключи одинаковы, заменить текущее значение новым.
Иначе связать новый и старый объекты с помощью структуры данных «связанный список», указав ссылку на следующий объект в текущем и сохранить оба под индексом 6.
Теперь HashMap выглядит примерно так:
[примечание от автора перевода] Изображение взято из оригинальной статьи и изначально содержит ошибку. Ссылка на следующий объект в объекте vishal с индексом 6 не равна null, в ней содержится указатель на объект vaibhav.
Вычислить хэш код объекта <“sachin”>. Он был сгенерирован, как 115.
В нашем случае элемент найден и возвращаемое значение равно 30.
Вычислить хэш код объекта <"vaibhav">. Он был сгенерирован, как 118.
В данном случае он не найден и следующий объект node не равен null.
Если следующий объект node равен null, возвращаем null.
Если следующий объект node не равен null, переходим к нему и повторяем первые три шага до тех пор, пока элемент не будет найден или следующий объект node не будет равен null.
Изменения в Java 8
Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).
Структуры данных в картинках. HashMap
Приветствую вас, хабрачитатели!
Продолжаю попытки визуализировать структуры данных в Java. В предыдущих сериях мы уже ознакомились с ArrayList и LinkedList, сегодня же рассмотрим HashMap.
HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек.
Создание объекта
Вы можете указать свои емкость и коэффициент загрузки, используя конструкторы HashMap(capacity) и HashMap(capacity, loadFactor). Максимальная емкость, которую вы сможете установить, равна половине максимального значения int (1073741824).
Добавление элементов
Комментарий из исходников объясняет, каких результатов стоит ожидать — метод hash(key) гарантирует что полученные хэш-коды, будут иметь только ограниченное количество коллизий (примерно 8, при дефолтном значении коэффициента загрузки).
В моем случае, для ключа со значением »0» метод hashCode() вернул значение 48, в итоге:
При значении хэша 51 и размере таблице 16, мы получаем индекс в массиве:
Для того чтобы продемонстрировать, как заполняется HashMap, добавим еще несколько элементов.
Footprint
Object size: 376 bytes
Footprint
Object size: 496 bytes
Resize и Transfer
Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов. Как вы сами можете убедиться, ничего сложного в методах resize(capacity) и transfer(newTable) нет.
Метод transfer() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.
Если в исходный hashmap добавить, скажем, еще 15 элементов, то в результате размер будет увеличен и распределение элементов изменится.
Удаление элементов
У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается. И если в ArrayList предусмотрен метод trimToSize(), то в HashMap таких методов нет (хотя, как сказал один мой коллега — «А может оно и не надо?«).
Небольшой тест, для демонстрации того что написано выше. Исходный объект занимает 496 байт. Добавим, например, 150 элементов.
Теперь удалим те же 150 элементов, и снова замерим.
Как видно, размер даже близко не вернулся к исходному. Если есть желание/потребность исправить ситуацию, можно, например, воспользоваться конструктором HashMap(Map).
Итераторы
HashMap имеет встроенные итераторы, такие, что вы можете получить список всех ключей keySet(), всех значений values() или же все пары ключ/значение entrySet(). Ниже представлены некоторые варианты для перебора элементов:
Стоит помнить, что если в ходе работы итератора HashMap был изменен (без использования собственным методов итератора), то результат перебора элементов будет непредсказуемым.
Итоги
— Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки;
— Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии. Среднее же время работы будет Θ(1 + α), где α — коэффициент загрузки. В самом худшем случае, время выполнения может составить Θ(n) (все элементы в одной цепочке);
— Ключи и значения могут быть любых типов, в том числе и null. Для хранения примитивных типов используются соответствующие классы-оберки;
— Не синхронизирован.
Ссылки
Инструменты для замеров — memory-measurer и Guava (Google Core Libraries).
Подробный разбор класса HashMap
Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:
где n – длина массива.
Создается объект Node.
Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового элемента поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.
Теперь к очень подробному примеру.
Создадим объект класса HashMap:
С помощью метода put() добавим в хеш-отображение первую пару «ключ-значение»:
С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-код ключа, внутри которого предварительно вычисляется хеш-код с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное значение» – 2306967. Может проверить в IDEA с помощью
Проверяем таблицу на «пустоту»:
где [] tab — сама хеш-таблица: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.
Одновременно вычисляем индекс бакета, куда будет помещен наш объект, и проверяем, а есть ли уже в нем элементы. Вычисляем:
Так как в результате проверки мы получим true (в бакете элементов нет), будет сгенерирован объект Node со следующими полями:
Наш сформированный объект Node будет добавлен в бакет под индексом [4]:
newNode() — это метод, который просто возвращает объект класса Node.
После добавления будет произведена проверка не превышает ли текущее количество элементов параметр threshold :
Если превышает, тогда будет вызван метод resize() для увеличения размера хеш-таблицы.
На этом метод putVal() (соответственно и put() ) завершит свою работу.
Графически полученный результат изобразить можно так:
Так в общем случае выглядит добавление Node (пара «ключ-значение») в хеш-таблицу, если нужный бакет оказывается пуст. Теперь попробуем добавить такой элемент, который приведет к коллизии (когда в одном бакете оказывается более одного элемента).
С помощью метода put() добавим в хеш-отображение еще одну пару «ключ-значение»:
Вычисляем «предварительный хеш» – 63281361. Модифицируем его и в результате получаем окончательный хеш-код – 63281940.
Так как первая проверка на «пустоту» теперь вернет false (создавать таблицу не надо), сразу вычисляем индекс бакета, куда будет помещен наш объект:
В первую очередь мы сравниваем добавляемый элемент с первым элементом связного списка внутри бакета:
В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).
Игнорируем условие ( p instanceof TreeNode ), так как структура в бакете не является древовидной на данном этапе.
Вы можете спросить, а где же проверка на равенство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого элемента, и так как он сейчас равен null, можно сделать вывод о том, что в списке только один элемент. И так как мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.
Если же при первой итерации указатель не равен null, это говорит о том, что в списке как минимум два элемента, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого элемента со всеми ключами элементов в списке (способом, описанным в пятом пункте).
Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать значение у ключа.
После добавления второго элемента наш объект HashMap графически выглядит так:
В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:
После каждой итерации (добавления нового элемента) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:
До тех пор, пока их количество не станет равно или больше 7:
В таком случае произойдет вызов метода treeifyBin()treeify() для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:
Вместо перехода к древовидной структуре будет вызван метод resize() для увеличения размера хеш-таблицы с перераспределением элементов. treeify() в свою очередь связный список из TreeNode конвертирует в красно-черное дерево. Метод resize() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.
Если кратко, не вдаваясь в подробности структуры красно-черного дерева, то происходит следующее:
Первый элемент списка записывается как корень всего дерева (чёрный цвет):
Для остальных элементов:
распределяем их налево или направо в зависимости от значения хешей:
Все левые потомки должны быть меньше своего корневого узла (или равны ему), в то время как все правые потомки должны быть больше.
Проверяем элементы дерева (объекты TreeNode ) до тех пор, пока не будет найден дочерний (левый или правый) нулевой элемент.
Добавляем дочерний узел (левый или правый в зависимости от dir):
Так как при добавлении нового элемента может нарушиться баланс дерева, вызываем метод для перебалансировки:
Про балансировку КЧД можно почитать здесь: хабр
После балансировки корневой элемент может измениться. Исправляем это вызовом метода, который гарантирует, что переданный ему корень будет первым узлом:
Как строится и самобалансируется красно-черное дерево можно наглядно посмотреть здесь: визуализация
На этом в принципе всё и на примере предположим, что мы хотим добавить в качестве ключей следующие имена: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. И допустим, что в хеш-таблице у нас как минимум 64 бакета, и все эти элементы скопились в одном бакете. Структурно этот бакет будет выглядеть так (элементы сортируются по хеш-коду): Вид КЧД:
если предыдущее выражение возвращает true, необходимо убедиться в том, что длина внутреннего массива больше 0: (n = tab.length) > 0;
если предыдущее выражение также возвращает true, переходим в бакет под индексом (в нашем случае 4), который был предварительно вычислен, и проверяем его на наличие в нем элементов:
Так как в нашем случае, ключ “KING” будет предшествовать ключу “BLAKE” (внутри связного списка новые элементы добавляются в конец, а KING был добавлен первым), мы остановимся на данном этапе и вернем объект first типа Node методу get(), который «выцепит» у него поле со значением (100):
Если внутри бакета находится больше одного элемента, тогда:
заходим в нужный бакет (опять же он предварительно вычисляется);
если в бакете только один объект (проверяем у него указатель null) сравниваем хеши, ссылки и equals (если вдруг хеши не равны). Нашлось совпадение? Отлично, это наш ключ – удаляем его (=null) и возвращаем значение этого ключа.
если в бакете больше одного элемента, проверяем каждый элемент в цикле до тех пор, пока не найдем элемент или достигнем конца списка.
если элемент не был найден — возвращаем null.
В ситуации с деревом довольно мудреная реализация, о которой лучше не знать и спать спокойно (в описании к методу даже написано, что реализация сложнее, чем в обычной операции удаления в красно-черном дереве). Тем более, при удалении количество узлов в одном бакете может вернуться к значению 6, и тогда дерево обратно перестроится в связный список. Если Вы не разработчик с многолетнем стажем, знать об этом и понимать это совсем не обязательно (да и просто не нужно).
Русские Блоги
java HashMap
Резюме
HashMap является наиболее часто используемым типом данных для обработки отображения (пара ключ-значение) программистами Java. С обновлением версии JDK (Java Developmet Kit) JDK1.8 оптимизирует базовую реализацию HashMap, такую как введение структуры данных красно-черного дерева и оптимизация расширения. Эта статья объединяет различия между JDK1.7 и JDK1.8, чтобы подробно обсудить структурную реализацию и функциональные принципы HashMap.
Введение
Java определяет интерфейс java.util.Map для отображения в структуре данных. Этот интерфейс имеет четыре обычно используемых класса реализации, а именно HashMap, Hashtable, LinkedHashMap и TreeMap. Отношение наследования классов показано на следующем рисунке:
Ниже приведено описание характеристик каждого класса реализации:
(1) HashMap: хранит данные на основе значения ключа hashCode, в большинстве случаев может напрямую определять свое значение, поэтому имеет быструю скорость доступа, но порядок обхода не определен. HashMap позволяет только ключу одной записи быть нулевым, а значение нескольких записей равно нулю. HashMap не является поточно-ориентированным, то есть может быть несколько потоков, пишущих одновременно HashMap, что может привести к несогласованности данных. Если вам нужно обеспечить безопасность потоков, вы можете использовать метод коллекций SynchronizedMap для обеспечения безопасности потоков HashMap или использовать ConcurrentHashMap.
(2) Hashtable: Hashtable является унаследованным классом. Общие функции многих карт аналогичны HashMap. Разница в том, что он наследует от класса Dictionary и является потокобезопасным. Только один поток может писать Hashtable в любое время, и параллелизм не так хорош, как ConcurrentHashMap, потому что ConcurrentHashMap вводит сегментные блокировки. Hashtable не рекомендуется использовать в новом коде. HashMap можно использовать, когда безопасность потоков не требуется. ConcurrentHashMap можно использовать, когда требуется безопасность потоков.
(3) LinkedHashMap: LinkedHashMap является подклассом HashMap, который сохраняет порядок вставки записей. При использовании Iterator для обхода LinkedHashMap сначала должны быть вставлены первые полученные записи. Вы также можете взять параметры во время построения и отсортировать их в соответствии с порядком доступа.
(4) TreeMap: TreeMap реализует интерфейс SortedMap, который может сортировать записи, которые он сохраняет по ключу. По умолчанию сортировка значений ключей производится в порядке возрастания, а также можно указать компаратор сортировки. Когда итератор используется для обхода TreeMap, полученные записи сортируются. из. Если вы используете отсортированное сопоставление, рекомендуется использовать TreeMap. При использовании TreeMap ключ должен реализовывать интерфейс Comparable или передавать собственный компаратор при создании TreeMap, в противном случае он вызовет исключение типа java.lang.ClassCastException во время выполнения.
Для вышеуказанных четырех классов типов карты ключ на карте должен быть неизменным объектом. Неизменный объект состоит в том, что его хеш-значение не будет изменено после создания объекта. Если значение хеш-функции объекта изменится, объект Map может не найти местоположение карты.
Из приведенного выше сравнения мы узнаем, что HashMap является обычным членом семейства Java Map. Учитывая, что он может удовлетворять условиям использования большинства сценариев, он является наиболее частым в использовании. Далее мы в основном объединяем исходный код, чтобы подробно объяснить принцип работы HashMap с точки зрения структуры хранения, анализа распространенных методов, расширения и безопасности.
Внутренняя реализация
Чтобы понять HashMap, вам сначала нужно знать, что такое HashMap, то есть его поле структуры хранения, а во-вторых, понять, что он может делать, то есть метод реализации его функции. Ниже мы подробно объясним эти два аспекта.
Поле структуры хранения
С точки зрения структурной реализации, HashMap реализуется массивом + связанный список + красно-черное дерево (часть красно-черного дерева добавлена в JDK1.8), как показано ниже.
Здесь необходимо понять две проблемы: что именно хранится в нижней части данных? Каковы преимущества этого метода хранения?
(1) Исходный код содержит очень важное поле в классе HashMap, которое представляет собой таблицу Node [], представляющую собой массив хэш-блоков. Очевидно, что это массив Node. Давайте посмотрим, что такое Node [JDK1.8].
Система вызовет метод hashCode () ключа «Meituan», чтобы получить его значение hashCode (этот метод применим к каждому объекту Java), а затем передаст вторые два шага алгоритма хеширования (операция высокого порядка и операция модуля, как описано ниже) ) Чтобы найти место хранения пары ключ-значение, иногда эти два ключа будут располагаться в одном и том же месте, что указывает на то, что произошло столкновение Hash. Конечно, чем более равномерно распределены результаты вычислений алгоритма хеширования, тем меньше вероятность коллизии хеш-функции и тем выше эффективность доступа к карте.
Прежде, чем понять процесс хеширования и расширения, мы должны сначала понять несколько полей хеш-карты. Из исходного кода конструктора HashMap по умолчанию конструктор должен инициализировать следующие поля: Исходный код выглядит следующим образом:
Поле размера на самом деле легко понять, то есть количество пар ключ-значение, которые фактически существуют в HashMap. Обратите внимание на разницу между длиной таблицы и максимальным порогом, чтобы учесть количество порогов. Поле modCount в основном используется для записи количества изменений внутренней структуры HashMap и в основном используется для быстрого сбоя итерации. Чтобы подчеркнуть один момент, изменения во внутренней структуре относятся к изменениям в структуре, таким как добавление новой пары ключ-значение, но значение, соответствующее ключу, перезаписывается, не является структурным изменением.
В HashMap длина таблицы массива хэш-блоков должна быть n-й степенью 2 (должно быть составным числом). Это нестандартный дизайн. Традиционный дизайн предназначен для расчета размера блока как простого числа. Условно говоря, вероятность того, что простое число вызывает конфликт, меньше, чем составное число, для конкретных доказательств вы можете обратиться к http://blog.csdn.net/liuqiyao_01/article/details/14475159 Начальный размер сегмента Hashtable равен 11, что означает, что размер сегмента задан как простое число (нельзя гарантировать, что Hashtable будет простым числом после расширения). HashMap принимает этот нетрадиционный дизайн, главным образом для оптимизации по модулю и расширения емкости, и в то же время, чтобы уменьшить конфликты, HashMap также присоединяется к процессу высокоуровневого участия в вычислении местоположения индекса сегмента хеша.
Здесь есть проблема: даже если коэффициент загрузки и алгоритм хеширования разработаны более разумно, это неизбежно приведет к ситуации, когда застежка-молния слишком длинная, а слишком длинная застежка-молния серьезно повлияет на производительность HashMap. Поэтому в версии JDK1.8 структура данных была дополнительно оптимизирована, и было представлено красно-черное дерево. Если длина связанного списка слишком велика (по умолчанию более 8), связанный список преобразуется в красно-черное дерево. Функция быстрого добавления, удаления, изменения и проверки красно-черного дерева используется для повышения производительности HashMap. Используются вставка, удаление и поиск красно-черного дерева. алгоритм. В этой статье больше не будет обсуждаться красно-черное дерево, если вы хотите узнать больше о том, как работает структура данных красно-черного дерева, вы можете обратиться http://blog.csdn.net/v_july_v/article/details/6105630 。
Метод реализации функции
Есть много внутренних функций HashMap. В этой статье в основном представлены три репрезентативные точки получения позиции индекса массива хэш-блоков в соответствии с ключом, подробное выполнение метода put и процесс расширения.