python中字典的内部实现原理是什么

发布时间：2021-06-21 18:21:27 作者：Leah
来源：亿速云阅读：271

# Python中字典的内部实现原理是什么

## 1. 字典的基本特性

字典（dict）是Python中最重要且最常用的数据结构之一，它以键值对（key-value）的形式存储数据，具有以下核心特性：

- **无序性**（Python 3.6+后变为有序实现）
- **可变性**：可动态添加/删除键值对
- **唯一键**：每个键必须是唯一的
- **高效查找**：平均O(1)时间复杂度

## 2. 字典的底层数据结构

Python字典的底层实现经历了重大演变：

### 2.1 Python 3.6之前的实现

采用**哈希表（Hash Table）**实现，包含三个核心部分：

1. **哈希表条目（dict_entry）**：存储键值对
2. **哈希函数**：将键映射到索引位置
3. **冲突解决机制**：开放寻址法（线性探测）

### 2.2 Python 3.6+的优化实现

引入更高效的**紧凑型（compact）**存储结构：

```python
# 概念性结构示意
struct dict {
    PyObject **indices;    // 稀疏哈希索引表
    PyDictKeyEntry *entries; // 紧凑条目数组
    Py_ssize_t size;       // 总容量
    Py_ssize_t used;       // 已用数量
};

3. 哈希表工作原理

3.1 哈希函数

Python使用内置的hash()函数计算键的哈希值：

index = hash(key) % table_size

3.2 冲突解决

当不同键产生相同哈希值时，Python采用开放寻址法处理：

计算初始索引
如果发生冲突，按公式index = (5*index + 1) % table_size探测
重复直到找到空槽

3.3 哈希表扩容

当哈希表填充率超过2/3时触发扩容（resize）：

新容量计算：new_size = 4 * used或2 * size
重建哈希表并重新哈希所有条目

4. Python 3.6+的优化细节

4.1 内存布局优化

采用分离式存储设计： - indices：稀疏数组，存储条目索引（1字节/8字节） - entries：紧凑数组，按插入顺序存储实际数据

# 示例字典
d = {'a': 1, 'b': 2}

# 内部存储示意
indices = [None, 0, None, 1]  # 哈希索引
entries = [
    {'hash': hash('a'), 'key': 'a', 'value': 1},
    {'hash': hash('b'), 'key': 'b', 'value': 2}
]

4.2 顺序保持特性

由于条目按插入顺序存储，Python 3.7+正式将字典顺序确定为语言特性。

5. 关键操作的时间复杂度

操作	平均情况	最坏情况
查找	O(1)	O(n)
插入	O(1)	O(n)
删除	O(1)	O(n)
迭代	O(n)	O(n)

6. 字典的特殊处理机制

6.1 自定义对象的哈希

自定义类默认使用id()作为哈希值，但可重写__hash__方法：

class Person:
    def __init__(self, name):
        self.name = name
    
    def __hash__(self):
        return hash(self.name)

6.2 不可变类型作为键

只有可哈希（不可变）类型才能作为字典键： - 允许：str, int, float, tuple - 禁止：list, dict, set

6.3 字典视图

Python 3提供三种视图对象： - dict.keys()：键视图 - dict.values()：值视图 - dict.items()：键值对视图

7. 性能优化技巧

预分配空间：使用dict.fromkeys()或预设大小
```
d = dict.fromkeys(range(1000))
```
避免频繁扩容：预估最终大小初始化字典
```
d = {None: None} * expected_size
```
使用简单键：整数和字符串的哈希效率最高
利用字典推导式：
```
squares = {x: x*x for x in range(100)}
```

8. 字典与其它数据结构的对比

8.1 与列表比较

特性	字典	列表
查找速度	O(1)	O(n)
内存占用	较高	较低
顺序	插入序	索引序

8.2 与集合比较

集合本质上是只有键的字典，实现原理相同。

9. 实际案例分析

9.1 字典合并操作

Python 3.9+支持合并运算符：

d1 = {'a': 1}
d2 = {'b': 2}
merged = d1 | d2

9.2 默认字典处理

collections.defaultdict的优化实现：

from collections import defaultdict
dd = defaultdict(list)
dd['key'].append(1)  # 自动初始化列表

10. 底层C源码解析

关键结构体定义（简化版）：

typedef struct {
    Py_hash_t me_hash;    // 缓存哈希值
    PyObject *me_key;     // 键对象
    PyObject *me_value;   // 值对象
} PyDictKeyEntry;

typedef struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;    // 哈希表大小
    PyDictKeyEntry dk_entries[]; 
} PyDictKeysObject;

11. 总结

Python字典的高效性源于： 1. 精心设计的哈希算法 2. 动态扩容机制 3. 内存布局优化（3.6+） 4. 冲突解决策略的平衡

随着Python版本迭代，字典在保持高效的同时，获得了顺序保持、内存优化等特性，成为Python中最强大的数据结构之一。

注意：实际实现细节可能因Python版本和具体解释器（CPython/PyPy等）而有所不同。本文主要基于CPython 3.10实现分析。 “`

这篇文章共计约1750字，全面介绍了Python字典的内部实现原理，包含： 1. 数据结构演变 2. 哈希表工作原理 3. 性能优化细节 4. 实际应用案例 5. 底层源码解析

采用Markdown格式编写，包含代码块、表格等元素，便于技术文档的呈现和阅读。