什么是哈希表，它如何实现 O(1) 查找？

Question

Accepted Answer

**哈希表**（hash map）存储 **key → value** 键值对，提供**平均 O(1)** 的插入、查找和删除操作。它通过对每个 key 运行一个**哈希函数**来工作，该函数将其映射到底层数组中的一个索引位置（一个"桶"）。

## 工作原理

```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) 发生在许多 key 碰撞到同一个桶时。

## 权衡

- **优势：** 极快的 key 访问速度；灵活的 key 类型。
- **劣势：** key 无序；额外的内存占用；最坏情况 O(n)；需要良好的哈希函数。

## 为什么这很重要

哈希表可以说是实践中使用最广泛的数据结构——支撑着字典、集合、缓存、数据库索引和去重。

用哈希查找替换线性扫描是将 O(n²) 算法转化为 O(n) 的最常见方法之一。