写了这么多年Python回头看看每天写在代码里的东西出现频率最高的不是复杂的算法也不是花哨的设计模式而是最朴素的列表和字典。作为Python数据容器中的两大支柱列表负责按顺序装东西字典负责按名字找东西两者配合能解决绝大多数日常开发问题。很多人把它们当能存东西的箱子用会用append、会用d[key]但真正理解这两种容器的内存模型、操作成本和适用边界的人并不算多。这篇内容我想从底层实现、操作复杂度、踩坑细节和选型思路几个角度把列表和字典的艺术感拆开讲清楚。无论你是刚接触Python的新手还是写了一两年业务代码想进阶的开发者应该都能从中拿到一些可以直接用的东西。1. 列表与字典Python数据容器中最容易被低估的两个角色1.1 为什么几乎所有Python代码都离不开这两种容器先想一个问题如果你只能给初学者讲两种Python内置数据结构你会选哪两个答案大概率就是列表和字典。原因在于它们正好覆盖了人类组织信息的两种最本能的方式——按顺序排列和按名称检索。你去超市买东西手里拿着一张购物清单从上到下依次写着牛奶、面包、鸡蛋这是列表思维你翻开手机通讯录输入张三直接跳转到对应的号码这是字典思维。Python把这两种日常生活中最自然的组织方式直接做成了语言内置的类型所以你写起来才会觉得这玩意儿好像不需要学就会用。但也正因为太自然很多人反而忽略了它们背后的一整套设计逻辑。列表是一个有序的、可变的、可重复元素的序列容器。它的特点是你关心的是第几个而不是叫什么。字典则是一个基于键值映射的容器你关心的是有没有这个键以及这个键对应什么值。两者互补性极强列表适合保存有前后关系的数据比如用户操作记录、任务队列字典适合保存有唯一标识的数据比如用户ID映射到用户信息、配置名映射到配置值。我见过不少刚入门的朋友试图用列表模拟字典的查找功能做法是维护两个列表一个存名字一个存电话然后通过index()去查。这在数据量小的时候还能跑一旦数据量上来性能会迅速恶化。因为列表的查找是逐个遍历的而字典的查找是直接跳到目标位置的。理解了这个本质区别后面的很多选型问题都会变得清晰。1.2 从能装东西到装得聪明的认知升级我始终觉得容器这个词本身就透着一股哲学味道。它不只是装数据的盒子更决定了你能以什么方式访问数据、以什么代价修改数据、以什么视角理解数据。举个例子同样一批商品数据用列表存[手机, 电脑, 耳机]你知道第一件是什么但想知道手机在不在里面必须从头遍历。用字典存{phone: 手机, computer: 电脑, earphone: 耳机}你通过键可以瞬间拿到对应值但如果你想知道第几个是电脑反而要绕一圈。这就是容器带来的读写视角差异。列表擅长位置访问字典擅长键值访问。很多代码写得别扭不是因为算法不行而是因为一开始就把数据结构选错了。比如把一堆配置项存成列表然后在代码里到处写if timeout in config_list每次都是一次线性扫描完全可以用字典达到常数时间判断。所以这篇文章的核心观点先放在这里选对容器比优化代码更关键理解容器的底层机制比背API更关键。接下来的内容我会把列表和字典分别拆开从内存模型讲到操作成本再讲实战中的选型与避坑。2. 列表的底层逻辑连续内存、索引访问与可变操作的成本2.1 列表的内存模型为什么list[i]是O(1)很多人在学Python的时候会听到一个说法列表的索引访问是常数时间的。但并没有多少人真正理解为什么。其中的关键在于列表的底层实现是一个连续的内存数组数组里存的并不是对象本身而是指向对象的指针。你定义一个列表a [10, 20, 30]在内存里实际上是有一个连续的指针数组每个指针指向一个PyObject。当你执行a[1]时解释器做的事非常简单找到数组起始地址然后根据元素大小偏移一段固定距离直接取出那个位置的指针再转成Python对象。这个过程不依赖列表有多长所以时间复杂度是 O(1)。这也解释了另一个现象列表的索引不能随意越界。因为底层是固定大小的数组访问越界访问在C层面就是野指针Python为了安全会在访问前检查索引范围所以你会收到IndexError而不是读到乱码。理解连续内存模型还有一个实际意义当你需要频繁在头部插入或删除元素时列表并不合适。因为头部操作意味着所有后续元素都要向后移动一个指针的位置这是一个 O(n) 操作。一位做大数据处理的同事跟我讲过他曾经用列表存了数十万条流式数据每次都用insert(0, item)往头部塞结果程序越来越慢最后改用collection相关工具才解决。这个坑我们在后面实战部分还会详细说。2.2 append、insert、pop的复杂度差异看似相似代价不同列表提供了一堆看似很相似的操作但它们的时间复杂度完全不同。我把最常用到的几个整理成一张表操作时间复杂度说明list[i]O(1)位置访问底层指针数组偏移append(x)均摊O(1)尾部追加偶尔触发扩容insert(i, x)O(n)中间/头部插入元素整体移动pop()O(1)弹出末尾元素pop(i)O(n)弹出指定位置元素补位移动in成员判断O(n)线性遍历无哈希加速list.sort()O(n log n)原地排序Timsort算法len(list)O(1)单独维护的计数器你可能会问为什么append是均摊O(1)而不是严格O(1)这涉及列表的扩容策略。当一个列表满的时候Python会申请一块更大的内存通常扩容到当前容量的1.125倍左右然后把旧元素全部拷贝过去。这次拷贝是O(n)的。但因为扩容不是每次append都发生把多次append的总代价摊开后每次操作仍然接近于O(1)。这就是均摊常数时间的含义。我在实际写代码时有一条经验如果能提前知道列表的长度上限可以先用[None] * n预分配再从前往后赋值。这样能避免扩容带来的多次内存拷贝在大数据量场景下性能提升很明显。当然如果列表长度不确定强行预分配反而浪费直接用append就好。2.3 列表推导式的真正优势不只是语法糖谈到列表就绕不开列表推导式。很多人觉得它只是把for循环浓缩成一行是纯粹的语法糖。这么说不算错但忽略了一个更重要的点列表推导式在CPython中有专门的优化路径通常比等价的for循环加append更快。原因是列表推导式在执行过程中底层会直接为列表预分配空间并按需填装避免了循环体内反复调用append方法的开销。实测一个小例子生成100万个平方数列表推导式通常比for循环快30%到50%。这在单个操作上不算什么但如果写在热路径里累计起来就很有意义。不过列表推导式也容易被滥用。我看到有人写出几百个字符的超长推导式里面套了三四层条件读代码的人要花半天才能反应过来它在干什么。我自己的原则是推导式里的逻辑复杂度超过一个if条件时就拆回普通循环。代码是写给人读的性能优化如果牺牲了可读性那就要谨慎权衡。3. 字典的哈希世界哈希冲突、扩容与查找效率3.1 字典为什么看起来有序又不等于有序早期版本的Python字典是完全无序的遍历顺序跟插入顺序没有确定关系。但从Python 3.6开始字典的底层实现引入了一个改变——它保留了一个额外数组记录插入顺序所以你在新版本里遍历字典时顺序和插入顺序一致。这给很多人造成困惑字典不是无序的吗为什么我的遍历结果总是按插入顺序答案是字典在语义上仍然是键值映射的容器只是实现细节上碰巧保持了插入顺序。这个顺序是底层实现的副产物不是语言规范承诺的绝对保证。如果你依赖字典的插入顺序做业务逻辑短期内能跑但在不同实现或极端场景下可能出问题。真正需要有序且按键值语义访问的场景应该用OrderedDict或者直接考虑列表加字典的组合。从数据结构角度说字典的底层核心是一张哈希表具体来说CPython采用的是开放寻址法而不是链地址法。这意味着当两个键的哈希值落在同一个槽位时并不会挂一个链表而是会按照一定的探测序列去找下一个空闲槽位。这种设计的优点是内存更紧凑、缓存命中率高缺点是当哈希冲突严重时探测路径变长性能会明显下降。3.2 哈希冲突与扩容字典性能的隐性影响因素哈希表的关键指标是负载因子即已用槽位数除以总槽位数。负载因子越高冲突概率越大。CPython在负载因子达到一定阈值时会触发扩容重新分配更大的表并把已有键值对重新哈希。这里有一个值得注意的点字典的键必须是可哈希的。可哈希意味着对象有一个稳定的__hash__返回值并且这个概念不会在对象生命周期内改变。Python内置的不可变类型比如整数、字符串、元组都是可哈希的而列表、字典这些可变类型是不可哈希的。在实际工程里我见过最典型的字典性能杀手是用可变对象做key。你可能觉得用列表当key很方便d {} key [1, 2, 3] d[key] value这行代码直接报TypeError: unhashable type: list。原因很简单列表是可变的它的哈希值没法稳定——你刚把它存进去转头key.append(4)它的内容变了哈希值如果跟着变字典就再也找不到这个键了。所以Python干脆不让它哈希。比这更隐蔽的是自定义对象的哈希问题。如果你定义了一个类重写了__eq__却没重写__hash__那么在Python 3里这个对象会变成不可哈希的把它当字典键就会报错。反过来如果两个对象__eq__相等但__hash__不同它们就会在字典里同时存在违反哈希表的基本规则。这些细节在写业务代码时可能不常碰到但一旦碰到排查起来非常痛苦。我的建议是自定义对象作为字典键时务必同时重写__eq__和__hash__并且保证哈希值基于不可变字段计算。3.3 可哈希性的边界tuple也不总是安全的key说元组是可哈希的其实只说对了一半。元组的可哈希性取决于它内部元素的类型。如果一个元组里包含列表比如(1, [2, 3])那么这个元组就是不可哈希的。因为元组的哈希值需要递归计算内部元素的哈希而列表没有稳定的哈希值。我在写缓存逻辑时经常用到这个特性。比如需要把一个组合参数作为缓存的key常见的做法是拼成元组cache[(user_id, product_id)] result。这个做法在user_id和product_id是整数时完全没问题。但如果参数里混入了一个列表就必须先把列表转成元组或者用其他方式序列化否则直接报错。这里有一个实践技巧判断一个对象是否可哈希可以直接调用内置函数hash(obj)能正常返回就说明可以作为字典键。快速、省事比记文档靠谱。4. 列表与字典的实战选型从场景倒推数据结构4.1 两个核心诉求的权衡位置访问 vs 键值访问到了实战部分先问你一个很具体的问题你手里有一批用户数据每条记录有ID、姓名、年龄、城市。最合适的容器是什么如果数据量只有几百条且你只需要按顺序展示列表就够了users [{id: 1, name: A, age: 20}, ...]每次遍历即可。但随着数据量增长、查询变频繁比如用户点开详情时需要根据ID快速找到对应记录列表就要做线性扫描每次都是O(n)。这时候更合适的结构是把ID作为键、把记录字典作为值user_map {u[id]: u for u in users}这样按ID查询的时间复杂度从O(n)降到了O(1)。这个改造的代码量几乎没有增加但效果立竿见影。我在某次模拟用户行为分析的项目里把1万条用户记录的查询从5秒压到了50毫秒以内靠的就是这一行字典推导式。但我还想强调一个反向场景如果你经常需要按顺序切片、取第k个元素、翻转字典就不合适了因为它的底层是哈希表没有第k个的概念。字典的顺序只是插入顺序的副产品你无法像列表那样用下标去访问。正确的做法是列表为主必要时再辅助字典做索引。这就是为什么很多实际系统里两个容器会同时存在列表负责保持顺序字典负责加速查找。4.2 去重、计数、分组字典的经典用法字典最常见的艺术化用法在我看来有三个方向去重、计数、分组。去重的本质是利用键的唯一性。如果你想对一个列表里的元素去重同时保持原有顺序可以这样seen set() result [] for item in items: if item not in seen: seen.add(item) result.append(item)这里用的是集合集合底层其实也是哈希表可以理解为一个只有键没有值的字典。去重的核心思路是借助哈希结构把成员判断从O(n)降到O(1)从而把整个循环的复杂度从O(n²)降到O(n)。数据量一大差距就是天壤之别。我拿10万个元素的列表做过测试不去重用in判断耗时可能达到几秒用set辅助去重耗时在毫秒级。计数则是把键映射到整数频率from collections import defaultdict counter defaultdict(int) for item in items: counter[item] 1defaultdict的好处是访问不存在的键时自动用默认工厂创建一个初始值省去了if key not in counter的判断。分组类似只不过默认值从int换成了listgrouped defaultdict(list) for item in items: grouped[item.category].append(item)这三种用法几乎是字典的标准姿势我建议所有Python开发者都要熟练到不用思考。它们不涉及高级语法但对代码简洁度、运行效率的提升非常显著。4.3 嵌套数据结构的组织列表套字典还是字典套列表嵌套容器的选择是很多初学者纠结的地方。比如要存一个班级的学生信息有两种常见写法写法一是列表套字典class_students [ {name: A, score: 88}, {name: B, score: 95}, ]写法二是字典套列表class_students { A: {score: 88}, B: {score: 95}, }选哪种取决于你的主要访问模式。如果业务里经常要从头到尾遍历所有学生列表套字典更自然因为列表天然支持迭代和切片。如果业务里经常要输入名字立刻拿到某个学生的信息字典套列表或字典套字典更高效因为你可以直接class_students[A]取到不用遍历。我在实际项目里的习惯是以遍历为主用列表以按键查询为主用字典。如果两种需求都很强烈就两个都维护列表用来展示顺序字典用来加速查询两边保持同步更新。这种做法牺牲了一点代码量但换来了两个方向的极致性能。注意同步更新时容易遗漏建议封装成一个小的数据结构类把增删改查集中管理避免散落到处是list和dict的重复操作。5. 日常开发中最容易踩的坑与正确姿势5.1 可变默认参数列表当默认值的神奇bug这是一个每个Python开发者迟早会踩的经典坑。看下面这段代码def add_item(item, bucket[]): bucket.append(item) return bucket第一次调用add_item(1)返回[1]第二次调用add_item(2)你以为会得到[2]但实际得到[1, 2]。原因在于函数的默认参数只在定义时求值一次之后每次调用都复用同一个列表对象。这个列表在函数外部没有任何名字但它的生命周期贯穿整个程序导致状态在多次调用之间意外共享。这个问题在字典上同样存在def func(config{})也是同样的坑。正确的写法是在函数内部判断def add_item(item, bucketNone): if bucket is None: bucket [] bucket.append(item) return bucket这个坑之所以经典不仅是它会造成bug更重要的是它揭示了Python对象引用传递的本质默认值只是一个普通的Python对象它也有自己的身份和生命周期。写代码时只要记住一条原则——不要用可变对象做默认值就能避开80%的相关问题。5.2 浅拷贝与深拷贝嵌套容器修改的隐蔽问题列表复制也是一个高频踩坑点。看这段代码a [1, 2, 3] b a b.append(4) print(a) # [1, 2, 3, 4]b a只是把b指向了a的同一个对象所以修改b等同于修改a。如果要真正复制一份独立的列表要用a.copy()或a[:]。但这里还有一个更隐蔽的层次浅拷贝只复制外层容器内层元素仍然是引用。matrix_a [[1, 2], [3, 4]] matrix_b matrix_a.copy() matrix_b[0].append(99) print(matrix_a) # [[1, 2, 99], [3, 4]]matrix_b[0]和matrix_a[0]指向的是同一个内部列表所以修改底层的元素时原列表跟着变了。如果你希望完全独立的副本必须用深拷贝import copy matrix_c copy.deepcopy(matrix_a)深拷贝会递归复制所有嵌套对象代价是速度慢、占用内存多所以不要对任何对象都无脑deepcopy。正确的做法是先想想我到底需要共享什么、独立什么如果内层元素后续不会改动浅拷贝就够了反而更高效。5.3 字典的setdefault与defaultdict少写几十行if在字典使用中最常见的冗余代码就是判断键是否存在不存在就初始化if key not in d: d[key] [] d[key].append(value)这种行为模式可以用setdefault一行替代d.setdefault(key, []).append(value)更进一步如果整个字典绝大多数键都会执行同样的初始化逻辑直接用defaultdict更干净from collections import defaultdict d defaultdict(list) d[key].append(value)我在代码评审中看到过太多手写if判断的版本不是说不能用而是当这种模式出现三四处以上时用defaultdict会让代码的可读性和稳定性都上一个台阶。特别是涉及嵌套容器时defaultdict甚至还能搭配lambda生成多级默认结构比如defaultdict(lambda: defaultdict(list))在需要动态分组的场景非常实用。不过要提醒一句defaultdict在使用不存在的键时会自动创建条目如果你只是想查询而不想改写字典误用defaultdict会在字典里留下空条目后续遍历时会困惑。此时用d.get(key)或者普通字典更合适。6. 更进一步数据容器的性能优化思路6.1 用集合替换列表做成员判断这是我能想到的性价比最高的性能优化之一如果你只需要判断某个元素在不在此容器中用集合不要用列表。集合的成员判断是O(1)列表是O(n)。假设你有10万个元素的列表要判断1千个元素是否在其中列表版本可能要进行上亿次比较而集合版本只需要1千次哈希查找。两者的耗时差距可以到几个数量级。很多人在写数据过滤时无意识用了列表blacklist [a, b, c] if user_name in blacklist: pass如果黑名单元素不多这样写没问题。一旦黑名单涨到几千、几万每次in操作都在遍历就算只跑一次也能感知到卡顿。换成blacklist {a, b, c}立刻就舒服了。我在某个模拟推荐系统的Demo里处理过几十万条候选记录用列表做过滤时整个流程要十几秒换成集合后同样的逻辑不到一秒。这是一个字都不用改、只改数据结构的优化。6.2 排序、分组与缓存字典配合用得好的场景排序和字典看似不搭界但实际配合非常常见。比如你要按字典的值排序sorted_items sorted(d.items(), keylambda kv: kv[1], reverseTrue)这会返回一个键值对元组的列表顺序按值从大到小。很多人以为字典能直接排序其实排完的结果已经不是字典了。如果你需要保留字典的键值对应关系又需要按值排序展示这种字典转列表再排序的方式是最直接的做法。另一种应用是缓存。字典天然适合做缓存表键是输入参数值是计算结果。配合functools.lru_cache你可以把昂贵函数的入参到返回值的映射自动缓存起来。这里有一点需要保持清醒缓存的key必须可哈希。如果函数的入参是列表lru_cache会直接报错。常规解法是把列表转换成语义的不可变形式比如转成元组再传入。6.3 内存视角什么时候换用array、tuple或namedtuple列表虽然方便但在某些场景下并不是内存最省的方案。假设你要存100万个整数普通列表需要存储100万个指针加上100万个Python整数对象内存开销相当大。如果数据是纯数值且长度固定可以用array模块或者tuple来替代。tuple和list的内存差异主要体现在底层结构上tuple是不可变的所以不需要额外分配可增长的内存空间整体更紧凑同时因为它不可变可以被安全地用作字典键或者集合元素。能确定数据不会变的时候优先用tuple而不是list这是很多Python风格指南推荐的做法。namedtuple是tuple的增强版它让你通过字段名访问元素而不是靠索引。这在处理一批结构固定的记录时非常合适代码可读性比用下标取数据好很多又不需要像自定义类那样写一堆样板代码。不过namedtuple本质仍是tuple字段值不可修改如果需要可变行为还是得回到普通类或者字典。关于内存的最后一句话优化容器时不要只盯着时间也要盯内存。一个能跑但吃掉几个GB内存的程序和跑得快但内存友好的程序在生产环境中的命运完全不同。先用Python内置的sys.getsizeof看一下各个容器的基本内存占用再决定要不要换结构是我常用的第一步。写在最后的一点个人体会列表和字典真正让人着迷的地方不在于API有多丰富而在于它们用两种极简的抽象覆盖了大多数编程场景一个是顺序一个是映射。我在实际开发中反复体会到很多所谓的高性能优化其实只是把错误的容器换成了正确的容器很多难查的bug根因往往是对某个容器可变性或默认值机制的忽视。把这篇文章里的底层模型和踩坑经验消化掉你再回头写代码时对数据结构选型的判断会明显有底气。最后分享一个小技巧写代码前先花十秒钟在脑子里问自己这个数据是要按顺序访问还是按键查找这两个问题的答案往往已经决定了你该用列表还是字典。
写了这么多年Python回头看看每天写在代码里的东西出现频率最高的不是复杂的算法也不是花哨的设计模式而是最朴素的列表和字典。作为Python数据容器中的两大支柱列表负责按顺序装东西字典负责按名字找东西两者配合能解决绝大多数日常开发问题。很多人把它们当能存东西的箱子用会用append、会用d[key]但真正理解这两种容器的内存模型、操作成本和适用边界的人并不算多。这篇内容我想从底层实现、操作复杂度、踩坑细节和选型思路几个角度把列表和字典的艺术感拆开讲清楚。无论你是刚接触Python的新手还是写了一两年业务代码想进阶的开发者应该都能从中拿到一些可以直接用的东西。1. 列表与字典Python数据容器中最容易被低估的两个角色1.1 为什么几乎所有Python代码都离不开这两种容器先想一个问题如果你只能给初学者讲两种Python内置数据结构你会选哪两个答案大概率就是列表和字典。原因在于它们正好覆盖了人类组织信息的两种最本能的方式——按顺序排列和按名称检索。你去超市买东西手里拿着一张购物清单从上到下依次写着牛奶、面包、鸡蛋这是列表思维你翻开手机通讯录输入张三直接跳转到对应的号码这是字典思维。Python把这两种日常生活中最自然的组织方式直接做成了语言内置的类型所以你写起来才会觉得这玩意儿好像不需要学就会用。但也正因为太自然很多人反而忽略了它们背后的一整套设计逻辑。列表是一个有序的、可变的、可重复元素的序列容器。它的特点是你关心的是第几个而不是叫什么。字典则是一个基于键值映射的容器你关心的是有没有这个键以及这个键对应什么值。两者互补性极强列表适合保存有前后关系的数据比如用户操作记录、任务队列字典适合保存有唯一标识的数据比如用户ID映射到用户信息、配置名映射到配置值。我见过不少刚入门的朋友试图用列表模拟字典的查找功能做法是维护两个列表一个存名字一个存电话然后通过index()去查。这在数据量小的时候还能跑一旦数据量上来性能会迅速恶化。因为列表的查找是逐个遍历的而字典的查找是直接跳到目标位置的。理解了这个本质区别后面的很多选型问题都会变得清晰。1.2 从能装东西到装得聪明的认知升级我始终觉得容器这个词本身就透着一股哲学味道。它不只是装数据的盒子更决定了你能以什么方式访问数据、以什么代价修改数据、以什么视角理解数据。举个例子同样一批商品数据用列表存[手机, 电脑, 耳机]你知道第一件是什么但想知道手机在不在里面必须从头遍历。用字典存{phone: 手机, computer: 电脑, earphone: 耳机}你通过键可以瞬间拿到对应值但如果你想知道第几个是电脑反而要绕一圈。这就是容器带来的读写视角差异。列表擅长位置访问字典擅长键值访问。很多代码写得别扭不是因为算法不行而是因为一开始就把数据结构选错了。比如把一堆配置项存成列表然后在代码里到处写if timeout in config_list每次都是一次线性扫描完全可以用字典达到常数时间判断。所以这篇文章的核心观点先放在这里选对容器比优化代码更关键理解容器的底层机制比背API更关键。接下来的内容我会把列表和字典分别拆开从内存模型讲到操作成本再讲实战中的选型与避坑。2. 列表的底层逻辑连续内存、索引访问与可变操作的成本2.1 列表的内存模型为什么list[i]是O(1)很多人在学Python的时候会听到一个说法列表的索引访问是常数时间的。但并没有多少人真正理解为什么。其中的关键在于列表的底层实现是一个连续的内存数组数组里存的并不是对象本身而是指向对象的指针。你定义一个列表a [10, 20, 30]在内存里实际上是有一个连续的指针数组每个指针指向一个PyObject。当你执行a[1]时解释器做的事非常简单找到数组起始地址然后根据元素大小偏移一段固定距离直接取出那个位置的指针再转成Python对象。这个过程不依赖列表有多长所以时间复杂度是 O(1)。这也解释了另一个现象列表的索引不能随意越界。因为底层是固定大小的数组访问越界访问在C层面就是野指针Python为了安全会在访问前检查索引范围所以你会收到IndexError而不是读到乱码。理解连续内存模型还有一个实际意义当你需要频繁在头部插入或删除元素时列表并不合适。因为头部操作意味着所有后续元素都要向后移动一个指针的位置这是一个 O(n) 操作。一位做大数据处理的同事跟我讲过他曾经用列表存了数十万条流式数据每次都用insert(0, item)往头部塞结果程序越来越慢最后改用collection相关工具才解决。这个坑我们在后面实战部分还会详细说。2.2 append、insert、pop的复杂度差异看似相似代价不同列表提供了一堆看似很相似的操作但它们的时间复杂度完全不同。我把最常用到的几个整理成一张表操作时间复杂度说明list[i]O(1)位置访问底层指针数组偏移append(x)均摊O(1)尾部追加偶尔触发扩容insert(i, x)O(n)中间/头部插入元素整体移动pop()O(1)弹出末尾元素pop(i)O(n)弹出指定位置元素补位移动in成员判断O(n)线性遍历无哈希加速list.sort()O(n log n)原地排序Timsort算法len(list)O(1)单独维护的计数器你可能会问为什么append是均摊O(1)而不是严格O(1)这涉及列表的扩容策略。当一个列表满的时候Python会申请一块更大的内存通常扩容到当前容量的1.125倍左右然后把旧元素全部拷贝过去。这次拷贝是O(n)的。但因为扩容不是每次append都发生把多次append的总代价摊开后每次操作仍然接近于O(1)。这就是均摊常数时间的含义。我在实际写代码时有一条经验如果能提前知道列表的长度上限可以先用[None] * n预分配再从前往后赋值。这样能避免扩容带来的多次内存拷贝在大数据量场景下性能提升很明显。当然如果列表长度不确定强行预分配反而浪费直接用append就好。2.3 列表推导式的真正优势不只是语法糖谈到列表就绕不开列表推导式。很多人觉得它只是把for循环浓缩成一行是纯粹的语法糖。这么说不算错但忽略了一个更重要的点列表推导式在CPython中有专门的优化路径通常比等价的for循环加append更快。原因是列表推导式在执行过程中底层会直接为列表预分配空间并按需填装避免了循环体内反复调用append方法的开销。实测一个小例子生成100万个平方数列表推导式通常比for循环快30%到50%。这在单个操作上不算什么但如果写在热路径里累计起来就很有意义。不过列表推导式也容易被滥用。我看到有人写出几百个字符的超长推导式里面套了三四层条件读代码的人要花半天才能反应过来它在干什么。我自己的原则是推导式里的逻辑复杂度超过一个if条件时就拆回普通循环。代码是写给人读的性能优化如果牺牲了可读性那就要谨慎权衡。3. 字典的哈希世界哈希冲突、扩容与查找效率3.1 字典为什么看起来有序又不等于有序早期版本的Python字典是完全无序的遍历顺序跟插入顺序没有确定关系。但从Python 3.6开始字典的底层实现引入了一个改变——它保留了一个额外数组记录插入顺序所以你在新版本里遍历字典时顺序和插入顺序一致。这给很多人造成困惑字典不是无序的吗为什么我的遍历结果总是按插入顺序答案是字典在语义上仍然是键值映射的容器只是实现细节上碰巧保持了插入顺序。这个顺序是底层实现的副产物不是语言规范承诺的绝对保证。如果你依赖字典的插入顺序做业务逻辑短期内能跑但在不同实现或极端场景下可能出问题。真正需要有序且按键值语义访问的场景应该用OrderedDict或者直接考虑列表加字典的组合。从数据结构角度说字典的底层核心是一张哈希表具体来说CPython采用的是开放寻址法而不是链地址法。这意味着当两个键的哈希值落在同一个槽位时并不会挂一个链表而是会按照一定的探测序列去找下一个空闲槽位。这种设计的优点是内存更紧凑、缓存命中率高缺点是当哈希冲突严重时探测路径变长性能会明显下降。3.2 哈希冲突与扩容字典性能的隐性影响因素哈希表的关键指标是负载因子即已用槽位数除以总槽位数。负载因子越高冲突概率越大。CPython在负载因子达到一定阈值时会触发扩容重新分配更大的表并把已有键值对重新哈希。这里有一个值得注意的点字典的键必须是可哈希的。可哈希意味着对象有一个稳定的__hash__返回值并且这个概念不会在对象生命周期内改变。Python内置的不可变类型比如整数、字符串、元组都是可哈希的而列表、字典这些可变类型是不可哈希的。在实际工程里我见过最典型的字典性能杀手是用可变对象做key。你可能觉得用列表当key很方便d {} key [1, 2, 3] d[key] value这行代码直接报TypeError: unhashable type: list。原因很简单列表是可变的它的哈希值没法稳定——你刚把它存进去转头key.append(4)它的内容变了哈希值如果跟着变字典就再也找不到这个键了。所以Python干脆不让它哈希。比这更隐蔽的是自定义对象的哈希问题。如果你定义了一个类重写了__eq__却没重写__hash__那么在Python 3里这个对象会变成不可哈希的把它当字典键就会报错。反过来如果两个对象__eq__相等但__hash__不同它们就会在字典里同时存在违反哈希表的基本规则。这些细节在写业务代码时可能不常碰到但一旦碰到排查起来非常痛苦。我的建议是自定义对象作为字典键时务必同时重写__eq__和__hash__并且保证哈希值基于不可变字段计算。3.3 可哈希性的边界tuple也不总是安全的key说元组是可哈希的其实只说对了一半。元组的可哈希性取决于它内部元素的类型。如果一个元组里包含列表比如(1, [2, 3])那么这个元组就是不可哈希的。因为元组的哈希值需要递归计算内部元素的哈希而列表没有稳定的哈希值。我在写缓存逻辑时经常用到这个特性。比如需要把一个组合参数作为缓存的key常见的做法是拼成元组cache[(user_id, product_id)] result。这个做法在user_id和product_id是整数时完全没问题。但如果参数里混入了一个列表就必须先把列表转成元组或者用其他方式序列化否则直接报错。这里有一个实践技巧判断一个对象是否可哈希可以直接调用内置函数hash(obj)能正常返回就说明可以作为字典键。快速、省事比记文档靠谱。4. 列表与字典的实战选型从场景倒推数据结构4.1 两个核心诉求的权衡位置访问 vs 键值访问到了实战部分先问你一个很具体的问题你手里有一批用户数据每条记录有ID、姓名、年龄、城市。最合适的容器是什么如果数据量只有几百条且你只需要按顺序展示列表就够了users [{id: 1, name: A, age: 20}, ...]每次遍历即可。但随着数据量增长、查询变频繁比如用户点开详情时需要根据ID快速找到对应记录列表就要做线性扫描每次都是O(n)。这时候更合适的结构是把ID作为键、把记录字典作为值user_map {u[id]: u for u in users}这样按ID查询的时间复杂度从O(n)降到了O(1)。这个改造的代码量几乎没有增加但效果立竿见影。我在某次模拟用户行为分析的项目里把1万条用户记录的查询从5秒压到了50毫秒以内靠的就是这一行字典推导式。但我还想强调一个反向场景如果你经常需要按顺序切片、取第k个元素、翻转字典就不合适了因为它的底层是哈希表没有第k个的概念。字典的顺序只是插入顺序的副产品你无法像列表那样用下标去访问。正确的做法是列表为主必要时再辅助字典做索引。这就是为什么很多实际系统里两个容器会同时存在列表负责保持顺序字典负责加速查找。4.2 去重、计数、分组字典的经典用法字典最常见的艺术化用法在我看来有三个方向去重、计数、分组。去重的本质是利用键的唯一性。如果你想对一个列表里的元素去重同时保持原有顺序可以这样seen set() result [] for item in items: if item not in seen: seen.add(item) result.append(item)这里用的是集合集合底层其实也是哈希表可以理解为一个只有键没有值的字典。去重的核心思路是借助哈希结构把成员判断从O(n)降到O(1)从而把整个循环的复杂度从O(n²)降到O(n)。数据量一大差距就是天壤之别。我拿10万个元素的列表做过测试不去重用in判断耗时可能达到几秒用set辅助去重耗时在毫秒级。计数则是把键映射到整数频率from collections import defaultdict counter defaultdict(int) for item in items: counter[item] 1defaultdict的好处是访问不存在的键时自动用默认工厂创建一个初始值省去了if key not in counter的判断。分组类似只不过默认值从int换成了listgrouped defaultdict(list) for item in items: grouped[item.category].append(item)这三种用法几乎是字典的标准姿势我建议所有Python开发者都要熟练到不用思考。它们不涉及高级语法但对代码简洁度、运行效率的提升非常显著。4.3 嵌套数据结构的组织列表套字典还是字典套列表嵌套容器的选择是很多初学者纠结的地方。比如要存一个班级的学生信息有两种常见写法写法一是列表套字典class_students [ {name: A, score: 88}, {name: B, score: 95}, ]写法二是字典套列表class_students { A: {score: 88}, B: {score: 95}, }选哪种取决于你的主要访问模式。如果业务里经常要从头到尾遍历所有学生列表套字典更自然因为列表天然支持迭代和切片。如果业务里经常要输入名字立刻拿到某个学生的信息字典套列表或字典套字典更高效因为你可以直接class_students[A]取到不用遍历。我在实际项目里的习惯是以遍历为主用列表以按键查询为主用字典。如果两种需求都很强烈就两个都维护列表用来展示顺序字典用来加速查询两边保持同步更新。这种做法牺牲了一点代码量但换来了两个方向的极致性能。注意同步更新时容易遗漏建议封装成一个小的数据结构类把增删改查集中管理避免散落到处是list和dict的重复操作。5. 日常开发中最容易踩的坑与正确姿势5.1 可变默认参数列表当默认值的神奇bug这是一个每个Python开发者迟早会踩的经典坑。看下面这段代码def add_item(item, bucket[]): bucket.append(item) return bucket第一次调用add_item(1)返回[1]第二次调用add_item(2)你以为会得到[2]但实际得到[1, 2]。原因在于函数的默认参数只在定义时求值一次之后每次调用都复用同一个列表对象。这个列表在函数外部没有任何名字但它的生命周期贯穿整个程序导致状态在多次调用之间意外共享。这个问题在字典上同样存在def func(config{})也是同样的坑。正确的写法是在函数内部判断def add_item(item, bucketNone): if bucket is None: bucket [] bucket.append(item) return bucket这个坑之所以经典不仅是它会造成bug更重要的是它揭示了Python对象引用传递的本质默认值只是一个普通的Python对象它也有自己的身份和生命周期。写代码时只要记住一条原则——不要用可变对象做默认值就能避开80%的相关问题。5.2 浅拷贝与深拷贝嵌套容器修改的隐蔽问题列表复制也是一个高频踩坑点。看这段代码a [1, 2, 3] b a b.append(4) print(a) # [1, 2, 3, 4]b a只是把b指向了a的同一个对象所以修改b等同于修改a。如果要真正复制一份独立的列表要用a.copy()或a[:]。但这里还有一个更隐蔽的层次浅拷贝只复制外层容器内层元素仍然是引用。matrix_a [[1, 2], [3, 4]] matrix_b matrix_a.copy() matrix_b[0].append(99) print(matrix_a) # [[1, 2, 99], [3, 4]]matrix_b[0]和matrix_a[0]指向的是同一个内部列表所以修改底层的元素时原列表跟着变了。如果你希望完全独立的副本必须用深拷贝import copy matrix_c copy.deepcopy(matrix_a)深拷贝会递归复制所有嵌套对象代价是速度慢、占用内存多所以不要对任何对象都无脑deepcopy。正确的做法是先想想我到底需要共享什么、独立什么如果内层元素后续不会改动浅拷贝就够了反而更高效。5.3 字典的setdefault与defaultdict少写几十行if在字典使用中最常见的冗余代码就是判断键是否存在不存在就初始化if key not in d: d[key] [] d[key].append(value)这种行为模式可以用setdefault一行替代d.setdefault(key, []).append(value)更进一步如果整个字典绝大多数键都会执行同样的初始化逻辑直接用defaultdict更干净from collections import defaultdict d defaultdict(list) d[key].append(value)我在代码评审中看到过太多手写if判断的版本不是说不能用而是当这种模式出现三四处以上时用defaultdict会让代码的可读性和稳定性都上一个台阶。特别是涉及嵌套容器时defaultdict甚至还能搭配lambda生成多级默认结构比如defaultdict(lambda: defaultdict(list))在需要动态分组的场景非常实用。不过要提醒一句defaultdict在使用不存在的键时会自动创建条目如果你只是想查询而不想改写字典误用defaultdict会在字典里留下空条目后续遍历时会困惑。此时用d.get(key)或者普通字典更合适。6. 更进一步数据容器的性能优化思路6.1 用集合替换列表做成员判断这是我能想到的性价比最高的性能优化之一如果你只需要判断某个元素在不在此容器中用集合不要用列表。集合的成员判断是O(1)列表是O(n)。假设你有10万个元素的列表要判断1千个元素是否在其中列表版本可能要进行上亿次比较而集合版本只需要1千次哈希查找。两者的耗时差距可以到几个数量级。很多人在写数据过滤时无意识用了列表blacklist [a, b, c] if user_name in blacklist: pass如果黑名单元素不多这样写没问题。一旦黑名单涨到几千、几万每次in操作都在遍历就算只跑一次也能感知到卡顿。换成blacklist {a, b, c}立刻就舒服了。我在某个模拟推荐系统的Demo里处理过几十万条候选记录用列表做过滤时整个流程要十几秒换成集合后同样的逻辑不到一秒。这是一个字都不用改、只改数据结构的优化。6.2 排序、分组与缓存字典配合用得好的场景排序和字典看似不搭界但实际配合非常常见。比如你要按字典的值排序sorted_items sorted(d.items(), keylambda kv: kv[1], reverseTrue)这会返回一个键值对元组的列表顺序按值从大到小。很多人以为字典能直接排序其实排完的结果已经不是字典了。如果你需要保留字典的键值对应关系又需要按值排序展示这种字典转列表再排序的方式是最直接的做法。另一种应用是缓存。字典天然适合做缓存表键是输入参数值是计算结果。配合functools.lru_cache你可以把昂贵函数的入参到返回值的映射自动缓存起来。这里有一点需要保持清醒缓存的key必须可哈希。如果函数的入参是列表lru_cache会直接报错。常规解法是把列表转换成语义的不可变形式比如转成元组再传入。6.3 内存视角什么时候换用array、tuple或namedtuple列表虽然方便但在某些场景下并不是内存最省的方案。假设你要存100万个整数普通列表需要存储100万个指针加上100万个Python整数对象内存开销相当大。如果数据是纯数值且长度固定可以用array模块或者tuple来替代。tuple和list的内存差异主要体现在底层结构上tuple是不可变的所以不需要额外分配可增长的内存空间整体更紧凑同时因为它不可变可以被安全地用作字典键或者集合元素。能确定数据不会变的时候优先用tuple而不是list这是很多Python风格指南推荐的做法。namedtuple是tuple的增强版它让你通过字段名访问元素而不是靠索引。这在处理一批结构固定的记录时非常合适代码可读性比用下标取数据好很多又不需要像自定义类那样写一堆样板代码。不过namedtuple本质仍是tuple字段值不可修改如果需要可变行为还是得回到普通类或者字典。关于内存的最后一句话优化容器时不要只盯着时间也要盯内存。一个能跑但吃掉几个GB内存的程序和跑得快但内存友好的程序在生产环境中的命运完全不同。先用Python内置的sys.getsizeof看一下各个容器的基本内存占用再决定要不要换结构是我常用的第一步。写在最后的一点个人体会列表和字典真正让人着迷的地方不在于API有多丰富而在于它们用两种极简的抽象覆盖了大多数编程场景一个是顺序一个是映射。我在实际开发中反复体会到很多所谓的高性能优化其实只是把错误的容器换成了正确的容器很多难查的bug根因往往是对某个容器可变性或默认值机制的忽视。把这篇文章里的底层模型和踩坑经验消化掉你再回头写代码时对数据结构选型的判断会明显有底气。最后分享一个小技巧写代码前先花十秒钟在脑子里问自己这个数据是要按顺序访问还是按键查找这两个问题的答案往往已经决定了你该用列表还是字典。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
