Какая структура данных в API коллекций обеспечивает доступ к элементам за постоянное время?

В Java API коллекций структура данных, обеспечивающая доступ к элементам за постоянное время (O(1) в среднем), — это HashMap (для пар ключ-значение) и HashSet (для уникальных элементов).

Они основаны на хеш-таблицах, где для доступа к элементу используется хеш-функция, позволяющая быстро определить индекс в массиве. Благодаря этому операции вставки, удаления и поиска выполняются очень быстро в среднем случае.

Важно помнить, что в худшем случае (при большом количестве коллизий) время может деградировать до O(n), но в хорошо реализованных и правильно используемых хеш-таблицах это случается редко.