5. 集合

常用数据结构之集合
在学习了列表和元组之后，我们再来学习一种容器型的数据类型，它的名字叫集合（set）。
说到集合这个词大家一定不会陌生，在数学课本上就有这个概念。如果我们把一定范围的、
确定的、可以区别的事物当作一个整体来看待，那么这个整体就是集合，集合中的各个
事物称为集合的元素。通常，集合需要满足以下要求：

无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。
互异性：一个集合中，任何两个元素都是不相同的，即元素在集合中只能出现一次。
确定性：给定一个集合和一个任意元素，该元素要么属这个集合，要么不属于这个集合，
二者必居其一，不允许有模棱两可的情况出现。
Python 程序中的集合跟数学上的集合没有什么本质区别，需要强调的是上面所说的
无序性和互异性。无序性说明集合中的元素并不像列中的元素那样存在某种次序，
可以通过索引运算就能访问任意元素，集合并不支持索引运算。另外，集合的互异性
决定了集合中不能有重复元素，这一点也是集合区别于列表的地方，我们无法将重复
的元素添加到一个集合中。集合类型必然是支持in和not in成员运算的，这样就可以
确定一个元素是否属于集合，也就是上面所说的集合的确定性。集合的成员运算在性能
上要优于列表的成员运算，这是集合的底层存储特性决定的，此处我们暂时不做讨论，
大家记住这个结论即可。

说明：集合底层使用了哈希存储（散列存储），对哈希存储不了解的读者可以先看看
“Hello 算法”网站对哈希表的讲解，感谢作者的开源精神。

创建集合
使用花括号 {} 或 set() 函数创建（空集合必须用 set()，因为 {} 表示空字典）。
字典类型我们会在下一节课中为大家介绍。
当然，也可以使用 Python 内置函数set来创建一个集合，准确的说set并不是一个函数，
而是创建集合对象的构造器，这个知识点会在后面讲解面向对象编程的地方为大家介绍。
我们可以使用set函数创建一个空集合，也可以用它将其他序列转换成集合，
例如：set('hello')会得到一个包含了4个字符的集合（重复的字符l只会在集合中出现
一次）。除了这两种方式，还可以使用生成式语法来创建集合，就像我们之前用生成式
语法创建列表那样。

python

set1 = {1, 2, 3, 3, 3, 2}
print(set1)

set2 = {'banana', 'pitaya', 'apple', 'apple', 'banana', 'grape'}
print(set2)

set3 = set('hello')
print(set3)

set4 = set([1, 2, 2, 3, 3, 3, 2, 1])
print(set4)

set5 = {num for num in range(1, 20) if num % 3 == 0 or num % 7 == 0}
print(set5)

▶ 运行结果：

输出

{1, 2, 3}
{'banana', 'apple', 'grape', 'pitaya'}
{'l', 'o', 'e', 'h'}
{1, 2, 3}
{3, 6, 7, 9, 12, 14, 15, 18}

需要提醒大家，集合中的元素必须是hashable类型，所谓hashable类型指的是能够计算出哈希码的数据类型，通常不可变类型都是hashable类型，如整数（int）、浮点小数（float）、布尔值（bool）、字符串（str）、元组（tuple）等。可变类型都不是hashable类型，因为可变类型无法计算出确定的哈希码，所以它们不能放到集合中。例如：我们不能将列表作为集合中的元素；同理，由于集合本身也是可变类型，所以集合也不能作为集合中的元素。我们可以创建出嵌套列表（列表的元素也是列表），但是我们不能创建出嵌套的集合，这一点在使用集合的时候一定要引起注意。

温馨提示：如果不理解上面提到的哈希码、哈希存储这些概念，可以先放放，因为它并不影响你继续学习和使用 Python 语言。当然，如果是计算机专业的小伙伴，不理解哈希存储是很难被原谅的，要赶紧去补课了。

元素的遍历
我们可以通过len函数来获得集合中有多少个元素，但是我们不能通过索引运算来遍历集合中的元素，因为集合元素并没有特定的顺序。当然，要实现对集合元素的遍历，我们仍然可以使用for-in循环，代码如下所示。

python

set1 = {'Python', 'C++', 'Java', 'Kotlin', 'Swift'}
for elem in set1:
    print(elem)

▶ 运行结果：

输出

Java
Swift
Kotlin
C++
Python

提示：大家看看上面代码的运行结果，通过单词输出的顺序体会一下集合的无序性。

集合的运算
Python 为集合类型提供了非常丰富的运算，主要包括：成员运算、交集运算、并集运算、差集运算、比较运算（相等性、子集、超集）等。

成员运算
可以通过成员运算in和not in检查元素是否在集合中，代码如下所示。

python

set1 = {11, 12, 13, 14, 15}
print(10 in set1)      # False
print(15 in set1)      # True
set2 = {'Python', 'Java', 'C++', 'Swift'}
print('Ruby' in set2)  # False
print('Java' in set2)  # True

▶ 运行结果：

输出

False
True
False
True

二元运算
集合的二元运算主要指集合的交集、并集、差集、对称差等运算，这些运算可以通过
运算符来实现，也可以通过集合类型的方法来实现，代码如下所示。

python

set1 = {1, 2, 3, 4, 5, 6, 7}
set2 = {2, 4, 6, 8, 10}

# 交集
# 交集是指两个集合中共同存在的元素组成的集合。数学表示为 A∩B。

print(set1 & set2)                      # {2, 4, 6}
print(set1.intersection(set2))          # {2, 4, 6}
#共同元素是 2、4、6（因为只有这些元素同时出现在两个集合中）。

# 并集
# 并集是指两个集合中所有唯一元素组成的集合（去除重复）。数学表示为A∪B。

print(set1 | set2)                      # {1, 2, 3, 4, 5, 6, 7, 8, 10}
print(set1.union(set2))                 # {1, 2, 3, 4, 5, 6, 7, 8, 10}
#合并后元素：1, 2, 3, 4, 5, 6, 7, 8, 10（元素 2、4、6 重复，但集合自动去重）。

# 差集
# 差集是指只存在于第一个集合中、但不存在于第二个集合中的元素组成的集合。
#数学表示为A−B。

print(set1 - set2)                      # {1, 3, 5, 7}
print(set1.difference(set2))            # {1, 3, 5, 7}
# 差集元素：1,3,5,7（因为这些元素在set1中，但不在set2中；元素2、4、6被移除）。

# 对称差
# 对称差是指只存在于一个集合中、但不同时存在于两个集合中的元素组成的集合
#（即并集减去交集）。数学表示为A△B 或 A⊕B。

print(set1 ^ set2)                      # {1, 3, 5, 7, 8, 10}
print(set1.symmetric_difference(set2))  # {1, 3, 5, 7, 8, 10}
# 对称差元素：1, 3, 5, 7（只在 set1 中），8, 10（只在 set2 中）；
# 交集元素 2、4、6 被排除。

▶ 运行结果：

输出

{2, 4, 6}
{2, 4, 6}
{1, 2, 3, 4, 5, 6, 7, 8, 10}
{1, 2, 3, 4, 5, 6, 7, 8, 10}
{1, 3, 5, 7}
{1, 3, 5, 7}
{1, 3, 5, 7, 8, 10}
{1, 3, 5, 7, 8, 10}

通过上面的代码可以看出，对两个集合求交集，&运算符和intersection方法的作用
是完全相同的，使用运算符的方式显然更直观且代码也更简短。需要说明的是，集合
的二元运算还可以跟赋值运算一起构成复合赋值运算，
例如：set1 |= set2相当于set1 = set1 | set2，跟|=作用相同的方法是update；
set1 &= set2相当于set1 = set1 & set2，跟&=作用相同的方法是intersection_update，
代码如下所示。

python

set1 = {1, 3, 5, 7}
set2 = {2, 4, 6}
set1 |= set2
# set1.update(set2)
print(set1)  # {1, 2, 3, 4, 5, 6, 7}
set3 = {3, 6, 9}
set1 &= set3
# set1.intersection_update(set3)
print(set1)  # {3, 6}
set2 -= set1
# set2.difference_update(set1)
print(set2)  # {2, 4}

▶ 运行结果：

输出

{1, 2, 3, 4, 5, 6, 7}
{3, 6}
{2, 4}

比较运算
两个集合可以用==和!=进行相等性判断，如果两个集合中的元素完全相同，
那么==比较的结果就是True，否则就是False。如果集合A的任意一个元素都
是集合B的元素，那么集合A称为集合B的子集，反过来也可以称B是A的超集。
如果A是B的子集且A不等于B，那么A就是B的真子集。Python 为集合类型提供
了判断子集和超集的运算符，其实就是我们非常熟悉的<、<=、>、>=这些运
算符。当然，我们也可以通过集合类型的方法issubset和issuperset来判断
集合之间的关系，代码如下所示。

python

set1 = {1, 3, 5}
set2 = {1, 2, 3, 4, 5}
set3 = {5, 4, 3, 2, 1}

print(set1 < set2)   # True
print(set1 <= set2)  # True
print(set2 < set3)   # False
print(set2 <= set3)  # True
print(set2 > set1)   # True
print(set2 == set3)  # True

print(set1.issubset(set2))    # True
print(set2.issuperset(set1))  # True

▶ 运行结果：

输出

True
True
False
True
True
True
True
True

说明：上面的代码中，set1 < set2判断set1是不是set2的真子集，set1 <= set2
判断set1是不是set2的子集，set2 > set1判断set2是不是set1的超集。当然，我
们也可以通过set1.issubset(set2)判断set1是不是set2的子集；
通过set2.issuperset(set1)判断set2是不是set1的超集。

集合的方法
刚才我们说过，Python 中的集合是可变类型，我们可以通过集合的方法向集合添
加元素或从集合中删除元素。

python

set1 = {1, 10, 100}

# 添加元素
set1.add(1000)
set1.add(10000)
print(set1)  # {1, 100, 1000, 10, 10000}

# 删除元素
set1.discard(10) # 删除指定的集合元素,元素存在时删除，不存在时无操作也不抛异常
if 100 in set1:
    set1.remove(100) # 删除的元素不存在时，会报错
print(set1)  # {1, 1000, 10000}

# 清空元素
set1.clear()
print(set1)  # set()

▶ 运行结果：

输出

{1, 100, 1000, 10, 10000}
{1, 1000, 10000}
set()

说明：删除元素的remove方法在元素不存在时会引发KeyError错误，所以上面的代码中
我们先通过成员运算判断元素是否在集合中。集合类型还有一个pop方法可以从集合中随
机删除一个元素，该方法在删除元素的同时会返回（获得）被删除的元素，而remove和
discard方法仅仅是删除元素，不会返回（获得）被删除的元素。

集合类型还有一个名为isdisjoint的方法可以判断两个集合有没有相同的元素，如果没有
相同元素，该方法返回True，否则该方法返回False，代码如下所示。

python

set1 = {'Java', 'Python', 'C++', 'Kotlin'}
set2 = {'Kotlin', 'Swift', 'Java', 'Dart'}
set3 = {'HTML', 'CSS', 'JavaScript'}
print(set1.isdisjoint(set2))  # False
print(set1.isdisjoint(set3))  # True

▶ 运行结果：

输出

False
True

不可变集合
Python 中还有一种不可变类型的集合，名字叫frozenset。set跟frozenset的区别就
如同list跟tuple的区别，frozenset由于是不可变类型，能够计算出哈希码，因此它
可以作为set中的元素。除了不能添加和删除元素，frozenset在其他方面跟set是一样
的，下面的代码简单的展示了frozenset的用法。

python

fset1 = frozenset({1, 3, 5, 7})
fset2 = frozenset(range(1, 6))
print(fset1)          # frozenset({1, 3, 5, 7})
print(fset2)          # frozenset({1, 2, 3, 4, 5})
print(fset1 & fset2)  # frozenset({1, 3, 5})
print(fset1 | fset2)  # frozenset({1, 2, 3, 4, 5, 7})
print(fset1 - fset2)  # frozenset({7})
print(fset1 < fset2)  # False

▶ 运行结果：

输出

frozenset({1, 3, 5, 7})
frozenset({1, 2, 3, 4, 5})
frozenset({1, 3, 5})
frozenset({1, 2, 3, 4, 5, 7})
frozenset({7})
False

总结
Python 中的集合类型是一种无序容器，不允许有重复运算，由于底层使用了哈希存储，
集合中的元素必须是hashable类型。集合与列表最大的区别在于集合中的元素没有顺序、
所以不能够通过索引运算访问元素、但是集合可以执行交集、并集、差集等二元运算，
也可以通过关系运算符检查两个集合是否存在超集、子集等关系。