Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресации и на основе метода цепочек. Как реализована 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-решениями.

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

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

Почему нельзя использовать byte[] в качестве ключа в HashMap?

Хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хэш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняется сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента.

JAVA FROM EPAM (2020)

Пособие предназначено для программистов, начинающих и продолжающих изучение технологий Java SE. В книге рассматриваются основы языка Java и концепции объектно-ориентированного и функционального программирования. Также изложены аспекты применения библиотек классов языка Java, включая файлы, коллекции, Stream API, сетевые и многопоточные приложения, а также взаимодействие с СУБД и ХМL. В конце каждой главы даются теоретические вопросы по изученной главе, тестовые вопросы по материалу главы и задания для выполнения. В приложениях приведены дополнительные материалы с кратким описанием технологий Log4J2 и TestNG.

Какова роль equals() и hashCode() в HashMap?

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