Python字典底层实现原理详解

什么是字典

Python 中的字典是一种非常常用的数据类型，它可以存储键值对。字典的实现方式比较特殊，它使用了哈希表的数据结构，可以高效地进行键值对的存储和查询。

字典规则

字典的键必须是不可变的对象（比如字符串、数字或元组），而值可以是任意对象。字典中的键是唯一的，如果重复赋值会覆盖掉原有的键值对。

字典实现原理

Python 中的字典是通过哈希表实现的。哈希表（Hash Table）是一种用于存储键值对的数据结构，它可以支持高效的平均时间复杂度为 O(1) 的插入、删除、查找操作。哈希表的基本思想是将键通过哈希函数转化为索引，然后将键值对存储在该索引对应的位置上。

Python 中的哈希表是由数组（Array）和链表（Linked List）组成的。具体来说，Python 中的字典是由一个数组和若干条链表组成的。每个元素都是一个哈希桶（Hash Bucket），哈希桶中存储了若干个键值对。

当 Python 需要将一个键值对插入到字典中时，它会首先根据键计算出哈希值。哈希值是一个整数，它可以被看作是键在哈希表中的索引。然后 Python 会根据哈希值取模，计算出键应该存放在哪个哈希桶中。如果该桶中已经有了相同的键，则 Python 会更新对应的值。

当 Python 需要查询一个键时，它会根据相同的方式来计算哈希值和索引。然后 Python 会在对应的哈希桶中寻找键。如果找到了相应的键，则 Python 返回所对应的值。如果没有找到，则 Python 返回 KeyError 异常。

示例1

下面是一个字典的例子：

d = {'a': 1, 'b': 2, 'c': 3}

这个字典中包含了三个键值对。假设哈希函数计算出了键 'b' 对应的哈希值为 42，那么 'b' 应该存放在数组的第 42 个位置上。如果第 42 个哈希桶中已经有了相应的键，那么 Python 将会更新对应的值。否则，Python 会将键值对存放在该哈希桶中。

示例2

下面是一个字典查询的例子：

d = {'a': 1, 'b': 2, 'c': 3}
print(d['b'])  # 输出 2
print(d['d'])  # KeyError: 'd'

这个例子中，Python 首先计算出键 'b' 对应的哈希值，然后根据哈希值找到了它所对应的哈希桶，并在哈希桶中找到了键值对。因此，Python 输出了键 'b' 对应的值。然后 Python 又试图查询键 'd'，但是字典中并没有键 'd'，因此 Python 抛出了 KeyError 异常。