「Python 进阶之路」系列 Day27写在前面Day26 讲透了dict的哈希表实现今天讲它的近亲——set。很多人知道去重要用 set但没实测过到底能快多少、为什么快也容易搞混一个细节set和dict底层都是哈希表为什么 3.7 之后dict有序了set却没有一、是什么set 是只存 key 的 dictset底层也是哈希表和 Day26 讲的dict是近亲——可以理解成只有 key、没有 value 的 dict元素本身既是数据也是key同样需要满足可哈希的条件。set结构哈希表存索引数组只存键dict结构哈希表存索引紧凑数组存键值对{[1,2],3}# TypeError: unhashable type: list —— 和dict的key一样set的元素必须可哈希二、为什么去重和成员判断为什么这么快因为set底层是哈希表判断这个元素在不在集合里不需要遍历直接用哈希值算出槽位就能判断平均时间复杂度是 O(1)而list判断元素在不在in操作、或者去重时的重复检查需要从头到尾逐个比较是 O(n)。这就是用 set 去重比用 list 去重快得多的根本原因list 去重本质是对每个新元素都做一次 O(n) 的存在性检查总体退化成 O(n²)set 去重每次检查是 O(1)总体是 O(n)。三、怎么用1. set 不保持插入顺序和 Day26 讲的dict3.7 起保证插入顺序不一样set不保证遍历顺序sset()s.add(c)s.add(a)s.add(b)print(list(s))# [a, b, c] —— 不是插入顺序 c, a, bd{}d[c]1d[a]1d[b]1print(list(d.keys()))# [c, a, b] —— dict对比一定是插入顺序Python 3.6 给dict做的紧凑字典改造哈希表只存索引数据按插入顺序存进紧凑数组并没有同步应用到set上——set的设计目标始终是集合运算和成员判断的效率不承诺、也不应该依赖它的遍历顺序。2. list 去重 vs set 去重的性能差距importtimeit data[i%1000foriinrange(20000)]# 2万个元素1000个不同值defdedup_list(data):result[]forxindata:ifxnotinresult:# O(n)的成员检查result.append(x)returnresultdefdedup_set(data):returnlist(set(data))t1timeit.timeit(lambda:dedup_list(data),number3)t2timeit.timeit(lambda:dedup_set(data),number3)# 用list去重: 0.1410s# 用set去重: 0.000480s# set快了 294 倍3. 成员判断 in 操作的性能差距big_listlist(range(100000))big_setset(range(100000))t3timeit.timeit(lambda:99999inbig_list,number1000)t4timeit.timeit(lambda:99999inbig_set,number1000)# list的in操作(1000次): 0.5266s# set的in操作(1000次): 0.000031s# set快了 16805 倍结论很明确只要涉及判断某个元素在不在一堆数据里去重、成员判断、求交并差集只要元素可哈希优先用set而不是list。4. 集合运算与 frozensetset直接支持数学集合运算底层同样利用哈希表加速a{1,2,3,4}b{3,4,5,6}print(ab)# 交集 {3, 4}print(a|b)# 并集 {1, 2, 3, 4, 5, 6}print(a-b)# 差集 {1, 2}print(a^b)# 对称差 {1, 2, 5, 6}frozensetset的不可变版本因为不可变所以本身是可哈希的——可以作为dict的 key或者作为另一个set的元素普通set做不到因为普通set本身不可哈希fsfrozenset([1,2,3])print(hash(fs))# 可以哈希d{fs:value}# 可以作为dict的keyprint(d[fs])# values{frozenset([1,2]),frozenset([3,4])}# 可以作为set的元素print(s)hash({1,2,3})# TypeError: unhashable type: set —— 普通set做不到四、面试追问Q1set 的底层实现是什么和 dict 有什么关系set底层也是哈希表可以理解成只有 key 没有 value 的 dict元素本身就是要存储和判断的数据同样要求可哈希Day26 讲的哈希表、哈希冲突相关知识对set完全适用。Q2为什么用 set 去重比用 list 去重效率高list 去重时每次都要对已收集的结果做一次 O(n) 的重复检查总体时间复杂度退化成 O(n²)set 基于哈希表判断元素是否存在是平均 O(1)总体去重是 O(n)。实测 2 万个元素去重set 比手写 list 去重快了 294 倍。Q3set 和 dict 都是哈希表实现为什么 dict 在 3.7 后有序而 set 不是dict 在 Python 3.6 做了紧凑字典改造哈希表只存指向数据的索引真正的键值对数据按插入顺序存进一个紧凑数组遍历这个数组自然就是插入顺序。这个改造没有同步应用到 set 上set 的设计目标始终是集合运算和成员判断的效率优先不保证、也不应该依赖它的遍历顺序。Q4frozenset 和 set 的区别什么时候用 frozensetfrozenset是不可变版本的set因为不可变所以本身是可哈希的能作为dict的 key 或者另一个set的元素普通set本身不可哈希做不到这两件事。需要把一个集合本身当成不可变数据来用的场景比如集合套集合、用集合本身当字典的 key就该用frozenset。Q5set 的集合运算有哪些时间复杂度如何常见运算有交集、并集|、差集-、对称差^底层都基于哈希表实现平均时间复杂度与参与运算的集合规模相关通常与较小的那个集合的大小同量级比用列表手写循环逐个判断快得多。下一篇预告Day28 讲collections模块——defaultdict、Counter、OrderedDict、namedtuple这几个高频出现的工具类各自解决了什么标准dict/tuple不够方便的问题。