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

Python内置dict和set采用开放寻址法而非链地址法，通过探测序列寻找空槽；手动实现链地址法需用列表存桶，开放寻址法则需DELETE标记处理删除。哈希冲突发生时，dict 和 set 实际用的是链地址法Python 内置的 dict 和 set 在底层 C 实现中采用的是**开放寻址法（open addressing）**，不是链地址法（chaining）。这点很多人会搞反——尤其学过教材里“链表挂桶”的经典示例后，容易误以为 Python 也这么干。它用的是带探测序列的开放寻址：当 hash(key) % table_size 对应位置已被占用，就按固定规则（如线性探测 + 二次探测混合）找下一个空槽。好处是缓存友好、内存连续；坏处是负载因子一高，查找退化明显。你没法在纯 Python 层直接“切换”成链地址法——dict 的实现不暴露桶结构如果真需要链地址行为（比如调试冲突分布、教学演示），得自己手写哈希表类，用 list 存桶，每个桶是 list 或 dequePython 3.7+ 的 dict 保持插入顺序，但这和冲突解决策略无关，是额外维护的索引数组自己实现链地址法：用 list 做桶，hash() 控制索引核心就三步：算哈希 → 取模定桶 → 在桶内遍历比对键。注意 Python 的 hash() 对相同字符串稳定，但对不同进程/启动可能加盐（PYTHONHASHSEED），所以别拿它做持久化依据。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.sizedef 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</pre>桶大小固定，没扩容逻辑——实际要用就得加 len(self) > self.size * 0.7 时重建hash(key) 可能为负，但 % 在 Python 中结果恒为非负，安全桶内用线性查找，O(1) 是均摊的；最坏 O(n)（所有键哈希到同一桶）开放寻址法手动实现：线性探测 + 删除标记开放寻址难在删除：不能真删，否则会断掉后续探测链。得用一个特殊标记（如 DELETED）占位，查找时跳过，插入时可复用。 Mokker AI AI产品图添加背景