博客

Python中Dict两种实现的原理详解

  • Post category:Python

下面我将为您详细讲解 Python 中 Dict 两种实现的原理。

标准的字典实现

Python 中的标准实现 Dict，是使用哈希表来实现的。哈希表本质上是一个 Key-Value 映射表，通过将 Key 对应到一个索引来实现，在理想情况下，每一个 Key 都会被哈希到一个唯一的索引上，在索引处存储对应的 Value，这样就可以通过 Key 快速查找到对应的 Value，从而实现了字典的常数级访问速度。哈希表的实现需要解决哈希冲突的问题，通常使用的解决方法是开发定址法和链地址法。

具体来说，Python 中的哈希表实现是这样的：

  1. 创建一个基于哈希表的空字典对象时，Python 解释器会为其分配固定大小的内存空间，用于存储哈希表的各种元素。

  2. 当向字典中添加元素时，Python 解释器计算该元素的哈希值，然后将其映射到哈希表的相应插槽。如果该插槽已经有元素了，则需要使用冲突解决算法（Python 使用的是开放定址法和二次探测法），找到另一个空插槽，最终将元素插入到该插槽中。在 Python 中，每个哈希表插槽同时也是一个双向链表，用于解决哈希冲突时，将新元素插入到链表头，老元素则顺序排列在之后。

  3. 当从字典中删除元素时，Python 解释器会将该元素所对应的插槽从链表中移除，然后将其填入一个 dummy 值（这里指的是 PyDict_DUMMY 常量），以便 hash 查找时不再考虑该插槽。

  4. 对字典进行 resize（扩容）操作时，Python 解释器会新建一张哈希表，并将旧表中的所有元素重新哈希到新表中。其中的映射算法和插入和删除元素时类似，只是所有元素的操作需要在新加入的哈希表中进行，最后释放旧表空间。

下面是一个简单的代码示例：

# 创建一个空的字典
d = {}

# 添加元素
d['name'] = 'Jack'
d['age'] = 30

# 删除元素
del d['name']

# 查找元素
print(d['age']) # 输出 30

OrderedDict的实现

Python 中的 OrderedDict 是一个有序字典，其实现和普通的字典实现非常相似，只是多了一些双向链表的指针，用于维护元素的插入顺序。

具体来说，Python 中的有序字典 OrderedDict 与普通字典的区别如下：

  1. OrderedDict 内部维护着两个双向链表，一个是哈希表，用于快速定位元素，另一个是插入顺序链表，用于维护元素的插入顺序。

  2. 当向有序字典中添加元素时，Python 解释器会先在哈希表中寻找元素是否已经存在，如果存在，则更新对应的 Value 值；如果不存在，则将 Key-Value 对插入到哈希表的末尾，并将该元素插入到插入顺序链表的末尾。

  3. 当从有序字典中删除元素时，Python 解释器先从哈希表中将对应的元素删除，然后将该元素从插入顺序链表中删除。

  4. 由于有序字典需要维护插入顺序链表，所以在进行迭代时，迭代器会按照元素插入的顺序遍历字典内所有元素。

下面是一个简单的代码示例：

# 导入 OrderedDict 依赖
from collections import OrderedDict

# 创建一个空的有序字典
od = OrderedDict()

# 添加元素
od['name'] = 'Jack'
od['age'] = 30

# 删除元素
del od['name']

# 查找元素
print(od['age']) # 输出 30

# 迭代元素
for key, value in od.items():
    print(key, value)

# 输出：
# age 30
Tags: ,