Python 内置了强大的数据结构，比如列表、元组、字典，让 Python 开发者处理数据时可以信手拈来，但是正是因为 Python 做了太多，让我们忽视了很多细节，本文通过解析 CPython 源码，介绍 Python 的内置数据结构的设计与实现。
Python 序列类型概览
Python 标准库用 C 实现了丰富的序列类型。根据存放的内容可以分为 容器序列 和 扁平序列 ：
容器序列：list、tuple、collections.deque
扁平序列：str、bytes、bytearray、memoryview、array.array
简单讲，容器序列存放的是对任意对象的引用；扁平序列存放的是值，也就是说扁平序列只能存放字符、字节、数值等基础类型。接下来我们从 CPython 实现的角度出发，详细讲解 Python 中最常见的两种序列——列表和元组。
序列之列表
list 作为 Python 中最常用的内置数据结构，运用十分广泛且灵活。首先 list 是个可变序列，可以自由增加或删除元素，其次 list 可以存放任意类型的元素，光这两个特点就足够程序员开心的了。下面看看 list 是如何实现的。
列表的实现
首先看看 CPython 中对 list 结构的定义，其对象接口定义在 listobject.h 中：
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
typedef struct {
PyObject ob_base;
Py_ssize_t ob_size;
} PyVarObject;
其中 PyObject_VAR_HEAD 由下面的 PyVarObject 定义，而其中的 ob_size 记录的是实际使用的内存的数量；ob_item 指向了列表所在内存的首地址；allocated 则记录了当前列表中可存放的所有元素的数量总和。
每一次需要申请内存的时候，总会申请大块内存，将申请的内存大小记录在 allocated 中，而实际使用的内存大小记录在 ob_size 中。这样做就很高效的实现了内存管理，可以频繁地进行插入、删除等操作。
list 的所有操作都是通过指针 ob_item 实现的。指针指向存储对象的内存地址，也就实现了存放任意类型的元素这一功能。list 的实现定义在 listObject.c 中，代码就不贴出来了，链接：https://github.com/python/cpython/blob/master/Objects/listobject.c。
CPython 在列表中维护了一个缓冲池 free_list，里面存放了可用的 list 对象，总长度为 80。创建列表前先在这个缓冲池中查找可用对象，如果有直接唤醒，对其 ob_item 分配空间；如果没有则另外申请内存，再对其 ob_item 分配空间。相对应的，销毁 list 时，先销毁其 ob_item 指向的空间，再检查 free_list 中是否有空间，如果有将其放入以供下次使用；如果没有直接销毁。
正如前面所说，list 的所有操作都是通过 ob_item 实现的，那么基于 C 中指针的了解，不难理解列表的索引、修改等操作，这里不赘述。
需要注意的是，insert 和 append 操作都对列表当前的使用内存产生影响。所以在插入元素前调用 list_resize 函数来调整内存。调整过程为：
- 当
allocated/2 <= newsize <= allocated时，直接赋值，即ob_size = newsize； - 否则调用
realloc重新分配内存并缩小allocated，以实现内存空间的最大利用。
而 insert 和 append 的区别在于：insert 将 i (需要插入的位置) 向后的元素向后顺移，再在 i 处插入；append 在 ob_size + 1 处插入。
而删除操作，需要遍历整个列表，找到满足条件的元素时，将其删除，并将后面位置的元素前移一位。
了解了列表的基本操作之后，我们知道列表的索引、修改和 append 操作的复杂度为 O(1) ，而 insert 和删除需要遍历，复杂度为 O(n) 。
序列之元组
Python 中的元组以其不可变特征闻名，可以理解成是一个不可变的列表，下面看看元组的底层实现。
元组的实现
元组的结构定义在 tupleobject.h 中：
typedef struct {
PyObject_VAR_HEAD
PyObject *ob_item[1];
} PyTupleObject;
与列表类似， PyObject_VAR_HEAD 中的 ob_size 记录元组长度（一经创建不可改变）； ob_item 是存放元组元素的指针数组。
元组的相关操作定义在 tupleobject.c 中，链接：https://github.com/python/cpython/blob/master/Objects/tupleobject.c。 tupleobject.c 中也维护了一个元组缓冲池 free_list ，定义如下，但是长度只有 20。这个缓冲池与列表不一样的是，数组中每个元素指向的是一个单链表的头指针，这个链表中元组对象的 ob_item[0] 指向下一个元组，且每个元组长度一致。而 numfree 记录的是这个链表的长度，最长为 2000。
static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
static int numfree[PyTuple_MAXSAVESIZE];
元组的创建与列表类似，先从缓冲区中查找是否有可用对象，有则提取头指针，同时 numfree 对应减一；没有则另外开辟内存。删除元组的时候，先判断缓冲区对应的链表长度是否超过最大长度，没有就将其放入单链表头；超过则直接销毁。元组一经建立不可改变，所以没有其他赋值操作。
从以上分析可以看出，元组的缓冲区仅对长度小于 20 的元组做了优化。元组的元素索引也是通过指针读取，这一点跟列表一致。而与列表相比，元组中没有 allocated ，可以看出相同元素的列表比元组耗内存。
由于元组是通过指针数组 ob_item[] 存储的，换句话说，元组储存了元素的地址。元组的不可变在于其记录的内存地址不可变，而该地址中存储的内容是可以改变的（除非该地址中的内容本身也是不可变的）。
对序列的操作
Python 的序列一般都支持切片、+、* 等操作，基础操作这里不做介绍，只介绍一个特殊的操作——增量赋值及其可能引发的 bug 。
增量赋值
增量赋值是指 += 和 *= 操作，其表现如何取决于左边的操作对象。+= 相当于调用特殊方法 __iadd__ ，如果此对象没有实现 __iadd__ 方法则会调用 __add__ 。
而 __iadd__ 是就地加法（不会创建新变量），对于可变序列而言， a += b 相当于对 a 直接调用 a.extend(b) ；如果没有实现 __iadd__ ，就相当于 a = a + b ，而此过程是 a + b 创建出一个新对象，再赋值给 a 。
*= 与 += 一样，只是背后的特殊方法是 __imul__。总体来说，可变序列都实现了 __iadd__ 和 __imul__ 方法，所以 += 和 *= 都是就地加法。
然而，对某些元组使用增量赋值，会产生神奇的事情，看个 🌰：
In [1]: a = (1, 2, [3, 4])
In [2]: a[2] += [1, 1]
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-2-c3bcb5efc80e> in <module>()
----> 1 a[2] += [1, 1]
TypeError: 'tuple' object does not support item assignment
In [3]: a
Out[3]: (1, 2, [3, 4, 1, 1])
如果元组中有可变类型的变量，再对元组中的这个可变对象进行增量赋值的时候，会提示元组不支持赋值，但实际又赋值成功了。
这是因为增量赋值不是原子操作，这行代码的执行顺序是：
- 执行操作
a[2] + [1, 1] - 将第一步执行的结果赋值给
a[2]
由于 a[2] 是可变列表，所以第一步可以执行成功， a[2] 的值已经发生改变；但第二步是个赋值操作，由于元组是不可变的，所以报错。
上述这种边界情况十分罕见，为了避免这种情况出现，还是避免出现在元组中放入可变序列这种操作。
字典
Python 中另外一种十分重要的数据结构就是字典，在各种程序中被广泛使用。而 Python 也对其进行了高度优化。为了更好的使用字典，我们来剖析字典的内部构造。
字典的结构
字典是基于散列表实现的，其结构定义在 dictobject.h 中：
typedef struct {
PyObject_HEAD
Py_ssize_t ma_used;
uint64_t ma_version_tag;
PyDictKeysObject *ma_keys;
PyObject **ma_values;
} PyDictObject;
其中， ma_used 记录了字典中元素的个数； ma_version_tag 记录了字典版本，每次字典有修改该值都会变；指针 ma_keys 指向一个 PyDictKeysObject 类型的对象； ma_values 记录的是字典的 value 值，而我们根据这个值是否为 None 来判断字典的类型（ combined/split ）。
PyDictKeysObject 的结构如下：
| PyDictKeysObject |
|---|
| dk_refcnt |
| dk_size |
| dk_lookup |
| dk_usable |
| dk_nentries |
| dk_indices |
| dk_entries |
其中， dk_size 记录了 hash 表 dk_indices 的大小； dk_lookup 表示在 hash 表中查找元素的方法； dk_usable 记录的是 dk_entries 中可用的数量； dk_nentries 记录的是 dk_entries 中已用的数量； dk_indices 是真正的 hash 表； dk_entries 是一组 PyDictKeyEntry 对象的数组，其定义如下。
typedef struct {
/* Cached hash code of me_key. */
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;
由于对象的属性都是通过字典的形式存储，会导致很多对象的属性都是键一样但值不一样。Python 针对这一特性对字典的内存管理做了优化。将字典分成 combined 和 split。
combined 型字典中， dk_refcnt = 1 ，字典的值存放在 ma_keys 的 dk_entries 的 me_value 中；
split 型字典中，dk_refcnt >= 1，字典的值存放在 ma_values 中。
而 dk_entries 数组的 index 是根据 ma_keys 的 dk_indices 获取的，有4种状态：
- Unused. index == -1.
- Active. index >= 0, me_key != NULL and me_value != NULL
- Dummy. index == -2 (combined only)
- Pending. index >= 0, key != NULL, and value == NULL (split only)
显然，对于 Unused 和 Dummy 类型的 slot， dk_entries 中没有再浪费内存；同时，还会根据需要索引的 dk_entries 的数量动态的决定用什么类型的变量来表示 index。再来说说 split 类型的字典，这种字典的 key 是共享的，有个引数计数器 dk_refcnt 来维护当前被引用的个数，其 value 值以数组的形式存放在 ma_values 中，这样就避免同一个 key 多次储存 value ，节省了内存，也使得同一个 key 值的 value 以更紧凑的方式存储在内存中。
字典的实现原理
基于对字典结构的认知，我们再来看看字典的实现原理。关于字典的操作源代码链接：https://github.com/python/cpython/blob/master/Objects/dictobject.c
(1) 创建字典
字典中也维护了一个缓冲池 freelist ，长度为 80。创建字典的逻辑也类似，先在缓冲池中查找可用的字典，有则直接使用，没有则走申请内存的逻辑。在某些特定情况(比如对象的属性赋值)下，会将字典初始化为 split 型。
字典在每次 insert 新键值对前，都会检查 dk_entries 中可用的空间，必要时重新分配以保证至少有三分之一是可用的。在插入新键值对时，先计算 key 的 hash 值，再用这个 hash 值根据一套完整的算法计算出 dk_entries 数组的 index。最后对应变量记录数据。
(2) 字典的索引
字典的索引也是根据 key 的 hash 值来获得的，计算出 hash 值后，将该值的最低几位数字当做偏移量，在 hash 表中查找 index，若找到的 dk_entries 为空，则抛错；若不为空，检查 me_key 是否等于 key，相等则对应的 me_value 即为所求，不相等则发生 hash 碰撞，为了解决 hash 冲突问题，算法会在 hash 值中另外再取几位，然后用特殊的方法处理一下，把新得到的数字再当作索引来寻找，重复以上步骤。可用图表示如下：
字典的特征
通过以上对字典的实现原理的分析，不难得出以下结论：
key 必须是可散列的。即满足以下条件：
- 支持
hash()函数，且得到的值是唯一的； - 支持通过
__eq__()方法来检测相等性； - 若
a == b为真，则hash(a) == hash(b)也为真；
字典在内存上的开销巨大
由于字典使用了 hash 表，而 hash 表又必须是稀疏的，这导致它在空间上的效率低下。而用元组取代字典可以节省相当的内存开销，原因有二：1. 避免了 hash 表所消耗的内存；2. 无需把记录中字段的名字在每个元素里都存一遍。
键查询很快
dict 的实现是典型的空间换时间，只要字典能被装在内存里，就可以提供无视数据量大小的快速访问。
键的次序取决于添加顺序
当往 dict 里添加新键而又发生散列冲突的时候，新键可能会被安排存放到另一个位置。
往字典里添加新键可能会改变已有键的顺序
无论何时往字典里添加新的键，Python 解释器都可能做出为字典扩容的决定。扩容导致的结果就是要新建一个更大的散列表，并把字典里已有的元素添加到新表里。这个过程中可能会发生新的散列冲突，导致新散列表中键的次序变化。所以最好不要对字典同时进行迭代和修改。
