Career Prep 2027

Appearance

Hash Table ​

一句话理解 ​

Hash Table 的底层通常仍然依赖数组 / bucket 结构，只是先通过 hash(key) 把任意 key 映射为 bucket，再配合冲突处理完成查找。

所以可以把它记成：

Hash Table = 数组 / Bucket + Hash 映射 + 冲突处理

核心目标：将任意 key 快速映射到有限的存储位置。

基本流程 ​

text
key
 ↓
hash(key)
 ↓
bucket index
 ↓
bucket
 ↓
value

理想情况下无需遍历整个集合，因此：

  • 查询：平均 O(1)
  • 插入：平均 O(1)
  • 删除：平均 O(1)

为什么不是永远 O(1) ​

不同 key 可能映射到同一个 bucket。

例如：

text
hash(A) % capacity = 3
hash(B) % capacity = 3

这称为：

Hash Collision

发生碰撞后仍需进一步比较或寻找存储位置，因此 Hash Table 通常只能描述为平均 O(1)。

极端碰撞情况下可能退化。

Collision Handling ​

Separate Chaining ​

同一个 bucket 中组织多个元素：

text
bucket 3
   ↓
[A] -> [B] -> [C]

Open Addressing ​

如果目标位置已占用，则继续寻找其他位置。

Linear Probing ​

text
3 occupied
 ↓
4
 ↓
5

Quadratic Probing ​

使用非线性的探测间隔寻找空槽。

Load Factor 与 Resize ​

随着元素数量增加，如果 bucket 数量不变，碰撞通常会越来越频繁。

常用指标是 Load Factor：

Load Factor=number of stored elementsnumber of buckets

当负载过高时，Hash Table 通常会扩容，并将已有元素重新映射到新的 bucket 空间，这个过程通常称为 Resize / Rehash。

核心链路：

text
元素增多
→ Load Factor 上升
→ Collision 风险上升
→ Resize / Rehash
→ 使用更多空间维持较低的平均查询成本

Resize 本身可能很贵，但不会在每次普通查询或插入时发生，因此 Hash Table 的常规操作仍通常以平均 / 摊销复杂度讨论。

秋招层面理解到这里即可，不需要为了这一知识点深入具体语言的 Hash Table 源码实现。

Direct Address Table vs Hash Table ​

如果 key 是小范围、稠密整数：

text
0 ~ 999

可以直接：

python
checked = [False] * 1000

查询：

python
checked[user_id]

为 O(1)。

这称为：

Direct Addressing

为什么仍然需要 Hash Table ​

如果 key：

text
3
81729372
2000000000

直接按 key 建数组会产生巨大的空间浪费。

Hash 可以将巨大、稀疏 key 空间压缩到有限 bucket 空间。

同时 key 还可能是：

  • string
  • tuple
  • user_id
  • URL
  • filename
  • object

Hash Function 可以将这些 key 转换成数组可使用的 bucket。

Trade-off ​

Hash Table 本质上是在做：

Space-Time Trade-off

使用额外存储空间，换取平均 O(1) 查询。

数据结构选择 ​

text
判断元素是否存在
│
├── 数据量很小
│   └── List
│
├── 小范围稠密整数 Key
│   └── Direct Address Array / Bitmap
│
├── 巨大稀疏 / 复杂 Key 空间
│   └── Hash Table
│
└── 需要有序 / 范围查询
    └── Tree

Python list vs set ​

频繁判断：

python
x in collection

List ​

查询：

O(n)

空间：

O(n)

Set ​

平均查询：

O(1)

空间：

O(n)

但 Hash Table 通常存在更大的常数空间开销。

Two Sum Pattern ​

Problem:

python
nums = [3, 1, 4, 7]
target = 8

核心思想：遍历当前数字 x，计算：

complement=target−x

然后查询：

python
complement in seen

如果存在，则找到答案；否则记录：

python
seen[x] = index

伪代码：

python
seen = {}

for i, x in enumerate(nums):
    complement = target - x

    if complement in seen:
        return [seen[complement], i]

    seen[x] = i

复杂度：

  • 遍历：O(n)
  • 每次 Hash 查询：平均 O(1)
  • 总时间：平均 O(n)
  • 额外空间：O(n)

核心模式：

利用 Hash Table 把原本 O(n) 的重复历史查询变成平均 O(1)。

高频理解点 ​

  • 为什么平均查询 O(1)：Hash Function 将 key 定位到有限 bucket，避免扫描整个集合；
  • 为什么不是永远 O(1)：Collision 会增加进一步查找成本；
  • 为什么不用数组直接寻址：巨大、稀疏或非整数 key 会造成空间浪费或无法直接作为下标；
  • 什么时候反而用数组：小范围、稠密整数 key；
  • 为什么需要 Resize：控制过高 Load Factor 和碰撞率。

Practice:

04_Practice/CS_MCQs/Data_Structure_Lesson_1.md

Related:

01_Common_CS/Data_Structure/05_set-map.md

Mistakes:

05_Mistakes/CS.md

Interview QA:

06_Interview/CS_QA/Data_Structure.md