Что хотят услышать интервьюеры:

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

Определение:

Хеш-таблица хранит пары «ключ → значение» и получает доступ к данным через хеш-функцию. Хеш-функция преобразует ключ в числовой индекс, по которому находится нужная ячейка в памяти. Если разные ключи дают один и тот же индекс, возникает коллизия, и структура должна уметь её обрабатывать.

Пример использования:

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

phone_book = {
    "Иван": "+7-900-111-22-33",
    "Анна": "+7-900-444-55-66",
}

# поиск по ключу
print(phone_book["Анна"])  # +7-900-444-55-66

# добавление нового значения
phone_book["Олег"] = "+7-900-777-88-99"

Пояснение кода:

В примере используется dict в Python, а словарь — это реализация хеш-таблицы. При обращении phone_book["Анна"] Python вычисляет хеш ключа "Анна", находит нужную ячейку и возвращает значение. При добавлении phone_book["Олег"] = ... происходит то же самое: ключ хешируется, и пара сохраняется в таблице. Если два ключа попадут в одну и ту же ячейку, Python обработает коллизию внутри реализации словаря.

Ключевые моменты:

Хеш-таблица хранит данные по принципу «ключ → значение».
Основная идея — быстро находить элемент по хешу ключа.
В среднем поиск, вставка и удаление работают за O(1).
Коллизии неизбежны, поэтому нужна стратегия их обработки.
В Python встроенный dict — это хеш-таблица.
Хеш-таблицы особенно полезны для кэшей, индексов и частотных словарей.

Можете объяснить, что такое структура данных хеш-таблица и как она работает?