Python中的字典与集合的哈希冲突解决策略

知识点描述
哈希冲突是指不同的键经过哈希函数计算后得到相同的哈希值。Python的字典和集合使用开放寻址法解决哈希冲突，具体实现是二次探测序列。理解这个机制有助于优化程序性能，特别是在处理大量数据时。

哈希表基础

1. 字典和集合底层都是哈希表实现
2. 每个键通过哈希函数得到索引位置
3. 理想情况下每个键都有唯一位置，但实际会出现冲突

冲突解决策略演进

第一步：线性探测

• 最简单的开放寻址法
• 发生冲突时，顺序检查下一个位置
• 示例：键A的哈希值是5，但位置5已被占用，就检查6、7、8...
• 缺点：容易产生聚集现象，降低查找效率

第二步：二次探测

• Python实际采用的方法
• 使用公式：index = (5*index + 1) % table_size
• 在Python中具体实现为：j = ((5*j) + 1) mod 2**i
• 这样能更均匀地分散冲突的键

具体实现细节

哈希表结构

# 简化版的字典条目结构
class DictEntry:
    def __init__(self, key, value, hash_value):
        self.key = key
        self.value = value
        self.hash_value = hash_value

插入过程

1. 计算键的哈希值：hash_value = hash(key)
2. 计算初始索引：index = hash_value % table_size
3. 如果该位置为空，直接插入
4. 如果发生冲突，使用探测序列找下一个位置

查找过程

1. 计算哈希值和初始索引
2. 检查该位置的键是否匹配
3. 如果不匹配，按探测序列继续查找
4. 遇到空位置说明键不存在

删除的特殊处理

• 不能简单地将位置置为空
• 需要标记为"伪删除"（dummy）
• 否则会中断探测序列，导致查找失败

性能优化考虑

负载因子

• 当负载因子（已用位置/总位置）超过2/3时触发扩容
• 新表大小是原表的2倍或4倍
• 扩容时重新哈希所有条目

哈希函数的重要性

• Python为内置类型提供了优化的哈希函数
• 自定义对象需要正确实现__hash__和__eq__方法

实际示例
考虑大小为8的哈希表，插入键"a"（哈希值97）、"b"（哈希值98）：

1. "a"插入位置：97%8=1
2. "b"插入位置：98%8=2
3. 如果又有键"i"（哈希值105）：105%8=1（冲突）
4. 使用探测序列：下一个位置是(5×1+1)%8=6

这种策略确保了即使在冲突情况下也能保持较高的查找效率。