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

Заметки: Теперь самое интересное. Время: Напомню, что О(1) — не моментальное время, а одинаковое всегда. Поиск в массиве с одним элементом и с миллиардом займет одинаковое время. Мы видим, что поиск в таблицах не уступает массивам, а вставка и удаление быстры как в связанных списках. Но в худшем способе все плохо, поэтому важно избегать коллизий (когда много котиков в одной квартире). Коэффициент заполнения вычисляется по формуле: количество элементов в хеш-таблице делим на общее количество элементов (всех котиков делим на количество квартир в доме)...