python 字典原理

1. Python字典

Python字典（dict）是一种可变容器模型，用于存储键值对（key-value）映射关系。它是Python中最重要、最常用的数据结构之一。

主要特性：

• 无序性（Python 3.7+开始保持插入顺序）
• 键必须是可哈希的不可变类型
• 值可以是任意Python对象
• 动态扩容，自动调整大小
• 提供快速的查找、插入和删除操作

2. 实现原理

• 计算哈希值：对键调用hash()函数得到哈希值
• 计算索引：index = hash(key) & (mask)，其中mask = table_size - 1
• 处理冲突：使用开放定址法中的伪随机探测
• 插入/查找：在计算的位置开始探测，直到找到空槽或匹配的键

2.1 数据结构

// 简化的CPython实现结构
typedef struct {
    Py_ssize_t me_hash;      // 键的哈希值缓存
    PyObject *me_key;        // 键对象
    PyObject *me_value;      // 值对象
} PyDictKeyEntry;

typedef struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;      // 哈希表大小
    Py_ssize_t dk_usable;    // 可用条目数
    PyDictKeyEntry dk_entries[1];  // 条目数组
} PyDictKeysObject;

此外，dict中还有三个重要的槽位概念:

• Dummy: 用于记录被删除过的槽，方便复用
• None: 空槽
• Active: 正在使用的槽

2.2 扩容机制

当前剩余容量不到1/3时，会触发，计算新的大小，并重建dict

def calculate_new_size(current_used):
    """计算新的表大小"""
    # 新大小 = 已使用条目数 × 4，向上取整到2的幂
    min_size = current_used * 4
    size = 8  # 最小大小
    
    # 找到大于min_size的最小2的幂
    while size < min_size:
        size <<= 1
    
    return size

2.3 整理机制

当dict满足以下两个条件之一的时候，触发整理:

• dummy槽过多: 当dummy槽 > 总容量的1/3时
• 字典大小远超实际需要: 当已经使用了50个hash槽，且容量不到1/8时

之后会重建字典，同时也会去除所有的dummy，重建后字典大小为MAX(当前字典大小 * 4(取上限到2的幂), 8, 当前的一半)

optimal_size = max(
    calculate_new_size(dict_obj.ma_used),
    dict_obj.ma_keys.dk_size // 2  # 至少缩小一半
)

3. hash碰撞解决方案(开发地址法)

python中使用伪随机探测序列的方法来解决hash碰撞问题:

index = (5 * index + 1 + perturb) % table_size
perturb >>= 5

槽位探测过程:

• 会记录Dummy槽（被删除的槽，重建时消失），后续如果找不到匹配的就优先使用Dummy
• 寻找空槽，没有Dummy再用
• 寻找匹配的键，用于查找、更新

def find_slot(keys, key, hash_value):
    """查找键的槽位或插入位置"""
    table_size = len(keys)
    mask = table_size - 1
    index = hash_value & mask
    perturb = hash_value
    
    # 记录第一个可用的dummy槽位
    first_dummy = None
    
    while True:
        entry = keys[index]
        
        if entry.me_key is None:
            # 空槽 - 可用于插入
            if first_dummy is not None:
                return first_dummy, 'DUMMY'  # 优先复用dummy槽
            return index, 'EMPTY'
            
        elif entry.me_key is dummy:
            # Dummy槽 - 记录但不立即使用
            if first_dummy is None:
                first_dummy = index
                
        elif entry.me_hash == hash_value and entry.me_key == key:
            # 找到匹配的键
            return index, 'ACTIVE'
            
        # 继续探测
        index = (5 * index + 1 + perturb) & mask
        perturb >>= 5

4. 与Java HashMap对比

Java使用链地址法，在Java8之后，对于链表长度超过8时就触发红黑树转换。

特性	Python Dict (开放定址法)	Java HashMap (链地址法)
缓存友好性	更好（数据局部性）	较差（指针跳转）
内存使用	紧凑	额外指针开销
最差性能	O(n)	O(log n)
删除操作	需特殊标记	直接删除