Python中list、tuple、set、dict 的底层实现原理？

昨晚我下班在地铁上刷手机的时候，有人群里问我：Python 里 list、tuple、set、dict 这些常用的数据结构，它们底层到底是怎么实现的？我当时正好卡在地铁门口，被一堆人推着走，心想算了回头再仔细聊。现在有空，就用轻松点的口吻给你展开说说。

list 是动态数组

Python 的 list 本质上是动态数组，有点像 C 语言里 malloc 出来的一块连续内存。它不是每次 append 都现开一格，而是会预留额外空间，空间用满了再一次性扩容。扩容不是翻倍那么简单，而是按照一个增长因子来分配，这样插入效率比较平衡。

所以 list 在随机访问的时候很快（O(1)），但如果你老是 insert(0, x) 在开头插入，就会很慢，因为要整体搬动。

tuple 是只读的 list

tuple 看起来和 list 一样，只不过加了个“不许改”的限制。它底层其实还是类似数组的存储方式，但因为不可变，所以能做一些优化，比如当作字典的 key，或者放到 set 里。不可变的好处就是能参与哈希运算。

你可以把 tuple 想成一个“写死的数组”。

set 用的是哈希表

再说 set，底层用的是哈希表。它存数据的时候不按顺序，而是算 hash 值再放进去，所以查找、插入、删除的平均复杂度是 O(1)。不过 hash 冲突还是会发生，Python 的做法是开放寻址（open addressing），简单理解就是冲突了就挪到下一个空位。

所以 set 是无序的，遍历时顺序可能跟插入时完全不一样。

dict 也是哈希表

最后是 dict，原理和 set 基本一样，只不过它存的是 key-value 对。Python 3.6 之后，dict 保留了插入顺序，这是因为官方在哈希表实现里加了一个紧凑数组来保存 key 的顺序，看起来有点像链表的效果。

dict 的查找效率同样是 O(1)，但它会额外存储键和值的映射关系，占用的内存比 set 多一些。

大体上就是这样：list 和 tuple 是数组家族，set 和 dict 是哈希表家族。你要是追求顺序和下标访问，就用 list/tuple；如果要快速查找和去重，就用 set/dict。

对了，我刚说这些的时候，脑子里还在想昨晚的烤串摊，结果差点打成 “dict = 大葱+羊肉” 。

以上就是“Python中list、tuple、set、dict 的底层实现原理？”的详细内容，想要了解更多Python教程欢迎持续关注编程学习网。