关注+星标，每天学习Python新技能

来源：网络

最近有读者发了一条私信，希望我介绍一下 Python 列表和字典在读写数据的时候谁更快。

那就安排一下，我们先来介绍列表和字典的底层实现，如果了解了具体的实现，那么一切问题就都迎刃而解了。我准备分多篇文章介绍，本次先来介绍列表。

列表是怎么实现的？

在初学列表的时候，可能书上会告诉你列表就是一个大仓库，什么都可以存放。但我们要知道，无论是 Python 的变量，还是列表、元组里面的元素，它们本质上都是一个指针。

并且根据我们使用列表的经验，可以得出以下两个结论：

• 每个列表的元素个数可以不一样，所以这是一个变长对象；

• 可以对列表的元素进行添加、删除、修改等操作，所以这是一个可变对象；

而列表在底层由PyListObject结构体表示，定义于头文件 Include/listobject.h 中：

typedefstruct {    PyObject_VAR_HEAD    PyObject **ob_item;    Py_ssize_t allocated;} PyListObject;

我们看到里面有如下成员：

• PyObject_VAR_HEAD：变长对象的公共头部信息，包含了以下三个字段；

• ob_refcnt：对象的引用计数；

• ob_type：对象的类型；

• ob_size：负责维护变长对象的长度，比如 len(列表) 的时候，会直接返回这里的 ob_size；

• ob_item：一个二级指针，指向 PyObject * 类型的指针数组，这个指针数组保存的便是对象的指针，而操作底层数组都是通过 ob_item 来进行操作的；

• allocated：容量，我们知道列表底层是使用了 C 的数组，而底层数组的长度就是列表的容量；

列表之所以要有容量的概念，是因为列表可以动态添加和删除元素，但是底层的数组在创建完毕之后，其长度却是固定的。所以一旦添加新元素的时候，发现数组已满，这时候只能申请一个更长的数组，同时把旧数组中的元素依次拷贝到新数组里面（这一过程就是列表的扩容），然后再将新元素添加进去，最后再将旧数组释放掉。

但是问题来了，总不可能每添加一个元素，就申请一次数组、将所有元素都拷贝一次吧。所以列表在扩容的时候，会将数组申请的长一些，可以在添加元素的时候不用每次都申请新的数组。

这便是列表的底层结构示意图，我们看到底层数组的长度为 5，说明此时列表的容量为 5，但是里面只有 3 个 PyObject * 指针，说明列表的 ob_size 是 3，或者说列表里面此时有 3 个元素。

如果这个时候往列表中 append 一个元素，那么会将这个新元素设置在数组索引为 ob_size 的位置、或者说索引为 3 的位置。一旦设置完，ob_size 会自动加 1，因为 ob_size 要和列表的长度保持一致。

如果此时再往列表中 append 一个元素的话，那么还是将新元素设置在索引为 ob_size 的位置，此时也就是索引为 4 的位置。然后 ob_size 加 1，变成 5。

列表的容量是 5，但此时长度也达到了 5，这说明当下一次 append 的时候，已经没有办法再容纳新的元素了。因为此时列表的长度、或者说元素个数已经达到了容量。当然最直观的还是这里的底层数组，很明显全都占满了。那这个时候如果想再接收新元素的话，要怎么办呢？显然只能扩容了。

原来的容量是 5，长度也是 5，当再来一个新元素的时候由于没有位置了，所以要扩容。但是扩容的时候肯定会将容量申请的大一些、即底层数组申请的长一些。

而申请的新的底层数组长度是9，那么说明列表的容量就变成了 9。然后将原来数组中的 PyObject * 按照顺序依次拷贝到新的数组里面，并让 ob_item 指向新的数组。然后将新元素设置在新数组中索引为 ob_size 的位置、即索引为 5 的位置，再将 ob_size 加 1（此时 ob_size 变成了 6）。

以上便是列表底层在扩容的时候所经历的过程。

并且通过以上几张图，我们可以得知列表在append之后地址是不变的。因为如果长度没有达到容量，那么 append 其实就是往底层数组中设置了一个新元素；如果达到容量了，那么会扩容，但扩容只是申请一个新的指针数组，然后让 ob_item 重新指向罢了。

所以底层的指针数组会变，但 PyListObject 结构体实例本身是没有变化的。因此列表执行 append, extend, pop, insert 的时候，因为是本地操作，所以它的地址是不会变化的。

下面我们再来看看列表所占的内存大小是怎么算的：

• PyObject_VAR_HEAD：24字节；

• ob_item：8 字节；

• allocated：8 字节；

所以总共 40 字节，但是不要忘记，在计算列表大小的时候，ob_item 指向的指针数组也要算在内。所以：列表的大小 = 40 + 8 * 指针数组长度(或者说列表容量)。注意是指针数组长度、或者说列表容量，可不是列表长度，因为数组一旦申请了，不管你用没用，大小就摆在那里了。就好比你租了间房子，就算不住，房租该交还是得交。

# 显然一个空数组占40个字节print([].__sizeof__())  # 40# 40 + 3 * 8 = 64print([1, 2, "x" * 1000].__sizeof__())  # 64#虽然里面有一个长度为1000的字符串#但我们说列表存放的都是指针，所以大小都是8字节#注意: 我们通过lst = [1, 2, 3]这种方式创建列表的话#不管内部元素有多少个, 其ob_size和allocated都是一样的#只有当列表在添加元素的时候，发现容量不够了才会扩容lst = list(range(10))# 40 + 10 * 8 = 120print(lst.__sizeof__())  # 120# 这个时候append一个元素lst.append(123)print(lst.__sizeof__())  # 184#我们发现大小达到了184, (184 - 40) // 8 = 18#说明扩容之后申请的数组的长度为18

所以列表的大小我们就知道是怎么来的了，以及为什么列表在通过索引定位元素的时候，时间复杂度是 O(1)。因为列表存储的都是对象的指针，不管对象有多大，其指针大小是固定的，都是 8 字节。通过索引可以瞬间计算出偏移量，从而找到对应元素的指针，而操作指针会自动操作指针所指向的内存。

print([1, 2, 3].__sizeof__())  # 64print([[1, 2, 3]].__sizeof__())  # 48

相信上面这个结果，你肯定能分析出原因。因为第一个列表中有3个指针，所以大小是40 + 24 = 64；而第二个列表中有一个指针，所以是40 + 8 = 48。用一张图来展示一下[1, 2, 3]和[[1, 2, 3]]的底层结构，看看它们之间的区别：

到此相信你已经彻底掌握列表的结构了，下面我们来分析一下列表相关操作的时间复杂度。

添加元素

假设有如下这样一个列表：

我们来看一下它在添加元素的时候，是怎么表现的。

首先添加元素有很多种方式，其中 append 方法用于向尾部追加一个元素，看一下它的底层实现。

static PyObject *list_append(PyListObject *self, PyObject *object){  //显然调用的app1是核心, 它里面实现了添加元素的逻辑//Py_RETURN_NONE是一个宏，表示返回Python中的None//因为list.append返回的就是Noneif (app1(self, object) == 0)        Py_RETURN_NONE;returnNULL;}staticintapp1(PyListObject *self, PyObject *v){  //参数self是列表，v是要添加的元素//获取列表的长度    Py_ssize_t n = PyList_GET_SIZE(self);//......//因为v作为了列表的一个元素，所以其指向的对象的引用计数要加1    Py_INCREF(v);//设置元素，原来的列表长度为n，最大索引是n - 1//那么追加的话就等于将元素设置在索引为n的地方    PyList_SET_ITEM(self, n, v);return0;}

以上就是 append 的逻辑，所谓插入、追加本质上都是先计算出索引，然后再通过索引设置元素。

如果上面的列表 append 一个 6，就会变成如下：

还是很好理解的。

添加元素除了 append，还可以使用 insert，和只能在尾部追加的 append 不同，该方法可以在任意位置插入。

staticintins1(PyListObject *self, Py_ssize_t where, PyObject *v){  /*    参数self：列表    参数where：索引    参数v：插入的值    *///i是循环变量，n则是当前列表的元素个数    Py_ssize_t i, n = Py_SIZE(self);//指向指针数组的二级指针    PyObject **items;//......//确定插入位置if (where < 0) {//如果where小于0，则加上 n//比如有6个元素，where=-1，那么会加上6，得到5//显然就是insert在索引为5的位置上         where += n;//如果吃撑了，写个 -100，加上元素的个数还是小于0if (where < 0)//那么where = 0，就在开头插入            where = 0;    }//如果where > n，那么就在索引为n的位置插入，//可元素个数为n，最大索引是n-1啊//对，所以此时就相当于appendif (where > n)        where = n;//走到这，索引就确定完了，然后是设置元素//拿到原来的二级指针，指向一个指针数组    items = self->ob_item;//然后从where处开始，把索引为i的值赋值给索引为i+1//相当于元素后移//既然是在where处插入，那么where之前的就不需要动了//所以到where处就停止了for (i = n; --i >= where; )        items[i+1] = items[i];//增加v指向的对象的引用计数，因为要被放到列表里    Py_INCREF(v);//将索引为where的值设置成v    items[where] = v;return0;}

逻辑不难理解，然后是时间复杂度。

• append：显然时间复杂度为 O(1)，只是在指定位置写入一个元素。但需要注意：如果容量不够了，那么会扩容，而扩容是一个 O(n) 操作。因此 append 最坏情况下也是一个 O(n) 操作，只不过扩容不会频繁发生，所以 append 方法的平均时间复杂度还是O(1)。

• insert：平均时间复杂度是 O(n)，因为从插入位置开始的每一个元素，都要向后移动；

• extend：这个我们没有说，但也能够猜到，它的时间复杂度和 append 是一样的；

获取元素

列表支持基于索引获取元素，这个就比较简单了。直接拿到底层的指针数组，然后基于索引获取即可，所以它是一个时间复杂度为 O(1) 的操作。

当然除了索引，还可以使用切片，只不过切片在底层仍然使用了索引。

# lst[1: 8: 3] 等价于start = 1end = 8step = 3while start < end:    item = lst[start]# .....    start += step

因此一些看似高端的操作，在底层实际上并没有那么神秘。

设置元素

我们可以获取指定索引的元素，当然也可以对其进行设置。

# 获取元素item = lst[5]# 设置元素lst[5] = item

前面说了，添加元素本质上也是通过设置元素实现的。如果列表最大索引为 n，那么 append 就等价于在 n + 1 的地方设置元素；而 insert 则是先将待插入位置后面的元素依次后移，然后再将待插入位置设置成指定的元素，本质上也是在不断地设置元素。

而设置元素的时间复杂度显然也是 O(1)，当然对一个已存在的元素进行设置，就等价于修改。

另外在设置元素的时候，除了使用索引，还可以使用切片。而在使用切片的时候非常灵活，我们通过 Python 演示一下。

lst = [1, 2, 3, 4, 5, 6, 7, 8]#首先通过切片进行设置的话#右值一定要是一个可迭代对象lst[0: 3] = [11, 22, 33]# 会将lst[0]设置为11、lst[1]设置为22、lst[2]设置为33print(lst)  # [11, 22, 33, 4, 5, 6, 7, 8]#而且它们的长度可以不相等#这里表示将[0: 3]的元素设置为[1, 2]#其中lst[0]设置成1, lst[1]设置成2#问题来了, lst[2]咋办? #由于右值中已经没有元素与之匹配了, 那么lst[2]就会被删掉lst[0: 3] = [1, 2]print(lst)  # [1, 2, 4, 5, 6, 7, 8]#所以如果想删除[0: 3]的元素，那么只需要执行lst[0: 3] = []即可#因为[]里面没有元素能与之匹配，所以lst中[0: 3]的位置由于匹配不到#那么相当于执行了删除操作，当然由于Python的动态特性，#lst[0: 3] = []、lst[0: 3] = ()、lst[0: 3] = "#都是可以的lst[0: 3] = ""print(lst)  # [5, 6, 7, 8]#实际上我们del lst[0]的时候，就是执行了lst[0: 1] = []# 当然如果右值元素多的话也是可以的lst[0: 1] = [1, 2, 3, 4]print(lst)  # [1, 2, 3, 4, 6, 7, 8]#将lst[0]设置为1很好理解, 但此时左边已经结束了#所以剩余的元素会依次插在后面#然后重点来了, 如果切片有步长的话, 那么两边一定要匹配#由于此时lst中有7个元素, lst[:: 2]会得到4个元素#那么右边的可迭代对象的长度也必须是4lst[:: 2] = ['a', 'b', 'c', 'd']print(lst)  # ['a', 2, 'b', 4, 'c', 7, 'd']# 但是，如果长度不一致try:    lst[:: 2] = ['a', 'b', 'c']except Exception as e:# 显然会报错    print(e)  # attempt to assign sequence of size 3 to extended slice of size 4

理解起来应该不难，建议去源码 listobject.c 中看一下具体实现，而在查看的时候，有以下几个函数，要牢牢地抓住。

• list_subscript：获取元素时，会调用此函数；

• list_ass_subscript：设置元素时，会调用此函数；

然后这两个函数即可以接收索引，也可以接收切片：

• 获取元素时传入的是索引，那么list_subscript内部会调用list_item；传入的是切片，那么内部会调用list_slice。

• 设置元素时传入的是索引，那么list_ass_subscript内部会调用list_ass_item；传入的是切片，那么会调用list_ass_slice。并且list_ass_slice虽然是设置元素，但删除元素也是调用的它，比如通过 lst[n:n+1]=[] 便可删除索引为n的元素。事实上remove、pop方法都只是计算出待删除元素的索引，真正的删除操作还是通过list_ass_slice来执行的。

• 另外当传入切片时，只有步长为 1，才会调用list_slice和list_ass_slice；如果步长不为1，那么就采用循环的方式逐个遍历。

以上就是 Python 在设置元素时的具体实现，虽然是设置元素，但添加和删除用的也是它。

删除元素

删除元素可以使用 pop，默认从尾部弹出元素，当然我们也可以指定索引，弹出指定的元素。

而我们说了 pop 和 del 在删除元素的时候，会调用 list_ass_slice。

lst = [1, 2, 3, 4, 5]# 修改元素，在底层相当于修改指针数组中索引为 4 的元素lst[4] = 55print(lst)"""[1, 2, 3, 4, 55]"""# 添加元素，本质上是将元素设置在索引为 5 的位置# 但我们不能执行 lst[5] = 6，因为索引越界了# 需要调用 append，由解释器帮我们设置lst.append(6)print(lst)"""[1, 2, 3, 4, 55, 6]"""# 删除索引为 3 的元素# 可以执行 del lst[3] 或者 lst.pop(3)# 但它们底层都等价于如下lst[3: 4] = []print(lst)"""[1, 2, 3, 55, 6]"""

Python 解释器是用 C 实现的，而 C 是一门很单纯的语言，所以列表的一些花里胡哨的功能回归到 C，就是一些对 C 数组的简单操作罢了。

列表的扩容

前面说过，当添加元素时，可能会发生容量不够的情况，因此列表在执行 append 和 insert 方法的时候，都会先检测列表已存储的元素个数是否已达到当前容量。一旦达到，那么要先进行扩容。

而在 list_resize 里面，它的扩容机制是这样的。

我们来验证一下：

lst = [0] * 1000# 长度和容量一致print(len(lst))print((lst.__sizeof__() - 40) // 8)"""10001000"""# 再必须提一下# 扩容是当解释器在添加元素时，发现容量不够的时候才会扩容# 而使用 lst = [...] 这种方式创建的列表# 其大小和容量是相等的# 但此时添加一个元素的话, 那么ob_size会变成1001，大于容量1000# 所以此时列表就要扩容了, 执行 list_resize# (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);# 显然 newsize 就是 1001print(1001 + (1001 >> 3) + (3if1001 < 9else6))  # 1132# append一个元素，列表扩容lst.append(123)print((lst.__sizeof__() - 40) // 8)  # 1132

结果是一样的，因为底层就是这么实现的，所以结果必须一样。只不过我们通过这种测试的方式证明了这一点，也加深了对列表的认识。

介绍完扩容，再来介绍缩容，因为列表元素个数要是远小于容量的话，也要进行缩容，否则就会出现内存浪费。那什么时候缩容呢？答案是当列表的元素个数小于容量的一半时就会缩容。

举个生活中的例子，假设你租了10间屋子用于办公，显然你要付10间屋子的房租，不管你有没有用，一旦租了肯定是要付钱的。同理底层数组也是一样，只要你申请了，不管有没有存储元素，内存已经占用了。

但有一天你用不到10间屋子了，假设要用8间或者9间，那么会让剩余的屋子闲下来。但由于退租比较麻烦，并且只闲下来一两间屋子，所以干脆就不退了，还是会付10间屋子的钱，这样没准哪天又要用的时候就不用重新租了。

对于列表也是如此，在删除元素（相当于屋子不用了）的时候，如果发现长度还没有低于容量的一半，那么也不会缩容。但反之就要缩容了，比如屋子闲了8间，也就是只需要两间屋子就足够了，那么此时肯定要退租了，闲了8间，可能会退掉6间。

lst = [0] * 1000print(len(lst))print((lst.__sizeof__() - 40) // 8)"""10001000"""# 删除500个元素, 此时长度或者说ob_size就为500lst[500:] = []# 但是ob_size还是达到了容量的一半, 所以不会缩容print(len(lst))print((lst.__sizeof__() - 40) // 8)"""5001000"""# 如果再删除一个元素的话, 那么就要进行缩容了# 因为 ob_size 变成了 499, 小于 1000 // 2# 缩容之后容量怎么算呢? 还是之前那个公式print(499 + (499 >> 3) + (3if499 < 9else6))"""567"""# 测试一下, 删除一个元素# 看看会不会按照我们期待的规则进行缩容lst.pop()print(len(lst))print((lst.__sizeof__() - 40) // 8)"""499567"""

一切都和我们想的是一样的，因为源码中就是这么写的。

最后在源码中还有一个 if 判断，就是当列表长度为 0 的时候，那么缩容之后的容量也会是 0。

lst = [0] * 1000lst[:] = []print(    len(lst), (lst.__sizeof__() - 40) // 8)  # 0 0# 如果按照之前的容量变化公式的话, 会发现结果应该是3# 但是结果是0, 就是因为多了if判断# 如果newsize是0, 就把容量也设置为0print(0 + (0 >> 3) + (3if0 < 9else6))  # 3

为什么要这么做呢？因为 Python 认为，列表长度为 0 的话，说明你不想用这个列表了，所以多余的 3 个也没有必要申请了。还以租房为例，如果你一间屋子都不用了，说明你可能不用这里的屋子办公了，因此直接全部退掉。

小结

以上就是列表的底层实现以及相关操作，这里再来总结一下。

1）列表在基于索引获取和设置元素时，时间复杂度是 O(1)，这个效率是极高的，比字典还要快一点。因为字典在基于 key 操作 value 的时候，也是先对 key 进行哈希，然后映射出一个索引，再基于索引查找。所以哈希表本质上也是一个数组。

我们看到在查找元素时，列表比字典还要快那么一点点。因为这两者在 C 的层面都是基于数组实现的，只不过列表是直接基于索引获取，而字典则需要多一步对 key 进行映射的过程。当然这两者的效率都是极高的，复杂度都是 O(1)。

2）列表可以调用 append 追加元素，它的时间复杂度也是 O(1)，只是偶尔会伴随着扩容。append 的效率也是极高的，比字典写入元素的效率还要快一点点。

列表写入 100万个元素需要 8.01ms，而字典写入 100万个键值对需要 9.97ms。当然两者单次写入没有太大区别，毕竟复杂度都是 O(1)。但列表添加元素使用的要不是 append，而是 insert，那速度就会变慢，因为它的时间复杂度是 O(n)。

3）因此，如果是基于索引操作的话，那么列表是没有任何问题的，但问题在于索引只是一个单纯的数字罢了。我们上面举的例子中，列表的索引和对应元素是相等的，但在工作中我们并不知道某个元素位于列表中的哪个位置，这个时候就只能靠遍历的方式了。

import timeimport numpy as npdeftest(count: int, value: int):"""    :param count: 循环次数    :param value: 查询的元素    :return:    """# 包含一千个随机数的列表    lst = list(np.random.randint(0, 2 ** 30, size=1000))# 基于列表构建一个字典    d = dict.fromkeys(lst)# 查询元素value是否在列表中, 循环count次, 并统计时间    t1 = time.perf_counter()for _ in range(count):        value in lst    t2 = time.perf_counter()    print("列表查询耗时:", round(t2 - t1, 2))# 查询元素value是否在字典中, 循环count次, 并统计时间    t1 = time.perf_counter()for _ in range(count):        value in d    t2 = time.perf_counter()    print("字典查询耗时:", round(t2 - t1, 2))# 分别查询一千次、一万次、十万次、二十万次test(10 ** 3, 22333)"""列表查询耗时: 0.13字典查询耗时: 0.0"""test(10 ** 4, 22333)"""列表查询耗时: 1.22字典查询耗时: 0.0"""test(10 ** 5, 22333)"""列表查询耗时: 12.68字典查询耗时: 0.01"""test(10 ** 5 * 2, 22333)"""列表查询耗时: 25.72字典查询耗时: 0.01"""

字典的查询速度非常快，从测试中我们看到，随着循环次数越来越多，列表所花费的总时间越来越长。但是字典由于查询所花费的时间极少，查询速度非常快，所以即便循环 20 万次，花费的总时间也不过才 0.01 秒左右。

此外字典还有一个特点，就是它的快不会受到数据量的影响，从含有一万个键值对的字典中查找，和从含有一千万个键值对的字典中查找，两者花费的时间几乎是没有区别的。

原因就是字典在查找元素的时候也是使用了数组的索引，而对于数组来说，基于索引查询第 0 个元素和第 100w 个元素也是没有区别的，都是 O(1)。所以字典才会这么快，并且不受数据量的影响。

但对于当前来说，列表它不是通过索引来判断元素是否存在的，而是遍历每一个元素，然后和指定的元素进行比较。此时它的复杂度就是 O(n)，因此遍历次数越多，耗时越长。

4）最后是删除元素，无论是基于索引删除，还是通过 remove 删除，时间复杂度都是 O(n)，因为涉及数据的移动或者比较。而字典仍是 O(1)，字典在删除元素的时候实际上是伪删除，只需要将对应的键值对标记为 DUMMY 即可。

以上就是列表和字典的区别，我们下一篇文章再介绍字典是怎么实现的，加深一遍印象。

长按或扫描下方二维码，免费获取 Python公开课和大佬打包整理的几百G的学习资料，内容包含但不限于Python电子书、教程、项目接单、源码等等
推荐阅读
Python 类型提示入门：让你的代码更清晰、更可靠
解锁Python高效循环技巧：告别低效代码，掌握for、while循环优化，让你的程序更快更强！
Lihil框架—其愿景是：使 Python 成为 Web 开发的主流编程语言
提升Python程序性能的7个习惯
点击 阅读原文 了解更多