Python 内置数据结构之七（set）

---

一、集 set

1.1 约定

• set 翻译为集合
• collection 翻译为集合类型，是一个大概念

1.2 set

• 可变的 、无序的 、不重复的 元素的集合

二、set 的定义及初始化

2.1 定义

• set() -> new empty set object
• set(iterable) -> new set object
• 示例

s1 = set()
s2 = set(range(5))
s3 = set(list(range(10)))
s4 = {}   # dict
s5 = {9,10,11}   # set
s6 = {(1,2),3,'a'}
s7 = {[1],(1,),1}   # ?

示例.png

三、set 的元素

3.1 set 的元素要求必须可以 hash

3.2 目前学过的不可 hash 的类型有 list、bytearray、set

3.3 元素不可以索引

3.4 set 可迭代

四、set 增加

4.1 add(elem)

• 增加一个元素到 set 中
• 如果元素存在，什么都不做

4.2 ipdate(*others)

• 合并其他元素到 set 集合中来
• 参数 others 必须是可迭代对象

• 就地修改

  
  增加示例.png

五、set 删除

5.1 remove(elem)

• 从 set 中移除一个元素
• 元素不存在，抛出 KeyError 异常

5.2 discard(elem)

• 从 set 中移除一个元素
• 元素不存在，什么都不做

5.3 pop() -> item

• 移除并返回任意的元素
• 空集返回 KeyError 异常

5.4 clear()

• 移除所有元素

  
  删除示例.png

六、set 修改、查询

6.1 修改

• 要么删除，要么加入新的元素

6.2 查询

• 非线性结构，无法索引

6.3 遍历

• 可迭代所有元素

6.4 成员运算符

• in 和 not in 判断元素是否在 set 中
• 效率高，相当于线性结构中利用索引

七、set 成员运算符的比较

• list 和 set 的比较

lst1 = list(range(100))
lst2 = list(range(1000000))
-1 in lst1、-1 in lst2 看看效率

set1 = set(range(100))
set2 = set(range(1000000))
-1 in set1、-1 in set2 看看效率

list 和 set 比较.png

八、set 和线性结构

8.1 线性结构的查询时间复杂度是 O(n)，即随着数据规模的增大而增加耗时

8.2 set、dict 等结构，内部使用 hash 值作为 key，时间复杂度可以做到 O(1)，查询时间和数据规模无关

8.3 可 hash

• 数值型 int、float、complex
• 布尔型 True、False
• 字符串 String、bytes
• tuple
• None
• 以上都是不可变类型，成为可哈希类型，hashable

8.4 set 的元素必须是可 hash 的

九、集合

9.1 基本概念

• 全集
  所有元素的集合，例如实数集，所有实数组成的集合就是全集
• 子集 subset 和超集 superset
  一个集合 A 所有元素都在另一个集合 B，A 就是 B 的真子集，B 是 A 的真超集
• 真子集和真超集
  A 是 B 的子集，且 A 不等于 B，A 就是 B 的真子集，B 是 A 的真超集
• 并集
  多个集合合并的结果
• 交集
  多个集合的公共部分
• 差集
  集合中除去和其他集合公共部分