常用数据结构之集合

集合（set）

如果我们把一定范围的、确定的、可以区别的事物当作一个整体来看待，那么这个整体就是集合，集合中的各个事物称为集合的元素。通常，集合需要满足以下要求：

  1. 无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。

  2. 互异性：一个集合中，任何两个元素都是不相同的，即元素在集合中只能出现一次。

  3. 确定性：给定一个集合和一个任意元素，该元素要么属这个集合，要么不属于这个集合，二者必居其一，不允许有模棱两可的情况出现。

集合并不支持索引运算。另外，集合的互异性决定了集合中不能有重复元素，集合类型必然是支持in和not in成员运算的，这样就可以确定一个元素是否属于集合，也就是上面所说的集合的确定性。集合的成员运算在性能上要优于列表的成员运算，这是集合的底层存储特性决定的。

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

元素的遍历

可以通过len函数来获得集合中有多少个元素，但不能通过索引运算来遍历集合中的元素。仍然可以使用for-in循环

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

集合的运算

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

成员运算

可以通过成员运算in和not in 检查元素是否在集合中

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

二元运算

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

image-erar.png

&运算符和intersection方法的作用是完全相同的,使用运算符的方式显然更直观且代码也更简短。

集合的二元运算还可以跟赋值运算一起构成复合赋值运算，例如：

set1 |= set2相当于set1 = set1 | set2，跟|=作用相同的方法是update；

set1 &= set2相当于set1 = set1 & set2，跟&=作用相同的方法是intersection_update，

比较运算

两个集合可以用==和!=进行相等性判断，如果两个集合中的元素完全相同，那么==比较的结果就是True，否则就是False。

集合的方法

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

说明：删除元素的remove方法在元素不存在时会引发KeyError错误，所以上面的代码中我们先通过成员运算判断元素是否在集合中。

不可变集合

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

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

总结

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