Python内置dict和set采用开放寻址法而非链地址法，通过探测序列寻找空槽；手动实现链地址法需用列表存桶，开放寻址法则需DELETE标记处理删除。
哈希冲突发生时，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），所以别拿它做持久化依据。
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</pre>- 桶大小固定，没扩容逻辑——实际要用就得加
len(self) > self.size * 0.7时重建 -
hash(key)可能为负，但%在 Python 中结果恒为非负，安全 - 桶内用线性查找，O(1) 是均摊的；最坏 O(n)（所有键哈希到同一桶）
开放寻址法手动实现：线性探测 + 删除标记
开放寻址难在删除：不能真删，否则会断掉后续探测链。得用一个特殊标记（如 DELETED）占位，查找时跳过，插入时可复用。
立即学习“Python免费学习笔记（深入）”；
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</pre>- 探测次数上限设为
self.size，避免死循环；实际工程中会限制最大探测长度（如 50 次） -
DELETED必须是唯一对象（用object()），不能用None或False，否则和合法值混淆 - 负载因子超过 0.7 后性能急剧下降，必须扩容——且扩容后要全部 rehash
冲突多的常见原因和检查方法
别急着换算法，先确认是不是真冲突多。Python 的 dict 在负载因子
- 用
sys.getsizeof(your_dict)看实际内存占用，再除以键数，估算平均桶长（内置 dict 不暴露桶数，但可以粗略推） - 自定义类里加计数器，在
set()里统计每次探测步数，打印最大/平均值 - 检查键类型：
str冲突率极低；但若用自定义类且__hash__返回固定值（如return 42），那必然全挤一桶 - 小数据量（
真正卡住的往往不是算法选择，而是哈希函数本身质量差，或者表尺寸没随数据增长动态调整——这两点比“链地址 or 开放寻址”重要得多。
