Что такое хеш-таблица и как она достигает поиска O(1)?

Question

Accepted Answer

**Хеш-таблица** (hash map) хранит пары **ключ → значение** и обеспечивает вставку, поиск и удаление в среднем за **O(1)**. Она работает, пропуская каждый ключ через **хеш-функцию**, которая отображает его на индекс в базовом массиве ("bucket").

## Как это работает

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## Пример

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## Сложность

| Операция | Среднее | Худший случай |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

**Худший случай** O(n) возникает, когда много ключей сталкиваются в одном bucket.

## Компромиссы

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

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

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

Замена линейного поиска на поиск с хешированием — один из самых распространённых способов превратить алгоритм O(n²) в O(n).