哈希表
一、什么是哈希表
哈希表是一种键值对（key-value）存储结构：给定键 key，可以快速找到对应的值 value（或判断 key 是否存在）。理想情况下，通过哈希函数把 key 映射到数组的某个桶（bucket）下标，直接按下标访问，因此查找、插入、删除的平均复杂度为 O(1)。
与数组按「下标」访问不同，哈希表按「键」访问：键可以是整数、字符串或其它可哈希类型，键的取值空间往往很大，而桶的个数有限，所以多个键可能映射到同一桶，产生冲突（collision），需要冲突处理策略。
二、哈希函数
哈希函数（hash function）把任意键映射到一个固定范围的整数（通常再对桶数取模得到下标）。好的哈希函数应满足：
- 确定性：相同 key 一定得到相同结果，否则无法正确查找。
- 均匀性：不同 key 尽可能均匀分布到各桶，减少冲突、避免某些桶过长。
- 计算快：单次计算应为 O(1) 或 O(key 长度)。
常见做法：整数可直接取模 key % n（n 为桶数）；字符串常用「加权求和再取模」或现成算法（如 Python 的 hash()）。键的类型必须不可变且可比较相等（Python 中需实现 __hash__ 与 __eq__），这样才适合做哈希表的键。
三、冲突处理
当两个不同的 key 映射到同一桶时发生冲突。常用两种策略：
3.1 链地址法（拉链法）
每个桶维护一条链表（或其它顺序结构），所有映射到该桶的键值对都挂在这条链上。查找时先定位桶，再在链上按 key 比较。插入：在对应桶的链上插入或覆盖。删除：在链上删除对应节点。若哈希函数均匀、负载因子不太大，每条链长度可视为常数，单次操作平均 O(1)。
3.2 开放定址法
桶数组只存键值对，不挂链表。发生冲突时，按某种规则找「下一个」空位，例如线性探测：若位置 i 被占，则尝试 i+1、i+2……直到找到空位或找到 key。查找时同样按该规则顺延。删除通常用「惰性删除」（标记为已删）或后续 rehash，否则会破坏探测链。负载因子较高时性能下降，需要扩容 rehash。
Python 的 dict 在 CPython 中采用开放定址（类似线性探测的变体）；很多教科书和面试实现采用链地址法，便于理解。
四、负载因子与扩容
负载因子（load factor）α = 已存键值对数 / 桶数。α 越大，冲突越多，查找越慢。通常设定阈值（如 0.75）：当 α 超过阈值时扩容（rehash）：申请更大的桶数组，把原有键值对重新哈希到新桶中。扩容后 α 降低，平均性能恢复。均摊下来，插入仍可视为 O(1)。
五、Python 中的 dict 与 set
Python 内置的 dict（字典）即哈希表：键唯一，支持 d[key]、d.get(key)、d[key]=val、del d[key]、key in d。set（集合）是「只有键没有值」的哈希表，用于去重、判存在。两者都要求键不可变（如 int、str、tuple 不可变元素）；list、dict 不能作为键。
下面用链地址法手写一个简易哈希表（只存整数 key→value），帮助理解「桶 + 链表」：
from typing import List, Optional, Tuple
class SimpleHashTable:
"""链地址法：桶数组 + 每桶存 (key, value) 列表；
负载因子超阈值时扩容 rehash。"""
LOAD_FACTOR: float = 0.75 # 负载因子阈值，超过则扩容
def __init__(self, capacity: int = 16) -> None:
self.cap: int = capacity
self.buckets: List[List[Tuple[int, int]]] = [[] for _ in range(capacity)] # 每桶一条链（用 list 表示）
self._n: int = 0 # 当前键值对个数，用于 O(1) 的 len 与负载因子
def _index(self, key: int) -> int:
"""由 key 取模得到桶下标。"""
return key % self.cap
def _load_factor(self) -> float:
"""负载因子 = 键值对数 / 桶数。"""
return self._n / self.cap if self.cap > 0 else 0.0
def _rehash(self) -> None:
"""扩容：桶数翻倍（至少 16），把旧桶中所有 (k,v)
按新 cap 重新散列到新桶。"""
old_buckets: List[List[Tuple[int, int]]] = self.buckets
self.cap = max(16, self.cap * 2)
self.buckets = [[] for _ in range(self.cap)]
for chain in old_buckets:
for k, v in chain:
i: int = self._index(k)
self.buckets[i].append((k, v))
def get(self, key: int) -> Optional[int]:
"""查找：先定位桶，再在桶内链上顺序找 key，
找到返回 value，否则 None。"""
i: int = self._index(key)
for k, v in self.buckets[i]:
if k == key:
return v
return None
def put(self, key: int, value: int) -> None:
"""插入或更新：桶内已有 key 则覆盖；否则在桶链末尾追加。
插入后若负载因子超阈值则 rehash。"""
i: int = self._index(key)
for j, (k, v) in enumerate(self.buckets[i]):
if k == key:
self.buckets[i][j] = (key, value)
return
self.buckets[i].append((key, value))
self._n += 1
if self._load_factor() > self.LOAD_FACTOR:
self._rehash()
def remove(self, key: int) -> None:
"""删除：在桶内链上找到 key 并移除；不存在则 KeyError。"""
i: int = self._index(key)
for j, (k, v) in enumerate(self.buckets[i]):
if k == key:
self.buckets[i].pop(j)
self._n -= 1
return
raise KeyError(key)
def __contains__(self, key: int) -> bool:
"""支持 key in table。"""
return self.get(key) is not None
def __len__(self) -> int:
"""当前键值对个数。"""
return self._n
def clear(self) -> None:
"""清空所有桶链并置 _n 为 0。"""
for i in range(self.cap):
self.buckets[i].clear()
self._n = 0负载因子与扩容：_load_factor() 返回 _n / cap。put 在插入新键后若负载因子超过 LOAD_FACTOR（默认 0.75），则调用 _rehash()：新桶数为原来的 2 倍（至少 16），将旧桶中所有键值对按新桶数重新 _index 放入新桶，从而降低负载因子、减少冲突。
下面用开放定址法（线性探测）再实现一版，支持同样操作；删除时用惰性删除（标记为已删，查找时跳过），扩容 rehash 时再清理。
from typing import List, Optional, Tuple, Any
# 惰性删除占位：删除时只把槽置为此标记，查找时跳过，rehash 时自然清理
_DELETED: Any = object()
class OpenAddressingHashTable:
"""开放定址（线性探测）：单数组存槽位，
None=空、_DELETED=已删、(k,v)=占用；负载因子超阈值则 rehash。"""
LOAD_FACTOR: float = 0.75
def __init__(self, capacity: int = 16) -> None:
self.cap: int = capacity
self.slots: List[Optional[Tuple[int, int]]] = [None] * capacity # 每槽 None / _DELETED / (key, value)
self._n: int = 0
def _index(self, key: int) -> int:
"""由 key 取模得到起始探测下标。"""
return key % self.cap
def _load_factor(self) -> float:
"""负载因子 = 键值对数 / 槽数。"""
return self._n / self.cap if self.cap > 0 else 0.0
def _probe_find(self, key: int) -> int:
"""线性探测查找 key：从 _index(key) 起顺延，
遇 key 返回下标，遇 None 返回 -1，_DELETED 继续。"""
i: int = self._index(key)
for _ in range(self.cap):
cell: Optional[Tuple[int, int]] = self.slots[i]
if cell is None:
return -1
if cell is not _DELETED and cell[0] == key:
return i
i = (i + 1) % self.cap
return -1
def _probe_slot(self, key: int) -> int:
"""为 put 找写入位置：若已有同 key 返回其下标（更新）；
否则返回第一个可写槽（优先复用 _DELETED，再 None）；表满返回 -1。"""
i: int = self._index(key)
first_deleted: int = -1
for _ in range(self.cap):
cell = self.slots[i]
if cell is None:
return first_deleted if first_deleted >= 0 else i
if cell is _DELETED and first_deleted < 0:
first_deleted = i
elif cell is not _DELETED and cell[0] == key:
return i
i = (i + 1) % self.cap
return first_deleted if first_deleted >= 0 else -1
def _rehash(self) -> None:
"""扩容：槽数翻倍（至少 16），仅把当前有效键值对
重新 put 进新表，_DELETED 自然被丢弃。"""
old_slots: List[Optional[Tuple[int, int]]] = self.slots
old_cap: int = self.cap
self.cap = max(16, self.cap * 2)
self.slots = [None] * self.cap
self._n = 0
for i in range(old_cap):
cell = old_slots[i]
if cell is not None and cell is not _DELETED:
self.put(cell[0], cell[1])
def get(self, key: int) -> Optional[int]:
"""查找：线性探测找到 key 则返回 value，否则 None。"""
pos: int = self._probe_find(key)
if pos < 0:
return None
return self.slots[pos][1]
def put(self, key: int, value: int) -> None:
"""插入或更新：_probe_slot 找位置；表满则先 rehash 再递归 put；
同 key 则覆盖，否则写入并检查负载因子。"""
pos: int = self._probe_slot(key)
if pos < 0:
self._rehash()
self.put(key, value)
return
if self.slots[pos] is not None and self.slots[pos] is not _DELETED and self.slots[pos][0] == key:
self.slots[pos] = (key, value)
return
self.slots[pos] = (key, value)
self._n += 1
if self._load_factor() > self.LOAD_FACTOR:
self._rehash()
def remove(self, key: int) -> None:
"""删除：线性探测找到 key 后把槽置为 _DELETED（惰性删除），
不移动后续元素以保持探测链；不存在则 KeyError。"""
pos: int = self._probe_find(key)
if pos < 0:
raise KeyError(key)
self.slots[pos] = _DELETED
self._n -= 1
def __contains__(self, key: int) -> bool:
"""支持 key in table。"""
return self.get(key) is not None
def __len__(self) -> int:
"""当前键值对个数。"""
return self._n
def clear(self) -> None:
"""清空所有槽为 None 并置 _n 为 0。"""
for i in range(self.cap):
self.slots[i] = None
self._n = 0说明：槽位为 None（空）、_DELETED（已删占位）或 (key, value)。_probe_find 从 _index(key) 起线性探测，遇空返回 -1，遇 key 返回下标。_probe_slot 为 put 找可写位置：优先复用第一个遇到的 _DELETED，否则用第一个 None；若找到同 key 则返回该下标以便覆盖。remove 只把槽位置为 _DELETED，不移动后续元素，保证探测链不断。_rehash 时新建更大数组，仅把当前有效键值对重新 put 进去，自然去掉所有 _DELETED。
内置用法示例：
from typing import Dict, Set, List, Optional
def dict_set_demo() -> None:
d: Dict[str, int] = {}
d["a"] = 1
d["b"] = 2
v: Optional[int] = d.get("a") # 1
has: bool = "c" in d # False
keys: List[str] = list(d.keys())
s: Set[int] = set()
s.add(3)
s.add(7)
s.discard(3)
in_set: bool = 7 in s # True六、哈希表操作复杂度
| 操作 | 平均 | 说明 |
|---|---|---|
| 查找（key 是否存在 / 取值） | O(1) | 哈希 + 冲突链或探测 |
| 插入 / 更新 | O(1) 均摊 | 含扩容 rehash |
| 删除 | O(1) 均摊 | 同上 |
| 遍历所有键值对 | O(n) | n 为键值对数量 |
七、常见应用延伸
哈希表适合：计数（key 为元素，value 为出现次数）、去重/判存在（set 或 dict 的 key）、两数之和（扫一遍，用 dict 记「已见过的数」及下标）、分组（key 为分组依据，value 为列表）、缓存（key 为请求，value 为结果）。下面三道例题覆盖「查找互补、分组、连续序列」。
八、例题与代码详解
以下三道题给出完整题目描述、Python3 解法（带类型标注）与详细讲解。
例题 1：两数之和（无序数组）
题目描述：给定整数数组 nums 和整数 target，在数组中找两个不同下标 i、j，使 nums[i] + nums[j] == target。返回这两个下标组成的列表；保证有且仅有一组解。
输入：nums 长度 ≥ 2；有且一组解。
输出：[i, j]，i < j。
from typing import List, Dict
def two_sum(nums: List[int], target: int) -> List[int]:
"""一遍扫描：用哈希表记录「值 → 下标」，对当前 x 查 target-x 是否已出现。"""
seen: Dict[int, int] = {}
for i, x in enumerate(nums):
need: int = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []讲解：对每个位置 i、值 x，若存在 j < i 使得 nums[j] == target - x，则 (j, i) 即为答案。用哈希表 seen 记录「已遍历过的值 → 其下标」，遍历到 x 时查 target - x 是否在 seen 中，若有则返回 [seen[need], i]，否则将 x → i 加入 seen。单遍扫描，时间 O(n)，空间 O(n)。
例题 2：字母异位词分组
题目描述：给定字符串数组 strs，将其中所有字母异位词（所含字母相同、仅顺序不同）分到同一组。返回分组后的列表，每组内为若干字符串。
输入：strs 非空，仅小写字母。
输出：List[List[str]]，每组为字母异位词列表。
from typing import List, Dict, Tuple
from collections import defaultdict
def group_anagrams(strs: List[str]) -> List[List[str]]:
"""分组键：将单词按字符排序后的元组（或计数元组），同键的为异位词。"""
groups: Dict[Tuple[str, ...], List[str]] = defaultdict(list)
for s in strs:
key: Tuple[str, ...] = tuple(sorted(s))
groups[key].append(s)
return list(groups.values())讲解：两个字符串是字母异位词当且仅当它们排序后相同。因此用「排序后的元组」作为分组键：key = tuple(sorted(s))，同一 key 下的所有字符串即一组异位词。用 defaultdict(list) 方便往组里 append。最后返回 groups.values() 转成的列表。设单词最大长度为 k，n 个单词，时间 O(n·k log k)，空间 O(n·k)。
例题 3：最长连续序列
题目描述：给定未排序的整数数组 nums，求其中数字连续的最长序列的长度。连续指如 [1,2,3,4] 这样相邻差为 1，不要求在原数组中连续出现。
输入：nums 可能含重复；长度 ≥ 0。
输出：最长连续序列的长度（整数）。
from typing import List, Set
def longest_consecutive(nums: List[int]) -> int:
"""用 set 存所有数；只从「某段连续序列的最小值」开始向后扩，避免重复统计。"""
s: Set[int] = set(nums)
best: int = 0
for x in s:
if x - 1 in s:
continue
cur: int = 0
while x + cur in s:
cur += 1
best = max(best, cur)
return best讲解：若从每个数都往后扩，会重复统计同一段。优化：只从「某段连续序列的最小值」开始扩——即当 x-1 不在集合中时，说明 x 可能是某段的最小值，从 x 开始用 while x+cur in s 向后数长度。用 set 使单次查找 O(1)，每个数最多被「起点」或「被数到」各一次，时间 O(n)，空间 O(n)。
九、小结
哈希表通过哈希函数将键映射到桶下标，实现平均 O(1) 的查找、插入、删除。哈希函数需确定性、均匀、高效；冲突处理常用链地址法或开放定址法；负载因子过高时需扩容 rehash。Python 的 dict 与 set 即哈希表，键须不可变。典型应用：计数、去重、两数之和、分组、缓存。下一章我们会学树与二叉树——层次结构与递归遍历。