Set 的意思是集合，在 Python 的实现中，Set 的 Key 与 Dict 的 Key 相似性相当高，也难怪一些作者认为 “Set 是 value 为空的特殊 Dict”。前面两节已经说明了 Set 元素的添加、删除等基本议题，它们都是 Set 元素操作中最接近底层的方法，在这些方法的基础上，实现了 Set 的高级特性。
为什么集合元素只能是不可变类型
我们已经知道，向 Set 中插入Key 需要两步：
- 在 table 中找到一个未用元素或者 dummy entry。
- 将 Key 设置为该 entry 的 key，完成插入。
这里隐含一个条件，即 Set 需要根据 Key 的 hash 快速定位 Key 在哈希表中的位置，所以 Key 的 hash 必须保持与它进入 table 时一致。hash 就像一个人的身份证号，一旦号码变了，系统就认为它是一个完全不同的 Key。
判断元素是否属于集合
Set 最关键的作用之一是判断元素的归属关系，如何确定一个集合中是否包含指定的 Key 呢？需要执行的是一个 lookup 函数，基本步骤为：
- 根据 Key 的 hash 定位 entry；
- 检查该 entry 的key 是否与 Key 相等；
- 不相等则继续探测链，直到探测到 key 为 NULL，即没有找到 Key。
如果在探测链结束前找到了 hash、key 都符合要求的 entry，这个 Key 就属于该集合，否则就不属于。
这个过程实际上是对 lookup 结果的解释，逻辑非常简单。
交集
首先回顾集合集的概念，对于集合 A、B：
result 是两个集合重叠部分，result 作为一个 Set，它的成员必须是即属于 A，也属于 B 的。Python 底层实现的逻辑也很朴素，依次遍历集合 A 的元素，检查其是否也存在于 B 中，将符合条件的元素 insert 到 result 集合中。
C 源码对应的 Python 代码如下：
# 结果集合，计算交集
result = set()
for k in A:
if k in B:
result.add(k)
并集
并集是指集合 A、B 包含的所有元素：
依然用 result 记录结果，Python 会遍历 A、B 的有元素，插入 result 中，由于 result 自身就是 Set，可以自动实现去重。C 底层实现对应的 Python 代码：
# 结果集合，并集
result = set()
for k in A:
result.add(k)
for k in B:
result.add(k)
差集
差集表示属于 A 但不属于 B 的集合：
result 首先是 A 的副本，在 C 中提供了 set_copy 函数实现复制。然后遍历 B 的元素，如果元素也存在于 result 中，将对应的 entry 设置为 dummy， 删除该元素。
# result 初始化为 A 的副本
result = A.copy()
for k in B:
if k in result:
result.remove(k)
总结
至此 Set 的关键特性都已经介绍完毕。Set 的底层实现可以清晰的看到，在 C 一层如何驱动 Python 的内置对象实现高级功能，这些代码几乎都可以直接翻译为 Python 实现，除了性能有损失，其他几乎没有差异。当然 C 语言的实现中也提供了一些额外的优化，这是纯 Python 实现无法比拟的，毕竟 C 层可以看到更多底层信息。
到目前为止，Python 的大多数基本类型实现都已经涉及到，Python 中实际上还有大量仅用于支持 Python 实现的内部对象，以及迭代器对象等等，在阅读代码的时候，可以清晰的感受到 Python 对面向对象技术的深度支持。
明天我会对迭代器这一常用但不太被关注的对象稍作解释，我们就可以进入下一个阶段，Python VM。
