Как устроен HashMap?

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

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

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

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

Среди методов открытой реализации различают:
• линейное пробирование;
• квадратичное пробирование;
• двойное хэширование.

Недостатки структур с методом открытой адресации:
• Количество элементов в хэш-таблице не может превышать размера массива. По мере увеличения числа элементов и повышения коэффициента заполнения производительность структуры резко падает, поэтому необходимо проводить перехэширование.
• Сложно организовать удаление элемента.
• Первые два метода открытой адресации приводят к проблеме первичной и вторичной группировок.

Преимущества хэш-таблицы с открытой адресацией:
• отсутствие затрат на создание и хранение объектов списка;
• простота организации сериализации/десериализации

Как работает HashMap при попытке сохранить в него два элемента по ключам с одинаковым hashCode(), но для которых equals() == false?

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

Какое начальное количество корзин в HashMap?

В конструкторе по умолчанию - 16, используя конструкторы с параметрами можно задавать произвольное начальное количество корзин.

Возможна ли ситуация, когда HashMap выродится в список даже с ключами имеющими разные hashCode()?

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

Вы когда-нибудь искали подробное введение в Maven, которое было бы веселым и интересным одновременно? Тогда вы его нашли.

В этом видео вы узнаете, как использовать Maven как профессионал: установка, использование Maven вместе с IDE, основы Maven и многое другое.

Предметно-ориентированное проектирование в Enterprise Java (2020) PDF

В книге подробно рассматриваются реализации шаблонов предметно-ориентированного проектирования с применением различных инструментальных средств и рабочих программных сред из Enterprise Java Space. При таком подходе читатель получает завершенную картину и возможность практического применения любого из этих средств в процессе предметно-ориентированного проектирования.
В начальных главах описывается эталонная реализация проекта Cargo Tracker - создание монолитного приложения с использованием платформы Jakarta EE. Затем рассматривается полный процесс преобразования монолитного приложения в архитектуру, основанную на микросервисах. В заключительных главах демонстрируется создание версии приложения с использованием шаблонов CQRS и Event Sourcing (ES); основной рабочей средой является Axon Framework.

👩‍💻 Дзен ищет Java-разработчика в команду инфраструктуры статистики

Компании нужен middle или senior, чтобы строить большой DWH, разрабатывать высоконагруженную систему и улучшать сервисы, отвечающие за работу подписки и ленты каналов. Соответственно, нужны знания Java 17, aka CS 101 и хоть какое-то взаимодействие с популярными NoSQL-решениями.

Немного контекста: команда инфраструктуры статистики создает сервисы, в задачи которых входят обработка и поставка всех клиентских событий и клиентской статистики; инфраструктура подготовки данных для аналитики и А/Б-тестирования.

Откликнуться на вакансию можно здесь.