Как работает хэш мапа

Обновлено: 01.07.2024

Java HashMap-один из самых популярных классов коллекций в java. Java HashMap-это реализация на основе хэш-таблицы. HashMap в java расширяет класс AbstractMap, реализующий интерфейс карты.

Хэш-карта Java

Некоторые из важных моментов, касающихся HashMap в Java, заключаются в следующем;

Java HashMap допускает нулевой ключ и нулевые значения.
HashMap не является упорядоченной коллекцией. Вы можете перебирать записи хэш-карты с помощью набора ключей, но не гарантируется, что они будут в порядке их добавления в хэш-карту.
Хэш-карта почти похожа на хэш-таблицу, за исключением того, что она несинхронизирована и допускает нулевой ключ и значения.
HashMap использует свой внутренний узел класса для хранения записей карты.
HashMap хранит записи в нескольких односвязных списках, называемых корзинами или ячейками. По умолчанию количество ячеек равно 16, и оно всегда равно 2.
HashMap использует методы hashCode() и equals() для ключей для операций get и put. Таким образом, ключевой объект HashMap должен обеспечивать хорошую реализацию этих методов. Именно по этой причине неизменяемые классы лучше подходят для ключей, например, String и Integer.
Java HashMap не является потокобезопасным, для многопоточной среды следует использовать класс ConcurrentHashMap или синхронизировать карту с помощью Коллекций.Метод synchronizedMap () .

Конструкторы хэш-карт Java

Java HashMap предоставляет четыре конструктора.

общедоступная хэш-карта() : Наиболее часто используемый конструктор хэш-карты. Этот конструктор создаст пустую хэш-карту с начальной емкостью по умолчанию 16 и коэффициентом загрузки 0,75
общедоступная хэш-карта(int initialCapacity) : Этот конструктор хэш-карты используется для указания начальной емкости и коэффициента загрузки 0,75. Это полезно, чтобы избежать повторного хэширования, если вы знаете количество отображений, которые будут храниться в хэш-карте.
общедоступная хэш-карта(int initialCapacity, коэффициент загрузки с плавающей точкой) : Этот конструктор хэш-карты создаст пустую хэш-карту с заданной начальной емкостью и коэффициентом загрузки. Вы можете использовать это, если знаете максимальное количество отображений, которые будут храниться в HashMap. В распространенных сценариях этого следует избегать, поскольку коэффициент загрузки 0,75 обеспечивает хороший компромисс между пространственными и временными затратами.
общедоступная хэш-карта(карта расширяет K, ? расширяет V> m) : Создает карту, имеющую те же сопоставления, что и указанная карта, и с коэффициентом загрузки 0,75 расширяет K, ? расширяет V> m)

Пример конструкторов хэш-карт Java

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

Методы хэш-карты Java

Давайте рассмотрим важные методы HashMap в java.

В HashMap появилось много новых методов, представленных в Java 8.

открытый V вычислитель(ключ K, Функция super K, ? расширяет V> Функция сопоставления) : Если указанный ключ еще не связан со значением (или сопоставлен нулю), этот метод пытается вычислить его значение с помощью данной функции сопоставления и вводит его в хэш-карту, если значение не равно нулю. super K, ? расширяет V> Функция сопоставления)
: Если указанный ключ еще не связан со значением (или сопоставлен нулю), этот метод пытается вычислить его значение с помощью данной функции сопоставления и вводит его в хэш-карту, если значение не равно нулю. общедоступный V-вычислитель(ключ K, бифункция super K, ? super V, ? расширяет V> Функция переназначения)
: Если значение для указанного ключа присутствует и не равно нулю, пытается вычислить новое сопоставление с учетом ключа и его текущего сопоставленного значения. super K, ? super V, ? расширяет V> Функция переназначения) : Если значение для указанного ключа присутствует и не равно нулю, пытается вычислить новое сопоставление с учетом ключа и его текущего сопоставленного значения.
открытые вычисления V(ключ K, бифункция super K, ? super V, ? расширяет V> Функция переназначения) : Этот метод хэш-карты пытается вычислить сопоставление для указанного ключа и его текущего отображенного значения. super K, ? super V, ? расширяет V> Функция переназначения)
: Этот метод хэш-карты пытается вычислить сопоставление для указанного ключа и его текущего отображенного значения. публичная пустота для каждого(двоякий номер super K, ? super V> действие)
: Этот метод выполняет данное действие для каждой записи на этой карте. super K, ? super V> действие) : Этот метод выполняет данное действие для каждой записи на этой карте.
открытый V getOrDefault(ключ объекта, V значение по умолчанию) : То же, что и get, за исключением того, что значение по умолчанию возвращается, если для указанного ключа не найдено сопоставление.
открытое слияние V(ключ K, значение V, бифункция super V, ? super V, ? расширяет V> Функция переназначения) : Если указанный ключ еще не связан со значением или связан с null, свяжите его с заданным ненулевым значением. В противном случае заменяет связанное значение результатами данной функции переназначения или удаляет, если результат равен нулю. super V, ? super V, ? расширяет V> Функция переназначения)
: Если указанный ключ еще не связан со значением или связан с null, свяжите его с заданным ненулевым значением. В противном случае заменяет связанное значение результатами данной функции переназначения или удаляет, если результат равен нулю. public V putIfAbsent(ключ K, значение V)
: Если указанный ключ еще не связан со значением (или сопоставлен нулю), связывает его с заданным значением и возвращает значение null, else возвращает текущее значение. публичное логическое удаление(ключ объекта, значение объекта)
: Удаляет запись для указанного ключа, только если он в данный момент сопоставлен с указанным значением. публичная логическая замена(K ключ, V старое значение, V новое значение)

Пример хэш-карты Java

Вот простая программа java для часто используемых методов HashMap.

Как работает HashMap в java?

HashMap в java использует узел внутреннего класса для хранения сопоставлений. HashMap работает по алгоритму хеширования и использует методы hashCode() и equals() для операций забывания и ввода ключей.

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

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

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

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

Рекомендуется прочитать : Хэш-код и значение метода equals в Java

Коэффициент загрузки хэш-карты Java

Коэффициент загрузки используется для определения того, когда хэш-карта будет повторно хэширована и размер корзины будет увеличен. Значение по умолчанию ведра или емкости равно 16, а коэффициент загрузки равен 0,75. Пороговое значение для повторной обработки рассчитывается путем умножения емкости и коэффициента загрузки. Таким образом, пороговое значение по умолчанию будет равно 12. Поэтому, когда хэш-карта будет иметь более 12 сопоставлений, она будет перефразирована, и количество ячеек будет увеличено до следующего уровня 2, т. е. 32. Обратите внимание, что емкость хэш-карты всегда равна 2.

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

Набор ключей Java HashMap

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

Вывод вышеприведенной программы даст понять, что набор ключей поддерживается картой.

Значения хэш-карты Java

Метод значений Java HashMap возвращает представление коллекции значений на карте. Эта коллекция поддерживается HashMap, поэтому любые изменения в HashMap будут отражены в коллекции значений и наоборот. Приведенный ниже простой пример подтверждает такое поведение коллекции значений HashMap.

Результаты вышеприведенной программы приведены ниже.

Набор записей Java HashMap

Метод ввода Java HashMap возвращает заданное представление отображений. Этот набор записей поддерживается HashMap, поэтому любые изменения в карте отражаются в наборе записей и наоборот. Взгляните на приведенный ниже пример программы для примера набора данных HashMap.

Java HashMap putIfAbsent

Простой пример метода HashMap putIfAbsent, представленного в Java 8.

Результатом вышеуказанной программы является;

Хэш-карта Java для каждого

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

Java HashMap заменяет все

Метод HashMap replaceAll может использоваться для замены значения каждой записи результатом вызова данной функции для этой записи. Этот метод добавлен в Java 8, и мы можем использовать лямбда-выражения для аргумента этого метода.

Вывод вышеприведенной программы замены хэш-карты-это;

Java HashMap computeIfAbsent

Метод HashMap computeIfAbsent вычисляет значение только в том случае, если ключ отсутствует на карте. После вычисления значения оно помещается на карту, если оно не равно нулю.

Результатом вышеуказанной программы является;

Java HashMap вычислитьпредставление

Метод Java HashMap computeIfPresent пересчитывает значение, если указанный ключ присутствует, а значение не равно нулю. Если функция возвращает значение null, сопоставление удаляется.

Выходные данные, полученные с помощью HashMap computeifпредставительный пример;

Вычисление хэш-карты Java

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

Слияние хэш-карт Java

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

Результатом вышеуказанной программы является;

Это все для HashMap на Java, я надеюсь, что ничего важного не пропущено. Поделитесь им и с другими, если вам понравилось.

Вычисляется хеш-значение ключа введенного объекта. Хэш ключа вычисляет метод static final int hash(Object key) , который уже обращается к известному нам методу hashCode() ключа. Для этого используется либо переопределенный метод hashCode() , либо его реализация по умолчанию. Дополнительные преобразования в методе hash() :

Почему бы просто не вычислить с помощью hashCode() ? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int 'a будут заполнены. Например, для Integer , Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-кодов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в какой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша объекта начали вносить коррективы в то, в какой бакет попадёт объект) и, как следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:

где n – длина массива.

Создается объект Node.

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

Теперь к очень подробному примеру.

Создадим объект класса HashMap:

С помощью метода put() добавим в хеш-отображение первую пару «ключ-значение»:

В этот момент внутри вызывается метод putVal() .

С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-код ключа, внутри которого предварительно вычисляется хеш-код с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное значение» – 2306967. Может проверить в IDEA с помощью

Полученный хеш-код модифицируется по формуле: (хеш-код) ^ (хеш-код>>> 16) , и в результате получаем окончательный хеш-код – 2306996 .

Проверяем таблицу на «пустоту»:

где [] tab — сама хеш-таблица: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.

Так как проверка вернёт true (потому что массив для таблицы не был создан с помощью оператора new в конструкторе), будет вызван метод resize() , который собственно и создаст таблицу размером на 16 элементов. Да-да, конструкторы класса никакой таблица не создают. Вместо этого всегда происходит вызов метода resize() при первом добавлении элемента. Длина созданной таблицы (считай длина массива) будет записана в переменную n – n = (tab = resize()).length , которая в дальнейшем используется для вычисления бакета.

Одновременно вычисляем индекс бакета, куда будет помещен наш объект, и проверяем, а есть ли уже в нем элементы. Вычисляем:

Так как в результате проверки мы получим true (в бакете элементов нет), будет сгенерирован объект Node со следующими полями:

Наш сформированный объект Node будет добавлен в бакет под индексом [4]:

newNode() — это метод, который просто возвращает объект класса Node.

После добавления будет произведена проверка не превышает ли текущее количество элементов параметр threshold :

Если превышает, тогда будет вызван метод resize() для увеличения размера хеш-таблицы.

На этом метод putVal() (соответственно и put() ) завершит свою работу.

Графически полученный результат изобразить можно так:

Так в общем случае выглядит добавление Node (пара «ключ-значение») в хеш-таблицу, если нужный бакет оказывается пуст. Теперь попробуем добавить такой элемент, который приведет к коллизии (когда в одном бакете оказывается более одного элемента).

external chaining или метод цепочек (реализован в HashMap) — т.е. в ячейке на самом деле содержится список (chain). А уже в списке может содержаться несколько значений (не обязательно с одинаковым хеш-кодом).
linear probing или метод открытой адресации (реализован в IdentityHashMap) – заключается в поиске первой пустой ячейки после той, на которую указала хеш-функция;

С помощью метода put() добавим в хеш-отображение еще одну пару «ключ-значение»:

Вычисляем "предварительный хеш" – 63281361. Модифицируем его и в результате получаем окончательный хеш-код – 63281940.

Так как первая проверка на «пустоту» теперь вернет false (создавать таблицу не надо), сразу вычисляем индекс бакета, куда будет помещен наш объект:

Бакет под указанным индексом проверяется на наличие в нем элементов и так как условие if ((p = tab[i = (n - 1) & hash]) == null) в этом случае не выполняется (в бакете уже есть элемент), тогда переходим к блоку else .

В первую очередь мы сравниваем добавляемый элемент с первым элементом связного списка внутри бакета:

При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется ( && ), так как объекты гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неравенства, ключи сравниваются уже посредством метода equals() . Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать значение у ключа:

В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).

Игнорируем условие ( p instanceof TreeNode ), так как структура в бакете не является древовидной на данном этапе.

Далее переходим в цикл for , где в пределах одного бакета проверяем у элементов указатель на следующий элемент next , и если он равен null (значит элемент в списке последний и единственный), добавляем новый элемент Node в конец списка:

Вы можете спросить, а где же проверка на равенство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого элемента, и так как он сейчас равен null, можно сделать вывод о том, что в списке только один элемент. И так как мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.

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

Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать значение у ключа.

После добавления второго элемента наш объект HashMap графически выглядит так:

В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:

проверяем с помощью методов hashCode() и equals() , что оба ключа одинаковы.
если ключи одинаковы, заменить текущее значение новым.
иначе связать новый и старый объекты с помощью структуры данных "связный список", указав ссылку на следующий объект в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре

После каждой итерации (добавления нового элемента) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:

До тех пор, пока их количество не станет равно или больше 7:

В таком случае произойдет вызов метода treeifyBin()treeify() для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:

Вместо перехода к древовидной структуре будет вызван метод resize() для увеличения размера хеш-таблицы с перераспределением элементов. treeify() в свою очередь связный список из TreeNode конвертирует в красно-черное дерево. Метод resize() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.

Если кратко, не вдаваясь в подробности структуры красно-черного дерева, то происходит следующее:

Первый элемент списка записывается как корень всего дерева (чёрный цвет):

Для остальных элементов:

распределяем их налево или направо в зависимости от значения хешей:

Все левые потомки должны быть меньше своего корневого узла (или равны ему), в то время как все правые потомки должны быть больше.

Если у двух элементов совпали хеши и их нельзя сравнить иным образом (не реализуют интерфейс Comparable ), прерываем построение дерева и вызываем метод tieBreakOrder() , который в свою очередь использует нативный метод System.identityHashCode() для вычисления глобального уникального хеш-кода.

Проверяем элементы дерева (объекты TreeNode ) до тех пор, пока не будет найден дочерний (левый или правый) нулевой элемент.

Добавляем дочерний узел (левый или правый в зависимости от dir):

Так как при добавлении нового элемента может нарушиться баланс дерева, вызываем метод для перебалансировки:

Про балансировку КЧД можно почитать здесь: хабр

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

Как строится и самобалансируется красно-черное дерево можно наглядно посмотреть здесь: визуализация

Вычислить хэш код ключа.
Вычислить индекс бакета.
Перейти по индексу и сравнить ключ первого элемента с имеющимся значением. Если они равны – вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.
Если следующий объект Node равен null, возвращаем null.
Если следующий объект Node не равен null, переходим к нему и повторяем первые три шага до тех пор, пока элемент не будет найден или следующий объект Node не будет равен null.

существует ли вообще хеш-таблица: (tab = table) != null

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

если предыдущее выражение возвращает true, необходимо убедиться в том, что длина внутреннего массива больше 0: (n = tab.length) > 0;

если предыдущее выражение также возвращает true, переходим в бакет под индексом (в нашем случае 4), который был предварительно вычислен, и проверяем его на наличие в нем элементов:

Сравниваем ключ, который мы ищем, с ключом первого элемента в списке внутри бакета, так как в большинстве бакетов будет находиться (не везде же у нас коллизии) только один элемент (наш случай). Как и в случае с методом put() , сравниваются хеши, и если они совпадают, ключи сравниваются по ссылке, и только потом по equals() .

Так как в нашем случае, ключ “KING” будет предшествовать ключу “BLAKE” (внутри связного списка новые элементы добавляются в конец, а KING был добавлен первым), мы остановимся на данном этапе и вернем объект first типа Node методу get(), который «выцепит» у него поле со значением (100):

Если внутри бакета находится больше одного элемента, тогда:

если бакет представляет собой связный список – проходимся в списке по каждому из элементов в цикле do – while до тех пор , пока не будет найдено совпадение:

если бакет представляет собой древовидную структуру, тогда дополнительно вызывается метод getTreeNode() , который в свою очередь для поиска нужного ключа использует метод find() . Осуществляем поиск по дереву – сравниваются хеши и определяется левый или правый узел корня для поиска. Если ключи равны (по ссылке или по equals ), возвращаем этот узел. Если левый или правый дочерний узлы равны null, дополнительно сравниваем ключи через compareTo (если ключи реализуют интерфейс Comparable ), иначе осуществляем рекурсивный поиск по дереву (правому или левому поддереву), пока не будет найдено совпадение.

заходим в нужный бакет (опять же он предварительно вычисляется);

если в бакете только один объект (проверяем у него указатель null) сравниваем хеши, ссылки и equals (если вдруг хеши не равны). Нашлось совпадение? Отлично, это наш ключ – удаляем его (=null) и возвращаем значение этого ключа.

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

Этот API устарел. Вместо него следует использовать класс unordered_map.

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

Синтаксис

Параметры

Раздел
Тип данных ключа для сохранения в hash_map.

Тип
Тип данных элемента для сохранения в hash_map.

Признаки
Тип, который включает два объекта-функции, один из классов compare, который может сравнить значения двух элементов как ключей сортировки, чтобы определить их относительный порядок, и хэш-функцию, которая является унарным предикатом, который сопоставляет значения ключей элементов с целыми числами без знака типа size_t . Этот аргумент является необязательным, и hash_compare< Key Key значение по умолчанию меньше<> > .

Выделен
Тип, представляющий сохраненный объект распределителя, который инкапсулирует сведения о выделении и освобождении памяти для hash_map. Этот аргумент является необязательным, а значение по умолчанию — распределитель <pair <const Key , Type >>.

Remarks

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

Является реверсивным, поскольку предоставляет двунаправленный итератор для получения доступа к его элементам.

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

Является уникальным, поскольку каждый его элемент должен обладать уникальным ключом.

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

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

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

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

Класс hash_map должен быть используемым ассоциативным контейнером, если условия, связывающие значения с ключами, удовлетворяются приложением. Модель этого типа структуры представляет собой упорядоченный список уникальных ключевых слов со связанными строковыми значениями, предоставляющими, к примеру, определения. Если вместо этого для слов существует несколько правильных определений и ключи не являются уникальными, предпочтительным контейнером будет hash_multimap. Если же сохранен только список слов, то в качестве контейнера необходимо выбрать набор hash_set. Если допускается многократное использование слов, то подходящей структурой контейнера будет hash_multiset.

Hash_map упорядочивает последовательность, которую он контролирует, вызывая хранимый объект признаков хэша класса value_compare. Доступ к этому сохраненному объекту можно получить путем вызова функции-члена key_comp. Такой объект функции должен вести себя так же, как объект класса hash_compare<Key, меньше <Key>>. В частности, для всех значений ключа типа Key вызов Traits ( Key ) дает распределение значений типа size_t .

В целом, упорядочиваемые элементы должны лишь подлежать сравнению "меньше чем" для установления такого порядка, чтобы, имея любые два элемента, можно было определить, что они равны (ни один не меньше другого) или что один меньше другого. Это приводит к упорядочению неравнозначных элементов. С более технической точки зрения, функция сравнения является бинарным предикатом, который вызывает строгого слабое упорядочение в стандартном математически смысле. Бинарный предикат f (x y) — это объект функции, имеющий два объекта-аргумента x и y возвращаемое значение true или false . Порядок, заданный для hash_map, является строгим слабым порядком, если бинарный предикат является нерефлексивным, антисимметричным и переходящим и если эквивалентность является переходящей, где два объекта x и y определяются как эквивалентные, когда оба параметра f(x,y) и f(y,x) имеют значение false. Если более строгое условие равенства между ключами заменяет условие эквивалентности, порядок становится общим (т.е. все элементы упорядочиваются относительно друг друга), и сопоставленные ключи будут неотличимы друг от друга.

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

Итератор, предоставляемый классом hash_map, является двусторонним итератором, но функции — члены класса insert и hash_map обладают версиями, принимающими в качестве параметров шаблона более слабый итератор ввода, чьи функциональные требования ниже, чем гарантированные классом двунаправленных итераторов. Различные концепции итераторов образуют семейство, связанное уточнениями функциональности. Каждая концепция итератора имеет собственный набор требований, а алгоритмы, работающие с ними, должны ограничивать свои предположения согласно требованиям, предоставляемым этим типом итератора. Можно предположить, что итератор ввода может быть разыменован для обращения к определенному объекту и инкрементирован до следующего итератора в последовательности. Это минимальный набор функциональных возможностей, но его достаточно, чтобы иметь возможность осмысленно говорить о диапазоне итераторов [First, Last) , в контексте функций — членов класса.

Реализации HashMap в Java Collections Framework

HashMap имеет следующие особенности:

Коэффициент загрузки по умолчанию и начальная мощность 0,75 и 16 соответственно. Их значения важны для производительности HashMap, поскольку они могут оптимизировать производительность итераций и количество операций изменения размера и повторного хеширования.
Нет гарантий порядка итераций.
Производительность итерации зависит от начальной емкости (количества сегментов) плюс количества записей. Таким образом, очень важно не устанавливать слишком высокую начальную мощность (или слишком низкий коэффициент загрузки).
Никаких повторяющихся ключей. Разрешает один нулевой ключ и несколько нулевых значений.
Проблема коллизии хэша решена за счет использования древовидной структуры данных, начиная с Java 8, для обеспечения отдельной цепочки.
Предлагает постоянное время O (1) в среднем и линейное время O (n) в худшем случае производительность для основных операций, таких как получение, размещение и удаление.
Чем меньше повторяющихся хэш-кодов, тем выше прирост производительности для вышеуказанных операций.
Ключевые объекты сравниваются на основе их равенства и реализации hashCode.
Объекты значений сравниваются на основе реализации их метода равенства.
HashMap не является потокобезопасным, поскольку это несинхронизированная реализация.
В многопоточном окружении хотя бы один поток изменяет карту, она должна быть синхронизирована извне.

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

HashMap против LinkedHashMap и TreeMap

HashMap не имеет гарантий упорядочивания и работает быстрее, чем TreeMap (постоянное время по сравнению с временем журнала для большинства операций)

LinkedHashMap обеспечивает итерацию с упорядоченной вставкой и работает почти так же быстро, как HashMap.

TreeMap обеспечивает итерацию по порядку значений. TreeMap можно использовать для сортировки HashMap или LinkedHashMap

Объявление HashMap

В результате иерархии классов вы можете объявить HashMap следующими способами:

Создание и инициализация

Предоставьте фабричный метод Map.of или Map.ofEntries, начиная с Java 9, в конструктор HashMap (Map) для создания и инициализации HashMap в одной строке во время создания.

Вы также можете инициализировать HashMap после времени создания, используя put, Java 8+ putIfAbsent, putAll.

Итерация HashMap

Вы можете перебирать пары ключ-значение HashMap, используя Java 8+ forEach (BiConsumer).

Итерировать по HashMap keySet() или values() с Java 8+ forEach(Consumer).

Получение и фильтрация

Используйте entrySet(), keySet(), values(), чтобы получить набор записей сопоставления ключ-значение, набор ключей и набор значений соответственно.

Получить значение по указанному ключу с помощью get(key).

Фильтрация ключей или значений HashMap с помощью Java 8+ Stream API.

Добавление, обновление и удаление

HashMap предоставляет методы containsKey (ключ), containsValue (значение), put (ключ, значение), replace (ключ, значение) и remove (ключ), чтобы проверить, содержит ли HashMap указанный ключ или значение, чтобы добавить новый ключ. пара значений, обновить значение по ключу, удалить запись по ключу соответственно.

Сравнение объектов в HashMap

Внутренне основные операции HashMap, такие как containsKey, containsValue, put, putIfAbsent, replace и remove, работают на основе сравнения объектов элементов, которые зависят от их равенства и реализации hashCode.

В следующем примере ожидаемые результаты не достигаются из-за отсутствия реализации equals и hashCode для определенных пользователем объектов.

Вы можете решить указанную выше проблему, переопределив equals и hashCode, как показано в примере ниже.

Сортировка HashMap

В Java нет прямого API для сортировки HashMap. Однако вы можете сделать это через TreeMap, TreeSet и ArrayList вместе с Comparable и Comparator.

В следующем примере используются статические методы comparingByKey (Comparator) и comparingByValue (Comparator) для Map.Entry для сортировки ArrayList по ключам и по значениям соответственно. Этот ArrayList создается и инициализируется из entrySet() HashMap.

@Test
public void sortByKeysAndByValues_WithArrayListAndComparator() Map.Entry e1 = Map.entry("k1", 1);
Map.Entry e2 = Map.entry("k2", 20);
Map.Entry e3 = Map.entry("k3", 3);

Map map = new HashMap<>(Map.ofEntries(e3, e1, e2));

List > arrayList1 = new ArrayList<>(map.entrySet());
arrayList1.sort(comparingByKey(Comparator.naturalOrder()));
assertThat(arrayList1).containsExactly(e1, e2, e3);

List > arrayList2 = new ArrayList<>(map.entrySet());
arrayList2.sort(comparingByValue(Comparator.reverseOrder()));
assertThat(arrayList2).containsExactly(e2, e3, e1);
>
Ниже представлен полный пример исходного кода.

public class HashMapTest @Test
public void declare() Map map1 = new HashMap<>();
assertThat(map1).isInstanceOf(HashMap.class);

HashMap map2 = new HashMap<>();
>

@Test
public void initInOneLineWithFactoryMethods() // create and initialize a HashMap from Java 9+ Map.of
Map map1 = new HashMap<>((Map.of("k1", 1, "k3", 2, "k2", 3)));
assertThat(map1).hasSize(3);

// create and initialize a HashMap from Java 9+ Map.ofEntries
Map map2 = new HashMap<>(Map.ofEntries(Map.entry("k4", 4), Map.entry("k5", 5)));
assertThat(map2).hasSize(2);
>

@Test
public void initializeWithPutIfAbsent() // Create a new HashMap
Map map = new HashMap<>();

// Add elements to HashMap
map.putIfAbsent("k1", 1);
map.putIfAbsent("k2", 2);
map.putIfAbsent("k3", 3);

// Can add null key and value
map.putIfAbsent(null, 4);
map.putIfAbsent("k4", null);

// Duplicate key will be ignored
map.putIfAbsent("k1", 10);
assertThat(map).hasSize(5);

// The output ordering will be vary as HashMap is not reserved the insertion order
System.out.println(map);
>

@Test
public void iterateOverKeyValuePairs() Map map = new HashMap<>(Map.of("k1", 1, "k2", 2));
map.forEach((k, v) -> System.out.printf("%s=%d ", k, v));
>

@Test
public void iterateOverKeySet() Map map = new HashMap<>(Map.of("k1", 1, "k2", 2));
map.values().forEach(k -> System.out.printf("%s ", k));
>

@Test
public void retrieve() Map hashMap = new HashMap<>(Map.of("k1", 1, "k2", 2));

Set > entrySet = hashMap.entrySet();
assertThat(entrySet).contains(Map.entry("k1", 1), Map.entry("k2", 2));

Set keySet = hashMap.keySet();
assertThat(keySet).contains("k1", "k2");

Collection values = hashMap.values();
assertThat(values).contains(1, 2);
>

@Test
public void getValueByKey() Map map = new HashMap<>(Map.of("k1", 1, "k2", 2));
int value = map.get("k1");

@Test
public void filter() Map map = new HashMap<>(Map.of("k1", 1, "k2", 2));
Integer[] arr = map.values().stream().filter(v -> v > 1).toArray(Integer[]::new);
assertThat(arr).contains(2);
>

@Test
public void containsPutReplaceRemove() Map map = new HashMap<>(Map.of("k1", 1, "k2", 2));

boolean containedKey = map.containsKey("k1");
assertThat(containedKey).isTrue();

boolean containedValue = map.containsValue(2);
assertThat(containedValue).isTrue();

map.put("k3", 3);
assertThat(map).hasSize(3);

map.replace("k1", 10);
assertThat(map).contains(Map.entry("k1", 10), Map.entry("k2", 2), Map.entry("k3", 3));

map.remove("k3");
assertThat(map).contains(Map.entry("k1", 10), Map.entry("k2", 2));
>

@Test
public void objectsComparingProblem() Map hashMap = new HashMap<>();

hashMap.put(new Category(1, "c1"), new Book(1, "b1"));

boolean containedKey = hashMap.containsKey(new Category(1, "c1"));
assertThat(containedKey).isFalse();

boolean containedValue = hashMap.containsValue(new Book(1, "b1"));
assertThat(containedValue).isFalse();

hashMap.put(new Category(1, "c1"), new Book(1, "b1"));
assertThat(hashMap).hasSize(2);

Book previousValue = hashMap.replace(new Category(1, "c1"), new Book(2, "b1"));
assertThat(previousValue).isNull();

hashMap.remove(new Category(1, "c1"));
assertThat(hashMap).hasSize(2);
>

static class Category int id;
String name;

Category(int id, String name) this.id = id;
this.name = name;
>
>

static class Book int id;
String title;

Book(int id, String title) this.id = id;
this.title = title;
>
>

@Test
public void objectsComparingFixed() Map hashMap = new HashMap<>();

hashMap.put(new CategoryFixed(1, "c1"), new BookFixed(1, "b1"));

boolean containedKey = hashMap.containsKey(new CategoryFixed(1, "c1"));
assertThat(containedKey).isTrue();

boolean containedValue = hashMap.containsValue(new BookFixed(1, "b1"));
assertThat(containedValue).isTrue();

hashMap.put(new CategoryFixed(1, "c1"), new BookFixed(1, "b1"));
assertThat(hashMap).hasSize(1);

BookFixed previousValue = hashMap.replace(new CategoryFixed(1, "c1"), new BookFixed(2, "b1"));
assertThat(previousValue).isNotNull();

hashMap.remove(new CategoryFixed(1, "c1"));
assertThat(hashMap).hasSize(0);
>

static class CategoryFixed int id;
String name;

CategoryFixed(int id, String name) this.id = id;
this.name = name;
>

@Override
public boolean equals(Object o) if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
CategoryFixed that = (CategoryFixed) o;
return that.id &&
Objects.equals(name, that.name);
>

@Override
public int hashCode() return Objects.hash(id, name);
>
>

static class BookFixed int id;
String title;

BookFixed(int id, String title) this.id = id;
this.title = title;
>

@Override
public boolean equals(Object o) if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
BookFixed bookFixed = (BookFixed) o;
return bookFixed.id &&
Objects.equals(title, bookFixed.title);
>

@Override
public int hashCode() return Objects.hash(id, title);
>
>

@Test
public void sortByKeysAndByValues_WithArrayListAndComparator() Map.Entry e1 = Map.entry("k1", 1);
Map.Entry e2 = Map.entry("k2", 20);
Map.Entry e3 = Map.entry("k3", 3);

Map map = new HashMap<>(Map.ofEntries(e3, e1, e2));

List > arrayList1 = new ArrayList<>(map.entrySet());
arrayList1.sort(comparingByKey(Comparator.naturalOrder()));
assertThat(arrayList1).containsExactly(e1, e2, e3);

List > arrayList2 = new ArrayList<>(map.entrySet());
arrayList2.sort(comparingByValue(Comparator.reverseOrder()));
assertThat(arrayList2).containsExactly(e2, e3, e1);
>
>

Средняя оценка / 5. Количество голосов:

Спасибо, помогите другим - напишите комментарий, добавьте информации к статье.

Читайте также: