Что такое коллизия в java
Внутренняя работа 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).
Что такое коллизия в java
Всем привет. Меня зовут Александр. Я снимаю видео ролики посвященные прохождению собеседования на позицию 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 указанную сложность выборки элемента?
Часть первая ответника, Java
Первым блоком идут вопросы о языке программирования Java.
1. Модификаторы доступа Java (в порядке от private до public):
private — ограничивает видимость данных и методов пределами одного класса.
protected — Поля и методы, обозначенные модификатором доступа protected, будут видны в пределах всех классов, находящихся в том же пакете, что и наш и в пределах всех классов-наследников нашего класса.
public — Не накладывает никаких ограничений на доступ; предназначаются для конечного пользователя.
2. Реализация «кучи» (где хранятся объекты):
Эта область памяти используется для объектов и классов. Новые объекты всегда создаются в куче, а ссылки на них хранятся в стеке. Эти объекты имеют глобальный доступ и могут быть получены из любого места программы.
Эта область памяти разбита на несколько более мелких частей, называемых поколениями:
Young Generation — область где размещаются недавно созданные объекты. Когда она заполняется, происходит быстрая сборка мусора.
Old (Tenured) Generation — здесь хранятся долгоживущие объекты. Когда объекты из Young Generation достигают определенного порога “возраста”, они перемещаются в Old Generation.
Permanent Generation — эта область содержит метаинформацию о классах и методах приложения, но начиная с Java 8 данная область памяти была упразднена.
Помимо рассмотренных ранее, куча имеет следующие ключевые особенности:Когда эта область памяти полностью заполняется, Java бросает java.lang.OutOfMemoryError Доступ к ней медленнее, чем к стеку. Эта память, в отличие от стека, автоматически не освобождается. Для сбора неиспользуемых объектов используется сборщик мусора. В отличие от стека, куча не является потокобезопасной и ее необходимо контролировать, правильно синхронизируя код.
3. Где и как используются методы equals() и hashcode():
Метод equals() являются ли два объекта одного происхождения логически равными. Создатель класса сам определяет характеристики, по которым проверяется равенство объектов этого класса.
Объекты должны быть экземплярами одного класса и не должны быть null. Переопределяя метод equals(), обязательно соблюдение этих требований:
Рефлексивность: Любой объект должен быть equals() самому себе.
Симметричность: Если a.equals(b) == true, то и b.equals(a) должно возвращать true.
Транзитивность: Если два объекта равны какому-то третьему объекту, значит, они должны быть равны друг и другу. Если a.equals(b) == true и a.equals(c) == true, значит проверка b.equals(c) тоже должна возвращать true.
Постоянность: Результаты работы equals() должны меняться только при изменении входящих в него полей. Если данные двух объектов не менялись, результаты проверки на equals() должны быть всегда одинаковыми.
Сравнение с null для любого объекта a.equals(null) должно возвращать false.
Метод hashCode() возвращает для любого объекта 32-битное число типа int. Если два объекта равны (т.е. метод equals() возвращает true), у них должен быть одинаковый хэш-код. Проверка по hashCode() должна идти первой для повышения быстродействия. Если метод hashCode() вызывается несколько раз на одном и том же объекте, каждый раз он должен возвращать одно и то же число. Одинаковый хэш-код может быть у двух разных объектов. Методы equals и hashCode необходимо переопределять вместе.
4. Что будет, если не переопределить метод hashcode():
Тогда с точки зрения метода equals два объекта будут логически равны, в то время как с точки зрения метода hashCode они не будут иметь ничего общего.
5. Реализация HashMap:
HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Сначала ключ проверяется на равенство с null. Если это проверка вернула true, будет вызван метод putForNullKey(value). Далее генерируется хэш на основе ключа. Для генерации используется метод hash(hashCode), в который передается key.hashCode(). С помощью метода indexFor(hash, tableLength), определяется позиция в массиве, куда будет помещен элемент. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Хэш и ключ нового элемента поочередно сравниваются с хэшами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается. Если же предыдущий шаг не выявил совпадений, будет вызван метод addEntry(hash, key, value, index) для добавления нового элемента.
6. Как разрешается коллизия в HashMap (метод цепочек или открытая адресация):
Разрешение коллизий при помощи цепочек. Каждая ячейка массива H является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.
7. Виды исключений в Java:
Unchecked(Error, RunTimeException); Checked(Exception)
8. Виды коллекций Java (перечисляете всё, что знаете):
List, Set, Queue, Deque, Map.
9. Типы ссылок Java и где используются, в порядке убывания жёсткости:
Сильные, они же обычные, нужны для указания на объекты, которые должны обязательно оставаться в памяти всё то время, что эти ссылки на него существуют. Если не складывается, получите OutOfMemoryError.
Мягкие ссылки полезны для кэшей, чувствительных к доступному объёму оперативной памяти. Объекты по ним могут зачиститься, но только в случае необходимости. Например, если нужно насоздавать ещё объектов с сильными ссылками, а уже негде, лучше освободить кэш и замедлить работу, чем уронить процесс напрочь.
Слабые ссылки полезны для сопоставления объектов чему-нибудь без удерживания их от зачистки когда они больше не нужны (а-ля Map >). На возможность зачистки они не влияют вообще никак, слабые ссылки будут очищены при очередном запуске сборщика.
Фантомные ссылки возникают, когда объект уже признан мусором, финализирован и находится в процессе зачистки, о чём можно узнать с помощью класса Cleaner и выполнить в это время какие-то собственные действия.
10. Способы синхронизации Java:
Синхронизация относится к многопоточности. Синхронизированый блок кода может быть выполнен только одним потоком одновременно. Синхронизация достигается в Java использованием зарезервированного слова synchronized. Вы можете использовать его в своих классах, определяя синхронизированные методы или блоки. Вы не сможете использовать synchronized в переменных или атрибутах в определении класса.
Блокировка на уровне объекта-это механизм, когда требуется синхронизировать нестатический метод или нестатический блок кода таким образом, чтобы только один поток мог выполнить блок кода на данном экземпляре класса. Это всегда должно быть сделано, чтобы сделать потокобезопасными данные уровня экземпляра.
Блокировка уровня класса предотвращает ввод нескольких потоков в синхронизированный блок в любом из всех доступных экземпляров во время выполнения. Это означает, что если во время выполнения есть 100 экземпляров DemoClass, то только один поток сможет выполнить demoMethod() в любом из экземпляров одновременно, а все остальные экземпляры будут заблокированы для других потоков.
11. Volatile — что это:
Запрещает помещать значение переменной в кэш. Ключевое слово volatile указывается для поля для того, чтобы указать компилятору, что все операции присвоения этой переменной и все операции чтения из неё должны быть атомарными. Более того, присвоение значения этой переменной имеет связь happens-before (произошло-до) для последующих чтений из этой переменной для любых потоков, то есть после присвоения нового значения переменной все потоки увидят это новое значение.
Дело в том, что Java позволяет потокам в целях производительности сохранять локальные копии переменной для каждого потока, который её использует (например в кешах или регистрах процессора). В таком случае после записи другим потоком нового значения в исходную переменную, первый поток будет видеть свою локальную копию со старым значением.
Использование ключевого слова volatile гарантирует, что все потоки всегда будут использовать общее, исходное значение, и они будут видеть изменения этого исходного значения другими потоками сразу же. Аналогично все изменения переменных, произошедшие внутри sychronized-методов и synchronized-блоков, а также блоков с другими блокировками вроде реализаций интерфейса java.util.concurrent.locks.Lock после выхода из блокировки будут гарантировано видны любым другим потокам после взятия блокировки над тем же самым объектом, но если более сложные блокировки не нужны, то можно использовать volatile.
12. StringBuilder vs String:
Благодаря неизменности, хэшкод экземпляра класса String кэшируется. Его не нужно вычислять каждый раз, потому что значения полей объекта никогда не изменятся после его создания. Это дает высокую производительность при использовании данного класса в качестве ключа для HashMap.
StringBuilder — изменяемый класс, поэтому при работе с ним не возникает такого же количества мусора в памяти, как со String. Поэтому если над строками проводится много модификаций, лучше использовать StringBuilder.
13. Назовите синхронизированную версию HashMap (Hashtable, но устарела):
SynchronizedMap и ConcurrentHashMap.
Методы SynchronizedMap удерживают блокировку на объекте, в то время как ConcurrentHashMap есть понятие «чередование блокировок», когда вместо блокировок удерживаются блоки содержимого. Таким образом улучшается масштабируемость и производительность.
14. Реализация ArrayList в Java (на базе массива):
Класс ArrayList реализует интерфейс List и может менять свой размер во время исполнения программы, при этом не обязательно указывать размерность при создании объекта. Элементы ArrayList могут быть абсолютно любых типов в том числе и null. Внутри у него находится массив, в котором и хранятся элементы. УArrayListʼa есть специальный механизм по работе с ним: Когда этот внутренний массив заполняется, ArrayList создает внутри себя новый массив. Его размер = (размер старого массива * 1,5) +1. Все данные копируются из старого массива в новый Старый массив удаляется сборщиком мусора.
15. Модификатор final в Java — где используется и что даёт:
Применяться к классам, методам, переменным (в том числе аргументам методов) Для класса это означает, что класс не сможет иметь подклассов, т.е. запрещено наследование. Для метода final означает, что он не может быть переопределен в подклассах. Для переменных примитивного типа это означает, что однажды присвоенное значение не может быть изменено. Для ссылочных переменных это означает, что после присвоения объекта, нельзя изменить ссылку на данный объект. Ссылку изменить нельзя, но состояние объекта изменять можно.
Кроме того, хотелось бы добавить вопрос из своего опыта:
Какие методы имеются у класса Object?
public String toString() — Возвращает строковое представление объекта.
public native int hashCode() и public boolean equals(Object obj) — Пара методов, которые используются для сравнения объектов.
public final native Class getClass() — Возвращает специальный объект, который описывает текущий класс.
public final native void notify(),
public final native void notifyAll(),
public final native void wait(long timeout),
public final void wait(long timeout, intnanos),
public final void wait() — Методы для контроля доступа к объекту из различных нитей. Управление синхронизацией нитей.
protected void finalize() — Метод позволяет «освободить» родные не-Java ресурсы: закрыть файлы, потоки и т.д.
protected native Object clone() — Метод позволяет клонировать объект: создает дубликат объекта.
Все ответы собраны из следующих источников:
Подробный разбор класса 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, и тогда дерево обратно перестроится в связный список. Если Вы не разработчик с многолетнем стажем, знать об этом и понимать это совсем не обязательно (да и просто не нужно).