我要评论day26 讲透了 dict 的哈希表实现，今天讲它的近亲——set。很多人知道"去重要用 set"，但没实测过到底能快多少、为什么快，也容易搞混一个细节：set 和 dict 底层都是哈希表，为什么 3.7 之后 dict 有序了，set 却没有？
一、是什么：set 是只存 key 的 dict
set 底层也是哈希表，和 day26 讲的 dict 是近亲——可以理解成"只有 key、没有 value 的 dict"，元素本身既是数据也是"key"，同样需要满足可哈希的条件。
{[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 讲的 dict（3.7 起保证插入顺序）不一样，set 不保证遍历顺序：
s = set()
s.add("c")
s.add("a")
s.add("b")
print(list(s)) # ['a', 'b', 'c'] —— 不是插入顺序 c, a, b！
d = {}
d["c"] = 1
d["a"] = 1
d["b"] = 1
print(list(d.keys())) # ['c', 'a', 'b'] —— dict对比：一定是插入顺序
python 3.6+ 给 dict 做的紧凑字典改造（哈希表只存索引，数据按插入顺序存进紧凑数组），并没有同步应用到 set 上——set 的设计目标始终是集合运算和成员判断的效率，不承诺、也不应该依赖它的遍历顺序。
2. list 去重 vs set 去重的性能差距
import timeit
data = [i % 1000 for i in range(20000)] # 2万个元素，1000个不同值
def dedup_list(data):
result = []
for x in data:
if x not in result: # o(n)的成员检查
result.append(x)
return result
def dedup_set(data):
return list(set(data))
t1 = timeit.timeit(lambda: dedup_list(data), number=3)
t2 = timeit.timeit(lambda: dedup_set(data), number=3)
# 用list去重: 0.1410s
# 用set去重: 0.000480s
# set快了 294 倍
3. 成员判断 in 操作的性能差距
big_list = list(range(100000)) big_set = set(range(100000)) t3 = timeit.timeit(lambda: 99999 in big_list, number=1000) t4 = timeit.timeit(lambda: 99999 in big_set, number=1000) # list的in操作(1000次): 0.5266s # set的in操作(1000次): 0.000031s # set快了 16805 倍
结论很明确：只要涉及"判断某个元素在不在一堆数据里"（去重、成员判断、求交并差集），只要元素可哈希，优先用 set 而不是 list。
4. 集合运算与 frozenset
set 直接支持数学集合运算，底层同样利用哈希表加速：
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
print(a & b) # 交集 {3, 4}
print(a | b) # 并集 {1, 2, 3, 4, 5, 6}
print(a - b) # 差集 {1, 2}
print(a ^ b) # 对称差 {1, 2, 5, 6}
frozenset：set 的不可变版本，因为不可变，所以本身是可哈希的——可以作为 dict 的 key，或者作为另一个 set 的元素（普通 set 做不到，因为普通 set 本身不可哈希）：
fs = frozenset([1, 2, 3])
print(hash(fs)) # 可以哈希
d = {fs: "value"} # 可以作为dict的key
print(d[fs]) # value
s = {frozenset([1, 2]), frozenset([3, 4])} # 可以作为set的元素
print(s)
hash({1, 2, 3})
# typeerror: unhashable type: 'set' —— 普通set做不到
四、面试追问
q1：set 的底层实现是什么，和 dict 有什么关系？
set 底层也是哈希表，可以理解成"只有 key 没有 value 的 dict"，元素本身就是要存储和判断的数据，同样要求可哈希，day26 讲的哈希表、哈希冲突相关知识对 set 完全适用。
q2：为什么用 set 去重比用 list 去重效率高？
list 去重时每次都要对已收集的结果做一次 o(n) 的重复检查，总体时间复杂度退化成 o(n²)；set 基于哈希表判断元素是否存在是平均 o(1)，总体去重是 o(n)。实测 2 万个元素去重，set 比手写 list 去重快了 294 倍。
q3：set 和 dict 都是哈希表实现，为什么 dict 在 3.7 后有序而 set 不是？
dict 在 python 3.6+ 做了紧凑字典改造：哈希表只存指向数据的索引，真正的键值对数据按插入顺序存进一个紧凑数组，遍历这个数组自然就是插入顺序。这个改造没有同步应用到 set 上，set 的设计目标始终是集合运算和成员判断的效率优先，不保证、也不应该依赖它的遍历顺序。
q4：frozenset 和 set 的区别，什么时候用 frozenset？
frozenset 是不可变版本的 set，因为不可变所以本身是可哈希的，能作为 dict 的 key 或者另一个 set 的元素；普通 set 本身不可哈希，做不到这两件事。需要"把一个集合本身当成不可变数据来用"的场景（比如集合套集合、用集合本身当字典的 key）就该用 frozenset。
q5：set 的集合运算有哪些，时间复杂度如何？
常见运算有交集 &、并集 |、差集 -、对称差 ^，底层都基于哈希表实现，平均时间复杂度与参与运算的集合规模相关（通常与较小的那个集合的大小同量级），比用列表手写循环逐个判断快得多。
到此这篇关于python使用set去重的操作教学与速度实测的文章就介绍到这了,更多相关python set去重内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论