浅析Python是如何实现集合的

楔子

有几天没有更新 Python 文章了，本次我们来聊一下 Python 的集合是怎么实现的？之前我们介绍过字典的实现原理，它底层是基于哈希表实现的，而集合也是如此。

并且字典和集合实现的哈希表是一样的，在计算哈希值、解决索引冲突等方面，两者没有任何区别。唯一的区别就是存储的 entry 不同，字典的 entry 里面包含了 key、value 和 key 的哈希值，而集合的 entry 里面只包含 key 和 key 的哈希值。

事实上，集合就类似于没有value的字典。

集合的使用场景

那么集合都有哪些用处呢？

1）去重

chars = ["a", "b", "a", "c", "c"]

print(
    list(set(chars))
)  # ['b', 'a', 'c']

再比如你需要监听一个队列，处理接收到的消息，但每一条消息都有一个编号，要保证具有相同编号的消息只能被处理一次，要怎么做呢？

显然集合此时就派上用场了，我们可以创建一个集合，每来一条消息，就检测它的编号是否在集合中。如果存在，则说明消息已经被处理过了，忽略掉；如果不存在，说明消息还没有被处理，那么就将它的编号添加到集合中，然后处理消息。

这里暂时不考虑消费失败等情况，我们假设每条消息都是能处理成功的。

2）判断某个序列是否包含指定的多个元素

data = ["S", "A", "T", "O", "R", "I"]

# 现在要判断 data 是否包含 "T"、"R" 和 "I"
# 如果使用列表的话
print(
    "T" in data and "R" in data and "I" in data
)  # True

# 显然这是比较麻烦的，于是我们可以使用集合
print(
    set(data) >= {"T", "R", "I"}
)  # True

同理，基于此方式，我们也可以检测一个字典是否包含指定的多个 key。

data = {
    "name": "satori",
    "age": 17,
    "gender": "female"
}

# 判断字典是否包含 name、age、gender 三个 key
print(
    data.keys() >= {"name", "age", "gender"}
)  # True

# 字典的 keys 方法会返回一个 dict_keys 对象
# 该对象具备集合的性质，可以直接和集合进行运算

显然对于这种需求，有了集合就方便多了。

集合的 API

然后我们来罗列一下集合支持的 API，在使用集合的时候要做到心中有数。

# 如果要创建一个空集合，那么要使用 set()
# 写成 {} 的话，解释器会认为这是一个空字典
s = {1, 2, 3}

# 添加元素，时间复杂度是 O(1)
s.add(4)
print(s)  # {1, 2, 3, 4}

# 删除指定的元素，如果元素不存在则报出 KeyError
# 时间复杂度为 O(1)
s.remove(2)
print(s)  # {1, 3, 4}

# 删除指定的元素，如果元素不存在则什么也不做
# 时间复杂度为 O(1)
s.discard(666)
print(s)  # {1, 3, 4}

# 随机弹出一个元素并返回
# 时间复杂度为 O(1)
print(s.pop())  # 1
print(s)  # {3, 4}

# 清空一个集合
s.clear()
print(s)  # set()

# 还有一些 API，但我们更推荐使用操作符的方式
# 两个集合取交集
print({1, 2} & {2, 3})  # {2}

# 两个集合取并集
print({1, 2} | {2, 3})  # {1, 2, 3}

# 两个集合取差集
# s1 - s2，返回在 s1、但不在 s2 当中的元素
print({1, 2, 3} - {2, 3, 4})  # {1}

# 两个集合取对称差集
# s1 ^ s2，返回既不在 s1、也不在 s2 当中的元素
print({1, 2, 3} ^ {2, 3, 4})  # {1, 4}

# 判断两个集合是否相等，也就是内部的元素是否完全一致
# 顺序无所谓，只比较元素是否全部相同
print({1, 2, 3} == {3, 2, 1})  # True
print({1, 2, 3} == {1, 2, 4})  # False

# 判断一个集合是否包含另一个集合的所有元素
# 假设有两个集合 s1 和 s2：
#    如果 s1 的元素都在 s2 中，那么 s2 >= s1；
#    如果 s2 的元素都在 s1 中，那么 s1 >= s2；
#    如果 s1 和元素和 s2 全部相同，那么 s1 == s2；
print({1, 2, 3} > {1, 2})  # True
print({1, 2, 3} >= {1, 2, 3})  # True

来源：https://mp.weixin.qq.com/s/ASAMuBLBbVEazyPDsdCb2A