Как хеш-таблицы оптимизируют алгоритмы?

Question

Accepted Answer

**Хеш-таблица** (словарь) обеспечивает **O(1) в среднем** для поиска, вставки и удаления. Обмен памяти O(n) на скорость превращает множество алгоритмов O(n²) в O(n), заменяя повторяющиеся сканирования мгновенным поиском.

## Идея

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

## Пример: two-sum в O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

Без карты это O(n²); с ней — одна итерация.

## Типичные применения

- **Удаление дубликатов / проверка принадлежности** с помощью набора.
- **Подсчёт частот** (`Counter`).
- **Группировка / индексирование** по ключу.
- **Кеширование / мемоизация** результатов.

## Сложность

- **В среднем:** O(1) на операцию. **В худшем случае:** O(n) при большом количестве коллизий. **Память:** O(n).

## Ошибки

Ключи должны быть **хешируемыми** и неизменяемыми. Коллизии в худшем случае снижают производительность. Хеш-таблицы неупорядочены (используйте упорядоченные варианты, если порядок важен).

## Почему это важно

Хеширование — самая частая оптимизация в собеседованиях по кодированию и реальных системах — оно превращает «ищи снова и снова» в «посмотри один раз».

Обмен пространства на время — это постоянный рычаг инженерного решения.

Подсчёт частот, кеширование и индексирование — всё это основано на этой одной идее.