哈希表如何优化算法？

Question

哈希表如何优化算法？

IT Interview Practice · Accepted Answer

一个**hash map**（字典）提供**O(1) 平均**的查找、插入和删除。用 O(n) 的内存换取速度，将许多 O(n²) 的算法转变为 O(n)，用即时查找替代重复扫描。

## 核心思想

不是每次都在列表中搜索，而是将已见的值存储在 hash map 中，以常数时间检查成员资格。

## 示例：O(n) 的 two-sum

```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)
```

没有 map 时是 O(n²)；有了它，一次遍历。

## 常见用途

- **去重 / 成员检查**（使用集合）。
- **频率计数**（`Counter`）。
- **按键分组 / 索引**。
- **结果缓存 / 记忆化**。

## 复杂度

- **平均：** O(1) 每次操作。**最坏：** 哈希碰撞严重时 O(n)。**空间：** O(n)。

## 常见陷阱

键必须**可哈希**且不可变。最坏情况的碰撞会降低性能。哈希表是无序的（如果顺序很重要，使用有序的变体）。

## 为什么这很重要

哈希是编码面试和实际系统中最常见的优化——它将

核心思想

示例：O(n) 的 two-sum

相关问题

常见用途

复杂度

常见陷阱

为什么这很重要