数据结构与算法 / 系统课时
哈希冲突处理
哈希冲突处理
不同键落入同一桶是哈希表的正常现象。本课比较链地址法与开放寻址法,并用一个支持插入、查询和删除的线性探测表说明探测路径为何不能被错误截断。
学习目标
- 解释哈希冲突为什么只能降低而不能消除。
- 说明链地址法和开放寻址法的存储差异。
- 实现带墓碑标记的线性探测插入、查询与删除。
两种常见处理策略
链地址法让每个桶保存多个键值对。定位桶后,再在桶内比较键;删除较直接,负载因子也可以超过 1,但需要额外的桶内结构。
开放寻址法把所有条目直接放在数组槽位中。目标槽已被占用时,按固定探测序列寻找后续位置。线性探测依次检查起始槽、下一个槽,并在数组末尾回绕。

为什么删除需要墓碑
在线性探测中,查找遇到“从未使用”的空槽即可停止,因为后续不可能再有沿该探测链插入的键。若删除时直接改成空槽,就会让后方元素被误判为不存在。
墓碑表示“这里曾被占用”。查询经过墓碑时继续探测,插入可以记住第一个墓碑,但仍需继续确认后面是否已有相同键,避免产生重复键。
主示例:带删除的线性探测表
示例使用整数键,并以 key % capacity 作为起始槽,便于稳定复现冲突。生产实现还需要扩容和更完善的哈希函数,本例只聚焦探测与删除语义。
python
from dataclasses import dataclass
from typing import Optional
_DELETED = object()
@dataclass
class Entry:
key: int
value: str
class LinearProbingMap:
def __init__(self, capacity: int) -> None:
if capacity <= 0:
raise ValueError("capacity 必须大于 0")
self._slots: list[Entry | object | None] = [None] * capacity
def _start(self, key: int) -> int:
return key % len(self._slots)
def put(self, key: int, value: str) -> None:
first_deleted: Optional[int] = None
# 必须沿完整探测序列寻找已有键,不能见到墓碑就立即写入
for offset in range(len(self._slots)):
index = (self._start(key) + offset) % len(self._slots)
slot = self._slots[index]
if slot is _DELETED:
if first_deleted is None:
first_deleted = index
continue
if slot is None:
target = first_deleted if first_deleted is not None else index
self._slots[target] = Entry(key, value)
return
if isinstance(slot, Entry) and slot.key == key:
slot.value = value
return
if first_deleted is not None:
self._slots[first_deleted] = Entry(key, value)
return
raise OverflowError("哈希表已满")
def get(self, key: int) -> Optional[str]:
for offset in range(len(self._slots)):
index = (self._start(key) + offset) % len(self._slots)
slot = self._slots[index]
if slot is None:
return None
if isinstance(slot, Entry) and slot.key == key:
return slot.value
return None
def remove(self, key: int) -> bool:
for offset in range(len(self._slots)):
index = (self._start(key) + offset) % len(self._slots)
slot = self._slots[index]
if slot is None:
return False
if isinstance(slot, Entry) and slot.key == key:
# 墓碑保持后续冲突键的查找路径连续
self._slots[index] = _DELETED
return True
return False
def slot_states(self) -> list[str]:
result: list[str] = []
for slot in self._slots:
if slot is None:
result.append("EMPTY")
elif slot is _DELETED:
result.append("DEL")
else:
result.append(str(slot.key))
return result
def main() -> None:
table = LinearProbingMap(5)
table.put(1, "A")
table.put(6, "B")
table.put(11, "C")
print("初始槽位:", table.slot_states())
table.remove(6)
print("删除 6 后读取 11:", table.get(11))
print("删除后槽位:", table.slot_states())
table.put(16, "D")
print("复用墓碑后:", table.slot_states())
if __name__ == "__main__":
main()预期输出
text
初始槽位: ['EMPTY', '1', '6', '11', 'EMPTY']
删除 6 后读取 11: C
删除后槽位: ['EMPTY', '1', 'DEL', '11', 'EMPTY']
复用墓碑后: ['EMPTY', '1', '16', '11', 'EMPTY']性能与选择
链地址法对删除更友好,桶内结构也较灵活;开放寻址法数据连续、缓存局部性较好,但在负载升高后探测距离会迅速增加。线性探测还容易形成连续占用区,也就是主聚集。
无论采用哪种策略,插入、查询和删除都必须使用一致的哈希与定位规则。开放寻址表还应在槽位过密或墓碑过多时扩容并重建。
按自己的节奏,确认真正理解。