Hashmap put не работает

Значение не вставлено в HashMap из put ()

Рассмотрим следующий фрагмент кода:

Карта size равна 6.

Карта table содержит следующее содержание:

FOUR исчез. Как отмечалось ранее, было бы разумно вычислить hashCode моих записей по модулю размера карты. Это дает следующий результат:

Как мы видим, hashCode ничего не указывает, учитывая столкновение FOUR с каким-либо значением. Это также работает с ConcurrentHashMap и LinkedHashMap , так что я предполагаю, что это проблема HashMap .

Может кто-нибудь объяснить мне, что на самом деле происходит? Я совершенно потерялся в этом.

2 ответа

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

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

Взгляните на исходный код HashMap.Node :

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

В вашем примере кода создается следующая таблица:

Кстати . Печать всей карты дает следующее:

«ЧЕТЫРЕ» никуда не делись. Вы сами убедились, что размер карты равен 6, и если вы распечатаете карту, вы увидите все 6 записей.

Если вы посмотрите более внимательно в отладчике, вы увидите, что ключи «ONE» и «FOUR» сопоставлены с одним и тем же сегментом (индекс 7). Это может произойти, даже если у них разный хэш-код (поскольку HashMap выполняет некоторые дополнительные вычисления для hashCode() ключа, а затем выполняет % table.length для результата, чтобы получить индекс ковша).

В вашем примере хеш-значение, вычисленное для «ONE», составляет 78407, а для «FOUR» — 2163975. Поскольку начальное количество сегментов по умолчанию равно 16, сегмент вычисляется следующим образом: 78407% 16 == 2163975% 16 == 7, поэтому оба ключа хранятся в одном ведре.

Источник

Внутренняя работа HashMap в Java

[примечание от автора перевода] Перевод был выполнен для собственных нужд, но если кому -то это окажется полезным, значит мир стал хоть немного, но лучше! Оригинальная статья — Internal Working of HashMap in Java

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

Как и в предыдущей статье, HashMap содержит массив Node и Node может представлять класс, содержащий следующие объекты:

1. int — хэш
2. K — ключ
3. V — значение
4. Node — следующий элемент

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

Хэширование

Хэширование -это процесс преобразования объекта в целочисленную форму, выполняется с помощью метода hashCode(). Очень важно правильно реализовать метод hashCode() для обеспечения лучшей производительности класса HashMap.

Здесь я использую свой собственный класс Key и таким образом могу переопределить метод hashCode() для демонстрации различных сценариев. Мой класс Key:

Здесь переопределенный метод hashCode() возвращает ASCII код первого символа строки. Таким образом, если первые символы строки одинаковые, то и хэш коды будут одинаковыми. Не стоит использовать подобную логику в своих программах.

Этот код создан исключительно для демонстрации. Поскольку HashCode допускает ключ типа null, хэш код null всегда будет равен 0.

Метод hashCode()

Метод hashCode() используется для получения хэш кода объекта. Метод hashCode() класса Object возвращает ссылку памяти объекта в целочисленной форме (идентификационный хеш (identity hash code)). Сигнатура метода public native hashCode() . Это говорит о том, что метод реализован как нативный, поскольку в java нет какого -то метода позволяющего получить ссылку на объект. Допускается определять собственную реализацию метода hashCode(). В классе HashMap метод hashCode() используется для вычисления корзины (bucket) и следовательно вычисления индекса.

Метод equals()

Метод equals используется для проверки двух объектов на равенство. Метод реализованн в классе Object. Вы можете переопределить его в своем собственном классе. В классе HashMap метод equals() используется для проверки равенства ключей. В случае, если ключи равны, метод equals() возвращает true, иначе false.

Корзины (Buckets)

Bucket -это единственный элемент массива HashMap. Он используется для хранения узлов (Nodes). Два или более узла могут иметь один и тот -же bucket. В этом случае для связи узлов используется структура данных связанный список. Bucket -ы различаются по ёмкости (свойство capacity). Отношение между bucket и capacity выглядит следующим образом:

Один bucket может иметь более, чем один узел, это зависит от реализации метода hashCode(). Чем лучше реализованн ваш метод hashCode(), тем лучше будут использоваться ваши bucket -ы.

Вычисление индекса в HashMap

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

где n равна числу bucket или значению длины массива. В нашем примере я рассматриваю n, как значение по умолчанию равное 16.

• изначально пустой hashMap: здесь размер hashmap равен 16:

HashMap:

• вставка пар Ключ — Значение: добавить одну пару ключ — значение в конец HashMap

Вычислить значение ключа <"vishal">. Оно будет сгенерированно, как 118.

Вычислить индекс с помощью метода index , который будет равен 6.

Создать объект node.

Поместить объект в позицию с индексом 6, если место свободно.

Теперь HashMap выглядит примерно так:

• добавление другой пары ключ — значение: теперь добавим другую пару

Вычислить значение ключа <"sachin">. Оно будет сгенерированно, как 115.

Вычислить индекс с помощью метода index , который будет равен 3.

Создать объект node.

Поместить объект в позицию с индексом 3, если место свободно.

Теперь HashMap выглядит примерно так:

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

Вычислить значение ключа <"vaibhav">. Оно будет сгенерированно, как 118.

Вычислить индекс с помощью метода index , который будет равен 6.

Создать объект node.

Поместить объект в позицию с индексом 6, если место свободно.

В данном случае в позиции с индексом 6 уже существует другой объект, этот случай называется коллизией.

В таком случае проверям с помощью методов hashCode() и equals(), что оба ключа одинаковы.

Если ключи одинаковы, заменить текущее значение новым.

Иначе связать новый и старый объекты с помощью структуры данных «связанный список», указав ссылку на следующий объект в текущем и сохранить оба под индексом 6.

Теперь HashMap выглядит примерно так:

[примечание от автора перевода] Изображение взято из оригинальной статьи и изначально содержит ошибку. Ссылка на следующий объект в объекте vishal с индексом 6 не равна null, в ней содержится указатель на объект vaibhav.

• получаем значение по ключу sachin:

Вычислить хэш код объекта <“sachin”>. Он был сгенерирован, как 115.

Вычислить индекс с помощью метода index , который будет равен 3.

Перейти по индексу 3 и сравнить ключ первого элемента с имеющемся значением. Если они равны -вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.

В нашем случае элемент найден и возвращаемое значение равно 30.

Вычислить хэш код объекта <"vaibhav">. Он был сгенерирован, как 118.

Вычислить индекс с помощью метода index , который будет равен 6.

Перейти по индексу 6 и сравнить ключ первого элемента с имеющемся значением. Если они равны -вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.

В данном случае он не найден и следующий объект node не равен null.

Если следующий объект node равен null, возвращаем null.

Если следующий объект node не равен null, переходим к нему и повторяем первые три шага до тех пор, пока элемент не будет найден или следующий объект node не будет равен null.

Изменения в Java 8

Как мы уже знаем в случае возникновения коллизий объект node сохраняется в структуре данных «связанный список» и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n).

Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).

Источник

Метод Java HashMap put не работает

Я пытался сделать упражнение, создавая PhoneBook с помощью HashMap .
Однако я вижу, что мой метод addPhone не добавляет новый телефон к моему PhoneBook pb то есть data.put(name, num); метод внутри моего addPhone не помещает данные в data HashMap .

Может кто-нибудь объяснить мне, что здесь не так?

UPD Теперь я понимаю, что это была ошибка, я использовал containsValue а не containsKey . Так просто!
Но этот вопрос совсем не похож на предложенный уже существующий вопрос. Я не спрашивал. Is checking for key existence in HashMap always necessary? Я знаю о способах поиска HashMap соответствии с ключом или значением. Этот вопрос на самом деле вызван ошибкой. Однако я получил здесь очень широкие и полезные ответы. Я считаю, что эти ответы, особенно ответ davidxxx, превосходны и могут быть полезны для многих людей.

Вы data.containsValue(name) имя, которое является ключом к data.containsValue(name) вместо значения.
Вам понадобится Map.containskey() если вы хотите вернуть значение в соответствии с ключом с клиентской стороны вашего класса.

Обратите внимание, что обработка существования на карте не требуется, поскольку null возвращается, поскольку для ключа не существует сопоставления:

Примечание

Не проблема в вопросе, а какая проблема.
ToString() действительно не является хорошим именем для метода:

Имена методов чувствительны к регистру, да, но это не справедливая причина, чтобы играть с этим, чтобы определить немного другое именование (здесь есть верхний регистр T ) для Object.toString() . Это делает ввод кода неверным.
Кроме того, ваш метод ничего не возвращает. Так что это беспомощно: pb.ToString();

То, что вы должны объявить:

Добавление @Override добавляет ограничение компиляции, которое проверяет, что метод определен в иерархии.

Теперь вы можете, например, записать в стандартный вывод представление toString() вашего объекта PhoneBook таким образом:

Источник

Русские Блоги

Анализ исходного кода HashMap. Почему HashMap не работает?

Анализ исходного кода HashMap

Почему HashMap вышел из строя?

Не по темеНедавно мой друг задал мне вопрос, который я тоже задал своему учителю, когда только начинал изучать HashMap. Поэтому я планирую написать блог, чтобы ответить. Я видел много блогов раньше, но никогда не думал о написании. Сначала попробуйте, пожалуйста, посоветуйте.

Вопрос: почему HashMap вышел из строя? Но в некоторых случаях это кажется упорядоченным?

Ситуация относится к следующим ситуациям:

Если вы добавите данные в HashMap описанным выше способом, вывод определенно будет:

Видя этот вывод, кто-то будет правРасстройство HashMapЕсть сомнение, почему здесь все в порядке?
(Вы также можете изменить порядок добавления данных, например, добавив «2», а затем «1», результат останется прежним)

С этим вопросом мы рассмотрим другой пример:

Давайте подумаем об этомКак вы думаете, что будет выходить? Все еще будет 1 2 3 4 5 6 65536 Это заказ?

Результат: 1 65536 2 3 4 5 6

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

Затем мы возвращаемся и думаем, почему в первом примере упорядоченная ситуация с HashMap?

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

Причина (исходный анализ):

отСтруктура данных иИсходная реализация Два аспекта для объяснения (возьмите JDK 1.8 в качестве примера)

Структура данных:

Структура данных HashMapмассив + Связанный список + Красное черное дерево(Красно-черное дерево добавлено только в JDK 1.8)

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

1. Какие конкретные элементы хранятся в нижней части данных (то есть, каковы маленькие черные точки на рисунке выше)? Из исходного кода (строка 395 класса HashMap) вы можете увидеть поле Node[] table(Т. Е. Массив хеш-памяти),
   Это поле является массивом на картинке выше. Node Тип это маленькая черная точка, NodeПройти между nextПоля, связанные в цепочку
   таблица. Вот конкретный код для типа узла:

1. Каковы преимущества этого способа хранения? Хэш-карта хранится с использованием хэш-таблицы. Для разрешения хэш-конфликтов используется метод цепного адреса (связанные документы: Хэш объяснил). Метод цепного адреса — это просто комбинация массива и связанного списка. Для каждого элемента массива имеется структура связанного списка. Когда данные хэшируются (то есть вызывается метод хеширования в исходном коде, Строка 337 исходного кода) Получить зашифрованное значение хеша, а затем получить индекс массива (вызов Выполните побитовую операцию И в строке 630 исходного кода, чтобы получить индекс массива) И, наконец, поместите данные в связанный список индексов массива.

Например, программа выполняет следующий код:

Система позвонит65536«Этоkey изhashCode() Способ получить егохэш-значение (Этот метод работает для каждого объекта Java), а затем выполните два последних шага алгоритма Hash (Операции высокого порядка и операции по модулю, Описанный ниже), чтобы найти пару ключ-значение, хранящуюся вПоложение в массивеА иногда дваkeyБудет располагаться в массивеТо же местоУказывает, что это произошлоХеш-коллизия (связанный список будет сгенерирован после коллизии), Конечно, чем более равномерно распределены результаты расчетов алгоритма хэширования, тем меньше вероятность коллизий хеш-функции и тем выше эффективность доступа к карте.

Если массив хеш-сегментов большой, то даже плохой алгоритм хеширования будет разбросан. Если массив массивов хеш-сегментов мал, даже хороший хэш-алгоритм будет иметь больше коллизий, поэтому он должен быть связан с космическими и временными затратами. Компромисс состоит в том, чтобы определить массив хэш-блоков в соответствии с реальной ситуацией (Node[] table) Размер и, исходя из этого, хороший алгоритм хеширования предназначен для уменьшения коллизий хешей. Поэтому хороший алгоритм хеширования и механизм расширения имеют решающее значение.

Прежде чем понять процесс хеширования и расширения, мы должны сначала понять несколько полей HashMap。
Из исходного кода конструктора по умолчанию HashMap конструктор должен инициализировать следующие поля:

Прежде всего,Node[] tableДлина инициализацииЗначение по умолчанию 16)，Load factorКоэффициент загрузки (по умолчанию0.75)，thresholdHashMap может держатьМаксимальное количество узлов (пар ключ-значение)。threshold = length * Load factor。
То есть после определения длины массива, чем больше коэффициент загрузки, тем больше пар ключ-значение может быть размещено.

Согласно формуле определения коэффициента нагрузки,thresholdПрямо здесьLoad factorиlength(Длина массива), соответствующий разрешенномуМаксимальное количество элементовЕсли это число превышеноresize(Разверните), емкость HashMap после расширенияВ два раза больше предыдущей емкости, Коэффициент загрузки по умолчанию 0,75 — это сбалансированный выбор эффективности использования пространства и времени, поэтому рекомендуется не изменять его, за исключением особых обстоятельств, таких как время и пространство, таких какБольшой объем памяти и высокие требования к эффективности времени могут уменьшитьКоэффициент загрузкиLoad factorЗначение; вместо этого, еслиОбъем памяти ограничен, а эффективность времени не высока, вы можете увеличитьКоэффициент загрузкиloadFactorЗначение может быть больше 1.

sizeЭто поле на самом деле очень легко понять, то есть количество пар ключ-значение, которые фактически существуют в HashMap. Примечание идлина стола、Содержит максимальное количество порогов ключ-значениеРазница иmodCountПоле в основном используется для записи количества изменений внутренней структуры HashMap. Подчеркните, что изменение внутренней структуры относится к изменению структуры, такой какputНовая пара ключ-значение, но некоторыеkeyсоответствующийvalueПерезаписываемое значение не является структурным изменением.

В HashMap, массив хэш-блоковtableдлинаlengthРазмер должен бытьМощность 2(Это должно быть составное число.) Это нестандартный дизайн. Традиционный дизайн предназначен для расчета размера ствола как простого числа. Условно говоря, вероятность столкновения между простыми числами меньше, чем составные числа.Почему количество блоков в хеш-таблице обычно простое。

Здесь есть проблема: даже если коэффициент загрузки и алгоритм хеширования спроектированы разумно, это неизбежно приведет к ситуации, когда застежка-молния слишком длинная. Поэтому в версии JDK 1.8 структура данных была дополнительно оптимизирована, и было представлено красно-черное дерево. Когда длина связанного списка слишком велика (по умолчанию превышает 8), связанный список преобразуется в красно-черное дерево, а характеристики красно-черного дерева для быстрого добавления, удаления и модификации используются для повышения производительности HashMap.

Реализация функции

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

1. Определить позицию индекса массива хэш-сегментов
   Независимо от добавления, удаления и поиска пар ключ-значение, определение местоположения массива хэш-блоков является критически важным первым шагом. Как упоминалось ранее, структура данных HashMap представляет собой комбинацию массива и связанного списка, поэтому, конечно, мы хотим, чтобы положение элементов в этом HashMap было максимально равномерно распределено. Когда мы используем алгоритм хеширования, чтобы найти эту позицию, мы можем сразу узнать, что соответствующий элемент Нам не нужно перебирать связанный список, что значительно оптимизирует эффективность запроса. HashMap находит позицию индекса массива, которая напрямую определяет дискретную производительность метода хеширования.Сначала посмотрите на реализацию исходного кода (Метод 1 + Метод 2):

Алгоритм хеширования здесь состоит из трех этапов: (1) Возьмите значение ключа hashCode, h = key.hashCode ();
(2) старшие биты участвуют в операции, h ^ (h >>> 16);
(3) Операция по модулю, h & (длина-1).

Для любого данного объекта, пока егоhashCode () возвращаемое значениеТо же самое, тогда программа вызывает метод один для расчетаЗначения хеш-кода всегда одинаковы, Первое, о чем мы подумали, это поставитьОперация модуля хеш-значения на длине массива, Так что элементРаспределение относительно равномерно, Однако потребление операции по модулю все еще относительно велико, что делается в HashMap:Вызовите метод два, чтобы вычислить, по какому индексу массива таблицы должен храниться объект。

Этот метод очень умный, он проходитh & (table.length -1)Чтобы получить бит сохранения этого объекта, а длина базового массива HashMap всегдаМощность 2Это оптимизация скорости HashMap. Когда длина всегда является n-й степенью 2,h& (length-1)Операция эквивалентнаДлина по модулю, Которая составляет h% длины,Но & является более эффективным, чем%.

В реализации JDK1.8 оптимизирован алгоритм работы высокого уровня.XOR или XOR 16 битов hashCode () реализованы: (h = k.hashCode ()) ^ (h >>> 16), В основном на основе скорости, эффективности и качества. Это может быть сделано, когда длина таблицы массива относительно мала.Убедитесь, что, учитывая высокий и низкий бит, участвуют в вычислении хэшаИ в то же время не будет много накладных расходов.

Следующие примеры иллюстрируют,nестьtable[] Длина:

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

Механизм расширения

Когда массив внутри объекта HashMap не может загрузить больше элементов, объект должен увеличить длину массива, чтобы загрузить больше элементов. Конечно, массивы в Java не могут быть автоматически расширены.Метод заключается в замене существующего небольшого массива новым。

Сначала возьмем пример, чтобы интуитивно испытать процесс расширения. Предположим, что наш алгоритм хеширования просто использует ключ mod для определения размера таблицы (то есть длины массива). Размер таблицы массива хэш-блоков равен 2, поэтому ключ равен 3, 7, 5, а порядок размещения — 5, 7 и 3. После мода 2 все конфликтует в таблице [1] здесь. Здесь предполагается, что коэффициент загрузки loadFactor = 1, то есть когда фактический размер пары ключ-значение больше, чем фактический размер таблицы, емкость увеличивается. Следующие три шага — это процесс изменения размера массива корзины хэша до 4, а затем все узлы переэшируются.

Проще говоря, это переназначить больший массив. Ниже мы объясним, какие оптимизации сделал JDK1.8. Наблюдение показывает, что мы используемРасширение до второй степениТаким образом, положение элемента либо вДомашняя позицияИли либо вПереместить исходную позицию во вторую позицию власти, Посмотрите на рисунок ниже, чтобы понять смысл этого предложения.n — длина столаРисунок (а) показываетkey1 и key2 определяют позицию индексаНа рисунке (b) показан пример определения позиции индекса двух ключей, key1 и key2, после раскрытия.hash1 — результат операции хеширования и старшего разряда, соответствующий key1。

После того, как элемент был пересчитан, потому чтоn становится 2 раза, тогда диапазон маски n-1 на 1 бит выше (красный)Итак, новый индекс изменится так:

Поэтому, когда мы расширяем HashMap, нам нужно толькоЭто зависит от того, равен ли новый добавленный бит исходного значения хеш-функции 1 или 0. Если он равен 0, индекс не изменяется. Если он равен 1, индекс становится «исходный индекс + oldCap».Можно увидеть на следующем рисунке схематическое изображение изменения размера от 16 до 32:

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

Наконец, мы должны знать, почему HashMap вышел из строя?

В общем, именно хеш-коллизия вызывает беспорядок.

Источник