Explique ce qu'est une structure de données de table de hachage et comment elle fonctionne.

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

Принцип работы:

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

Если два ключа дают одинаковый индекс (коллизия), используется метод разрешения коллизий, например, цепочки (связанные списки) или открытая адресация.

Это позволяет выполнять операции вставки, поиска и удаления в среднем за время O(1).