数据结构与算法 / 系统课时

哈希冲突处理

哈希冲突处理

不同键落入同一桶是哈希表的正常现象。本课比较链地址法与开放寻址法,并用一个支持插入、查询和删除的线性探测表说明探测路径为何不能被错误截断。

学习目标

  • 解释哈希冲突为什么只能降低而不能消除。
  • 说明链地址法和开放寻址法的存储差异。
  • 实现带墓碑标记的线性探测插入、查询与删除。

两种常见处理策略

链地址法让每个桶保存多个键值对。定位桶后,再在桶内比较键;删除较直接,负载因子也可以超过 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']

性能与选择

链地址法对删除更友好,桶内结构也较灵活;开放寻址法数据连续、缓存局部性较好,但在负载升高后探测距离会迅速增加。线性探测还容易形成连续占用区,也就是主聚集。

无论采用哪种策略,插入、查询和删除都必须使用一致的哈希与定位规则。开放寻址表还应在槽位过密或墓碑过多时扩容并重建。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

哈希冲突处理

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通