#вопросы_с_собеседований Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресации и на основе метода цепочек. Как реализована HashMap? Почему, по вашему мнению, была выбрана именно эта реализация? В чем плюсы и минусы каждого подхода? HashMap реализован с использованием метода цепочек, т.е. каждой ячейке массива (корзине) соответствует свой связный список и при возникновении коллизии осуществляется добавление нового элемента в этот список. Для метода цепочек коэффициент заполнения может быть больше 1 и с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов, либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения. Среди методов открытой реализации различают: • линейное пробирование; • квадратичное пробирование; • двойное хэширование. Недостатки структур с методом открытой адресации: • Количество элементов в хэш-таблице не может превышать размера массива. По мере увеличения числа элементов и повышения коэффициента заполнения производительность структуры резко падает, поэтому необходимо проводить перехэширование. • Сложно организовать удаление элемента. • Первые два метода открытой адресации приводят к проблеме первичной и вторичной группировок. Преимущества хэш-таблицы с открытой адресацией: • отсутствие затрат на создание и хранение объектов списка; • простота организации сериализации/десериализации