Python数据结构（三）set使用和原理

太过爱你忘了你带给我的痛 2024-04-18 22:12 63阅读 0赞

### 1. set是什么？ ###

数学上，把set称做由不同的元素组成的集合，集合（set）的成员通常被称做集合元素（set elements）。Python把这个概念引入到它的集合类型对象里。集合对象是一组无序排列的可哈希的值。集合关系测试和union、intersection等操作符在Python里也同样如我们所预想地那样工作。

### 2. set特点 ###

集合中的元素有三个特征：

1.  确定性：集合中的元素必须是确定的；
2.  互异性：集合中的元素互不相同，如：集合A=\{1，a\}，则a不能等于1）；
3.  无序性：集合中的元素没有先后之分，如：\{3,4,5\}和\{3,5,4\}算作同一个集合。

python中集合（set）是一个**无序不重复**元素的集。基本功能包括关系测试和消除重复元素，还可以计算交集、差集、并集等。它与列表(list)的行为类似，区别在于set不能包含重复的值，而且set元素是无序的。

在python中可以用大括号 `{}` 创建集合。注意：如果要创建或初始化一个空集合，你必须用 `set()` 而不是 `{}` 。因为后者`{}` 作为创建一个空的字典，以后我们会介绍字典这种数据结构。

### 3. python集合种类 ###

python集合有两种不同的类型：

*  可变集合(set)：可变集合(set)，可以添加和删除元素，
 *  不可变集合(frozenset)：不可变集合(frozenset)一旦创建就不允许更改。

根据上面两种集合可知，set是可变对象，因此既不能用做字典的键也不能做其他集合中的元素。frozenset则正好相反，它是不可变对象（这点类似python中的tuple），即它们有哈希值，能被用做字典的键或是作为集合中的一个成员。

`注意：` 上面我们说 set 是可变对象，不可哈希，是指创建的整个对象，而不是指对象中某个元素，这一点可以类比list和tuple区别。

### 4. 创建set ###

1.  创建空集合

s1 = set()  # 创建空集合
    print(s1)  # 打印空集合不是{} 而是set()，是为了和空字典区分
    print(type(s1))
    # set()
    # <class 'set'>
    
    d = { }  # 这个是创建空字典，注意区别
    print(d, type(d))
    # {} <class 'dict'>

1.  创建可变集合set

s1 = { 2, 1, 3}
    print(s1)  # 下面输出结果看出，集合是无序的
    # {1, 2, 3}
    
    s2 = { 1, 2, 3, 3}  # 虽然加入的元素有重复，但是集合自动去重
    print(s2)
    # {1, 2, 3}
    
    # 使用工厂创建集合，但是注意参数是可迭代的
    s3 = set('12aa')
    print(s3)
    # {'1', '2', 'a'}
    
    s4 = set([1, 2, 'a', 'a'])
    print(s4)
    # {1, 2, 'a'}

3.创建不可变集合frozenset

s1 = frozenset('12aa')
    print(s1)
    # frozenset({'2', 'a', '1'})
    
    s2 = frozenset([1, 2, 'a', 'a'])
    print(s2)
    # frozenset({1, 2, 'a'})

【创建集合讨论】  
根据上面代码，我们发现，创建空集合只能用`set()` ，不能用`{}` 。而且非空集合打印结果是由 `{}` 包裹起来的，前面我们学元组（tuple），它的打印结果是由 `()` 包裹起来的。另外有第二段代码可以看出集合是无序的，通过`set()` 可以把其他数据结构转换为集合，而且自动去重。

### 5. 集合遍历和访问 ###

循环遍历：

# 集合遍历使用for
    s1 = { 5, 4, 3, 2, 1}
    for x in s1:
        print(x, end=" ")
    # 1 2 3 4 5

集合没有索引，不能使用索引获取对应元素，比如使用`s[1]` 会报错，想想为什么？

s1={ 1,2,3}
    print(s1[1])
    # print(s1[1])
    # TypeError: 'set' object does not support indexing

上面代码可以看到使用索引获取元素报错，根本原因是集合是无序的，不可hash。

### 6. 集合的交并补运算 ###

<table> 
 <thead> 
  <tr> 
   <th>数学符号</th> 
   <th>Python符号</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>- 或| -</td> 
   <td>差集，相对补集</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>∩</td> 
   <td>&amp;</td> 
   <td>交集</td> 
  </tr> 
  <tr> 
   <td>∪</td> 
   <td>|</td> 
   <td>并集</td> 
  </tr> 
  <tr> 
   <td>≠</td> 
   <td>!=</td> 
   <td>不等于</td> 
  </tr> 
  <tr> 
   <td>＝</td> 
   <td>==</td> 
   <td>等于</td> 
  </tr> 
  <tr> 
   <td>∈</td> 
   <td>in</td> 
   <td>是成员关系</td> 
  </tr> 
  <tr> 
   <td>∉</td> 
   <td>not in</td> 
   <td>非成员关系</td> 
  </tr> 
 </tbody> 
</table>

**例子**

s1 = { 1, 2, 3, 4, 5}
    s2 = { 4, 5, 6, 7, 8}
    
    print(s1 - s2)  # 差集
    # {1, 2, 3}
    print(s2 - s1)
    # {8, 6, 7}
    print(s1 & s2)  # 交集
    # {4, 5}
    print(s1 | s2)  # 并集
    # {1, 2, 3, 4, 5, 6, 7, 8}
    print(s1 ^ s2)  # 交叉补集
    # {1, 2, 3, 6, 7, 8}
    
    print(6 in s1)
    # False
    print(6 not in s1)
    # True

### 7. 操作集合的函数 ###

*  len(set)：集合元素个数
 *  max(set)：返回集合元素最大值
 *  min(set)：返回集合元素最小值
 *  list(set)：将集合转换为列表
 *  del：删除集合，释放内存空间

### 8. 集合类定义的函数 ###

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>add()</td> 
   <td>为集合添加元素</td> 
  </tr> 
  <tr> 
   <td>update()</td> 
   <td>给集合添加元素</td> 
  </tr> 
  <tr> 
   <td>clear()</td> 
   <td>移除集合中的所有元素</td> 
  </tr> 
  <tr> 
   <td>copy()</td> 
   <td>拷贝一个集合</td> 
  </tr> 
  <tr> 
   <td>pop()</td> 
   <td>随机移除元素</td> 
  </tr> 
  <tr> 
   <td>remove()</td> 
   <td>移除指定元素</td> 
  </tr> 
  <tr> 
   <td>discard()</td> 
   <td>删除集合中指定的元素</td> 
  </tr> 
  <tr> 
   <td>isdisjoint()</td> 
   <td>判断两个集合是否包含相同的元素，如果没有返回 True，否则返回 False。</td> 
  </tr> 
  <tr> 
   <td>issubset()</td> 
   <td>判断指定集合是否为该方法参数集合的子集。</td> 
  </tr> 
  <tr> 
   <td>issuperset()</td> 
   <td>判断该方法的参数集合是否为指定集合的子集</td> 
  </tr> 
  <tr> 
   <td>symmetric_difference()</td> 
   <td>返回两个集合中不重复的元素集合。</td> 
  </tr> 
  <tr> 
   <td>symmetric_difference_update()</td> 
   <td>移除当前集合中在另外一个指定集合相同的元素，并将另外一个指定集合中不同的元素插入到当前集合中。</td> 
  </tr> 
  <tr> 
   <td>union()</td> 
   <td>返回两个集合的并集，等同于 |</td> 
  </tr> 
  <tr> 
   <td>difference()</td> 
   <td>返回多个集合的差集，等同于 -</td> 
  </tr> 
  <tr> 
   <td>difference_update()</td> 
   <td>移除集合中的元素，该元素在指定的集合也存在。</td> 
  </tr> 
  <tr> 
   <td>intersection()</td> 
   <td>返回集合的交集</td> 
  </tr> 
  <tr> 
   <td>intersection_update()</td> 
   <td>返回集合的交集。</td> 
  </tr> 
 </tbody> 
</table>

**例子**

s1 = { 1, 2, 3}
    s1.add(4)
    s1.add(3)  # 添加重复元素，自动去重
    print(s1)
    # {1, 2, 3, 4}
    
    s2 = { 3, 4, 5}
    s1.update(s2)
    print(s1)
    # {1, 2, 3, 4, 5}
    
    s1.remove(1)
    print(s1)
    # {2, 3, 4, 5}

### 9. 集合各种操作时间复杂度 ###

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>平均情况</th> 
   <th>最坏情况</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>x in s</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>并集 s|t</td> 
   <td>O(len(s)+len(t))</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>交集 s&amp;t</td> 
   <td>O(min(len(s), len(t))</td> 
   <td>O(len(s) * len(t))</td> 
  </tr> 
  <tr> 
   <td>差集 s-t</td> 
   <td>O(len(s))</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>s.difference_update(t)</td> 
   <td>O(len(t))</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>对称差集 s^t</td> 
   <td>O(len(s))</td> 
   <td>O(len(s) * len(t))</td> 
  </tr> 
  <tr> 
   <td>s.symmetric_difference_update(t)</td> 
   <td>O(len(t))</td> 
   <td>O(len(t) * len(s))</td> 
  </tr> 
 </tbody> 
</table>

![在这里插入图片描述][20190912180656843.png]

## 【附加阅读】 ##

### 底层实现机制，面试常见问题 ###

##### 1. 集合底层数据结构 #####

集合能如此高效，和它的内部的数据结构密不可分。不同于其他数据结构，集合的内部结构是一张哈希表：哈希表内只存储单一的元素。不了解哈希原理和特性的可网上搜索一下，以后我们也会写一些这方面内容。

##### 2. 哈希表插入数据 #####

当向集合中插入数据时，Python会根据通过 hash(valuse) 函数，计算该元素对应的哈希值。得到哈希值（例如为 hash）之后，再结合集合要存储数据的个数（例如 n），就可以得到该元素应该插入到哈希表中的位置（比如用 取模法 hash%n 方式）。

如果哈希表中此位置是空的，那么此元素就可以直接插入其中；反之，如果此位置已被其他元素占用，那么 Python 会比较这两个元素的哈希值是否相等：

**重点：**

*  如果相等，则表明该元素已经存在，再比较他们的值，不相等就进行更新；
 *  如果不相等，这种情况称为`哈希冲突`（即两个元素的键不同，但求得的哈希值相同）。这种情况下，Python 会使用`开放定址法、再哈希法`等继续寻找哈希表中空余的位置，直到找到位置。

##### 3. 哈希表查找数据 #####

在哈希表中查找数据，和插入操作类似，Python 会根据哈希值，找到该元素应该存储到哈希表中的位置，然后和该位置的元素比较元素值：

*  如果相等，则证明找到；
 *  反之，则证明当初存储该元素时，`遇到了哈希冲突，需要继续使用当初解决哈希冲突的方法进行查找，直到找到该元素或者找到空位为止。` 这里的找到空位，表示哈希表中没有存储目标元素。

##### 3. 哈希表删除元素 #####

对于删除操作，Python 会暂时对这个位置的元素赋于一个特殊的值，等到重新调整哈希表的大小时，再将其删除。

**重点：**

*  需要注意的是，`哈希冲突的发生往往会降低字典和集合操作的速度`。
 *  因此，为了保证其高效性，字典和集合内的哈希表，通常会保证其至少留有 `1/3` 的剩余空间。
 *  随着元素的不停插入，当剩余空间小于 `1/3` 时，Python 会重新获取更大的内存空间，扩充哈希表，与此同时，表内所有的元素位置都会被重新排放。

虽然哈希冲突和哈希表大小的调整，都会导致速度减缓，但是这种情况发生的次数极少。`所以，平均情况下，仍能保证插入、查找和删除的时间复杂度为 O(1)`。

##### 4. set 怎么判断两个元素是不是重复，怎么去重的？ #####

set的去重是通过两个函数`__hash__`和`__eq__`结合实现的。

*  当两个元素的哈希值不相同时，就认为这两个变量是不同的
 *  当两个元素哈希值一样时，调用`__eq__`方法，当返回值为True时认为这两个变量是同一个，应该去除一个。返回FALSE时，不去重。

[20190912180656843.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2bd225d1fac34fb0933424dae4c11b42.png