Хеш-таблица — одна из важнейших структур. Она хранит пары «ключ → значение» и даёт доступ по ключу в среднем за O(1). Это та самая структура за объектами JavaScript и словарями Python.
Как это работает: специальная хеш-функция превращает ключ в число — адрес ячейки, куда класть значение. Чтобы найти значение, ключ снова прогоняют через хеш-функцию и сразу попадают в нужную ячейку — без перебора.
map = {} map["Аня"] = 25 // запись O(1) map["Аня"] // чтение O(1)
Сравните: искать «Аню» в массиве пар — O(n), а в хеш-таблице — O(1). Поэтому хеш-таблицы используют для подсчётов, кеширования, проверки принадлежности.
Классический приём: за один проход O(n) посчитать частоту элементов через хеш-таблицу — там, где наивный способ дал бы O(n²). Хеш-таблицы — частый ключ к быстрому решению задач на собеседованиях: они меняют O(n²) на O(n).