коллизия hashmap что такое
Подробный разбор класса 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, и тогда дерево обратно перестроится в связный список. Если Вы не разработчик с многолетнем стажем, знать об этом и понимать это совсем не обязательно (да и просто не нужно).
Коллизия hashmap что такое
Всем привет. Меня зовут Александр. Я снимаю видео ролики посвященные прохождению собеседования на позицию java developera. Напомню что сейчас я разбираю коллекции в java. Сегодняшняя тема будет HashMap. Почему я выбрал эту тему? Да все по той же причине. Ее нужно знать обязательно если вы пришли на собеседование. Не знаете = не готовы!
Чтобы было проще понять что это такое можно представлять HashMap как пронумерованные корзинки в которых хранятся какие-то данные. При добавлении нового объекта в HashMap мы также передаем помимо самого объекта еще и ключ по которому в дальнейшем его можно будет отыскать. Как по ключу можно определить положение искомого объекта? Для этого нам нужно знать hashCode ключа. Где же его взять? Да это очень просто если понимать что в качестве ключа может выступать любой объект в java. Все знают что класс Object реализует метод hashCode() это означает что он будет унаследован или переопределен самим “ключом”. Т.к. все в java наследуются от класса Object. Теперь понятно откуда у ключа берется hashCode!
После того как в hashMap, был передан ключ + сохраняемый объект специальная hash функция вычисляет то в какую корзину отнести наши данные.
Как вы понимаете никаких корзинок в HashMap-е нет. Вместо их есть массив. который хранит ссылки на связанные списки в которых хранятся наши данные. Каждому элементу массива соответствует один список.
Какое начальное количество корзин в HashMap?
Данный вопрос мне ни разу не задавали я его нашел на хабре. Ответ 16. Но как и с ArrayList-ом в конструкторе можно задать другое количество.
Что такое коллизия? Способ решения коллизий.
Этот вопрос так же часто встречается. Коллизия это когда два разных объекта попадают в одну корзинку(связанный список). Причиной этому служат то что они имеют одинаковый hashcode. Для более эффективной работы с HashMap hashcode не должен повторяться для не эквивалентных объектов.
Как я уже упомянул выше, все данные хранятся в списках. Почему так? Почему не хранить всего один объект? Ответ прост. Все потому что это способ разрешения коллизий. Как происходит добавление? Первое это мы выясняем то какая корзина соответствует ключу объекта. Затем проверяем есть ли в ней уже какие-то объекты если нет то добавляем текущий. Если да то это случилась коллизия. Тогда мы начинаем сравнивать ключи текущего объекта и тех которые внутри (если конечно их там несколько). Сравнение производится методом equals. Если equals возвращает true значит ключи совпадают, производится замена, новый объект заменяет тот который уже там находится под тем же ключом, если нет новый объект добавляется в конец списка.
Как и когда происходит увеличение количества корзин в HashMap?
У HashMap имеет поле loadFactory. Оно может быть задано через конструктор. По умолчанию равняется 0.75. Для чего оно нужно? Его произведение на количество корзин дает нам необходимое число объектов которое нужно добавить чтобы состоялось удвоение количества корзин.. Например если у нас мапка с 16-ю корзинами, а loadFactory равняется 0.75, то расширение произойдет когда мы добавим 16 * 0.75 = 12 объектов. Мапка увеличивается вдвое.
Какая оценка временной сложности операций с HashMap? Гарантирует ли 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
Почему я выбрал эту тему? Ее нужно знать обязательно если Вы пришли на собеседование. Не знаете = не готовы!
Ниже я перечислил наиболее популярные вопросы по этой теме. Для тех кому лень читать – можно посмотреть видос.
Расскажите про устройство HashMap?
Во-первых что такое HashMap? HashMap – это ассоциативный массив. Если вкратце, то ассоциативный массив – это структура данных, которая хранит пары ключ-значения.
Чтобы было проще понять что это такое, можно представлять HashMap как пронумерованные корзинки, в которых хранятся какие-то данные. При добавлении нового объекта в HashMap, мы помимо самого объекта передаем еще и ключ, по которому в дальнейшем, его можно будет отыскать.
Как по ключу можно определить положение искомого объекта? Для этого нам нужно знать hashCode ключа. Где же его взять? Все очень просто, если понимать, что в качестве ключа, может выступать любой объект в java. Все знают что класс Object реализует метод hashCode(), это означает что он будет унаследован или переопределен самим “ключом”. Т.к. все в java наследуются от класса Object. Теперь понятно откуда у ключа берется hashCode!
После того как в hashMap, был передан ключ + сохраняемый объект, специальная hash-функция вычисляет то в какую корзину отнести наши данные.
Как вы понимаете, никаких корзинок в HashMap-е нет. Вместо них есть массив, который хранит ссылки на связанные списки в которых хранятся наши данные. Каждому элементу массива соответствует один список.
Какое начальное количество корзин в HashMap?
Данный вопрос мне ни разу не задавали я его нашел на хабре. Ответ – 16. Но как и с ArrayList-ом в конструкторе можно задать другое количество.
Что такое коллизия? Способ решения коллизий.
Этот вопрос так же часто встречается. Коллизия это когда два разных объекта попадают в одну корзинку(связанный список). Причиной этому служит то, что они имеют одинаковый hashcode. Для более эффективной работы с HashMap, hashcode не должен повторяться для не эквивалентных объектов.
Как я уже упомянул выше, все данные хранятся в списках. Почему так? Почему не хранить всего один объект? Ответ прост. Все потому, что это способ разрешения коллизий. Как происходит добавление? Смотр код 1
Первое – мы выясняем то какая корзина соответствует ключу объекта. Затем проверяем, есть ли в ней уже какие-то объекты, если нет – то добавляем текущий. Если да, то это случилась коллизия.
Тогда мы начинаем сравнивать ключ и hashcode текущего объекта и тех которые внутри (если конечно их там несколько).
Сначала проверяем равны ли hashcode ключей.
Если да, то сравниваем их ключ методом equals.
Если equals возвращает true, значит ключи совпадают по “значению” и hashcode – производится замена, новый объект заменяет тот который уже там находится под тем же ключом,
Если hashcode и “значение” ключа неравны – новый объект добавляется в конец списка.
Как и когда происходит увеличение количества корзин в HashMap?
HashMap имеет поле loadFactor. Оно может быть задано через конструктор. По умолчанию равняется 0.75. Для чего оно нужно? Его произведение на количество корзин дает нам необходимое число объектов, которое нужно добавить, чтобы состоялось удвоение количества корзин. Например, если у нас мапка с 16-ю корзинами, а loadFactor равняется 0.75, то расширение произойдет когда мы добавим 16 * 0.75 = 12 объектов. Мапка увеличивается вдвое.
Какая оценка временной сложности операций с HashMap? Гарантирует ли HashMap указанную сложность выборки элемента?
Рассмотрим сначала случай в котором нет коллизий. В этом случае добавление, удаление и поиск объектов по ключу выполняется за константное время O(1). Разумеется, не учитывается случай с расширением количества элементов. Вообще говоря, когда Вы работаете с HashMap, лучше сразу указать в конструкторе, сколько корзин нужно для работы и хорошо если оно равняется числу уникальных объектов с которыми Вы будите работать. В таком случае не придется тратить время и ресурсы на создание нового HashMap с удвоенным количеством bucket-ов. Почему такая хорошая производительность? Тут все просто. Повторюсь что коллизий нет – в таком случае нет никакой зависимости от других элементов из этой мапки. Удаление, Вставка, Поиск выполняются примерно по одной схеме. Берется HashCode ключа, вычисляется корзинка, и производится удаление, вставка или поиск. Все! Нигде не встречаются другие объекты. Но это лишь в том случае, если нет коллизий.
Теперь поговорим о случае когда коллизии все-таки присутствуют. Теоретически работая с HashMap в котором могут присутствовать коллизии, мы получаем временную сложность O(log(n)) на операции вставки, сохранения и удаления. В самом худшем случае, когда все объекты возвращают один и тот же HashCode, а значит попадают в одну корзину. На самом деле это связный список и тогда временная сложность как у LinkedList O(n).
Вопросы на собеседовании 2. HashMap.
Предположим, что в мапку, созданную данным способом (Код 1), нужно добавить 1 миллион объектов. Что тут плохого? Давайте подумаем.
Как обычно, видос для ленивых:
Что произойдет, когда выполнится данный код? Создастся массив на 16 элементов с loadFactor = 0.75. Получаем, что после добавления 12 элементов произойдет удвоение длинны массива. Напомню, что это число получается перемножив loadFactor и текущее количество корзинок или длину массива.
Как-бы, что тут плохого, ну удвоилось количество корзинок, можно добавлять дальше. Нет! Все работает не так. После того как состоялось удвоение, все элементы, которые уже были добавлены, будут перераспределены по корзинкам заново с учетом их нового количества.
Добавили 12. Потом эти 12 снова добавили, после увеличения массива. Грубо говоря добавили всего 24. Что получаем? В следующий раз, удвоение числа корзинок произойдет после добавления 24-го элемента, а в мапке уже 12.
Добавили еще 12 + снова перераспределение и еще 24, получаем 36.
Представляете сколько нужно будет выполнить работы, пока мы не закончим добавлять все 1 миллион объектов.
Когда я обдумывал данный пример, предполагал, что коллизий нет совсем. Боюсь представить, что было бы, если бы они все таки присутствовали.
В каком случае может быть потерян элемент в HashMap?
После добавления элемента в HashMap, у объекта, который выступает в качестве ключа, изменяют одно поле, которое участвует в вычислении хеш-кода. В результате, при попытке найти данный элемент по исходному ключу, будет происходить обращение к правильной корзине, а вот equals (ведь equals и hashCode должны работать с одним и тем же набором полей) уже не найдет указанный ключ в списке элементов. Тем не менее, даже если equals реализован таким образом, что изменение данного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хеш-кодов элементов, указанный элемент, с измененным значением поля, с большой долей вероятности попадет совсем в другую корзину и тогда он уже совсем потеряется.
Related Posts
Шаг 1 Первым делом Вы должны установить себе git на компьютер. Посмотрите для этого небольшое…
В этой статье я попробую простым языком и кратко рассказать, что такое класс в общем…
В этой статье я поговорю частично о технологиях без которых, никуда Вас не возьмут и…
На этот раз я расскажу о состоянии дел связанных с высшим образованием при устройстве на…
Структуры данных в картинках. 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).