Python哈希冲突怎么解决_链地址法与开放寻址法代码演示-Python教程-PHP中文网

python内置dict和set采用开放寻址法而非链地址法，通过探测序列寻找空槽；手动实现链地址法需用列表存桶，开放寻址法则需delete标记处理删除。

python哈希冲突怎么解决_链地址法与开放寻址法代码演示

哈希冲突发生时，`dict` 和 `set` 实际用的是链地址法

Python 内置的 dict 和 set 在底层 C 实现中采用的是**开放寻址法（open addressing）**，不是链地址法（chaining）。这点很多人会搞反——尤其学过教材里“链表挂桶”的经典示例后，容易误以为 Python 也这么干。

它用的是带探测序列的开放寻址：当 hash(key) % table_size 对应位置已被占用，就按固定规则（如线性探测 + 二次探测混合）找下一个空槽。好处是缓存友好、内存连续；坏处是负载因子一高，查找退化明显。

你没法在纯 Python 层直接“切换”成链地址法——dict 的实现不暴露桶结构
如果真需要链地址行为（比如调试冲突分布、教学演示），得自己手写哈希表类，用 list 存桶，每个桶是 list 或 deque
Python 3.7+ 的 dict 保持插入顺序，但这和冲突解决策略无关，是额外维护的索引数组

自己实现链地址法：用 `list` 做桶，`hash()` 控制索引

核心就三步：算哈希 → 取模定桶 → 在桶内遍历比对键。注意 Python 的 hash() 对相同字符串稳定，但对不同进程/启动可能加盐（PYTHONHASHSEED），所以别拿它做持久化依据。

Li Python Sec Check

Python 安全规范检查工具：基于 CloudBase 规范、腾讯安全指南，LLM 智能分析（默认禁用，优先本地执行）

下载

class SimpleChainedDict:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]
<pre class="brush:python;toolbar:false;">def _hash(self, key):
    return hash(key) % self.size

def set(self, key, value):
    idx = self._hash(key)
    bucket = self.buckets[idx]
    for i, (k, v) in enumerate(bucket):
        if k == key:  # 已存在，覆盖
            bucket[i] = (key, value)
            return
    bucket.append((key, value))  # 新增

def get(self, key, default=None):
    idx = self._hash(key)
    bucket = self.buckets[idx]
    for k, v in bucket:
        if k == key:
            return v
    return default

桶大小固定，没扩容逻辑——实际要用就得加 len(self) > self.size * 0.7 时重建
hash(key) 可能为负，但 % 在 Python 中结果恒为非负，安全
桶内用线性查找，O(1) 是均摊的；最坏 O(n)（所有键哈希到同一桶）

开放寻址法手动实现：线性探测 + 删除标记

开放寻址难在删除：不能真删，否则会断掉后续探测链。得用一个特殊标记（如 DELETED）占位，查找时跳过，插入时可复用。

class SimpleOpenAddressDict:
    EMPTY = object()
    DELETED = object()
<pre class="brush:python;toolbar:false;">def __init__(self, size=8):
    self.size = size
    self.keys = [self.EMPTY] * size
    self.values = [None] * size

def _hash(self, key, i):
    return (hash(key) + i) % self.size  # 线性探测

def set(self, key, value):
    for i in range(self.size):
        idx = self._hash(key, i)
        if self.keys[idx] is self.EMPTY or self.keys[idx] is self.DELETED:
            self.keys[idx] = key
            self.values[idx] = value
            return
    raise ValueError("Table full")

def get(self, key, default=None):
    for i in range(self.size):
        idx = self._hash(key, i)
        if self.keys[idx] is self.EMPTY:
            return default
        if self.keys[idx] is self.DELETED:
            continue
        if self.keys[idx] == key:
            return self.values[idx]
    return default