Что такое хеш-таблица и как она связана с Map? Что такое коллизия в контексте хеш-таблиц?

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

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

Коллизия — ситуация, когда разные ключи после применения хеш-функции дают одинаковый индекс. Это неизбежно из-за ограниченного размера массива. Для разрешения коллизий применяются разные методы, например:

• цепочки (chaining): в одной ячейке хранится список всех элементов с этим индексом;
• открытая адресация (open addressing): поиск следующей свободной ячейки.

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