数据类型第2篇「字典和集合的原理和应用」

作者：清菡 博客：oschina、云+社区、知乎等各大平台都有。

由于微信公众号推送改为了信息流的形式，防止走丢，请给加个星标 ⭐，你就可以第一时间接收到本公众号的推送！

目录

• 一、集合
  • 1.定义个有元素的集合
  • 2.自动去重
  • 3.集合常用的五个方法
• 二、集合和字典都是无序的
• 三 、字典和集合都是无序的，在内存中是怎么存储？
  • 1.为什么说字典和集合是无序的？
  • 2.字典查找值的过程
  • 3.Python 里基础数据类型分为三大类
  • 4.为什么会出现散列冲突？
• 四、可变和不可变元素：可哈希和不可哈希
  • 1.可变类型的数据不可进行哈希运算，不可变的数据类型可进行哈希运算
  • 2.集合为什么无序？
  • 3.散列类型为什么是无序的？
• 五、性能分析

本篇文章：重点掌握集合的用法即可。

字典，大家都用得特别多，花括号包起来的，一个键一个值构成一个元素。集合和字典的表达形式是一样的。

字典和集合在 Python 中都是使用花括号进行表示的。

一、集合

1.定义个有元素的集合

set1 = {1,2,3}

集合和字典相比，集合里面只有值，没有键。

2.自动去重

集合有个比较强大的功能：自动去重。 里面不会存在重复的元素，集合最常见的应用就是对列表去重。

2.1 把字典转换成集合，再转换回字典，它会真去重

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

打印出来是集合，重复的元素自动过滤掉了。定义的时候，不管定义多少个重复元素，都自动过滤掉了。

2.2 用集合对列表去重

li = [1,1,1,2,2,2,3,3,3] # 利用集合对列表去重
li2 = list(set(li))
print(li2)

首先把列表转换成一个集合，自动把里面的重复元素给去除掉了，再转换回列表。

集合在 Python 中是用得比较少的数据类型。

3.集合常用的五个方法

集合，它里面的元素是无序的。可以修改，集合是可变类型的数据。

3.1 空集合中怎么添加元素？

add()方法，每次可以往里面添加一个数据进去。

se = set()  # 空集合
# 集合添加数据
se.add('qinghan') # 一次只能添加一个，所以只添加了一个qinghan
print(se)

3.2 删除用 remove()

集合可以添加也可以删除。删除用remove()，传入对应的元素就可以进行删除。

集合还可以做交集、并集这样的操作，这个对我们用处不大。

3.3update() 更新元素

跟字典的update()一样的。它是将一个集合更新到这个集合里面，可以往里面一次加入多个元素。

通过这个方法：

se = set()  # 空集合
se.update({111,22,33,44})
print(se)

可以一次更新进去多个元素。

看update的源码：

接收的是不定量参数，可以传一个也可以传多个。

可以往里面加元组、列表、字符串，但是一般用的时候选择用集合，将一个集合更新到原来的集合里面。

3.4clear()清空元素

还有个常用的方法：clear()清空里面所有的元素。

3.5 copy()复制元素

copy() # 做一个复制的

二、集合和字典都是无序的

Python 里面把它称作散列类型。

Python 更新到 3.7 之后，字典出现一个新的特性：3.7 之前的字典是无序的。3.7 之后字典中元素的顺序，它会按你依次添加的顺序进行保存。现在字典，里面的元素实际上是有序的。

官方文档已声明：

三 、字典和集合都是无序的，在内存中是怎么存储？

dict 与 set 实现原理是一样的，都是将实际的值放到 list 中。

唯一不同的在于 hash 函数操作的对象，对于 dict，hash 函数操作的是其 key，而对于 set 是直接操作的它的元素。

假设操作内容为 x，其作为因变量，放入 hash 函数，通过运算后取 list 的余数，转化为一个 list 的下标，此下标位置对于 set 而言用来放其本身。

而对于 dict 则是创建了两个 list，一个 list 该下表放此 key，另一个 list 中该下标对应的 value。

其中，我们把实现 set 的方式叫做 Hash Set，实现 dict 的方式叫做 Hash Map/Table（注：map 指的是通过 Key 来寻找 value 的过程）。

1.为什么说字典和集合是无序的？

1.1 字典和集合底层都是存储在列表里面

一个字典，在存储的时候，会拆分成 2 部分，会存在 2 个列表里面，一个列表存键，一个列表存值：

字典存储时的拆分

1.2 怎么通过 Key 找到对应的 Value 值呢？

字典在存储之前，做了个 Hash 操作：

Hash操作如图，图片来自网络

拿到字典的键，进行哈希操作。通过对应的哈希算法，然后得出一串数字。

拿哈希出来的值除以内存分出来的列表的长度，得到余数。这个余数当成对应元素的下标。把键和值通过下标存在列表中对应的位置。

1.3 散列类型的存储过程

散列类型的存储过程，图片来自网络

散列类型的意思就是无序的。 散列就是哈希。散列内部元素是无序的。

刚开始内存分了 12 个格子存数据，哈希后，第一个元素得出的余数是 6，有 2 个列表，会把键存在对应的列表里面，把值存在对应的 6 的位置。

散列表存储数据很松散，不像列表完整得排过来的。散列表里面是分散存储的，会把对应的键存到一个散列表里面。

查找字典中元素的时候，首先它会拿到你这个键，同样进行哈希运算。运算完毕后得出一个值，然后去散列表里面找对应的键。找到对应的键，然后比较下是不是这个键。

字典哈希的是它的键，不是它的值。集合是哈希的它的值，所以集合里面的值是不可变类型的，不能有可变类型的值。

2.字典查找值的过程

字典查找值的过程

散列值就是哈希值。拿到键名，进行哈希，哈希过后得到散列值。

拿到散列值进行相应的运算，然后拿到表元。表元是在散列表中的一个序号。

2.1 第一种情况

比如序号是 6，看 6 里面存的这个键，跟你刚才输进来查找的那个键是不是一样的。

如果是一样的，键相等，会返回表元里面对应的值，会给你找到你所存储的字典的值。

如果它在这里没找到值的话，这个时候会抛出异常。（也就是字典通过键去找值，没找到的时候就会抛出错误。）

2.2 第二种情况

散列冲突：

每个元素哈希出来的结果是不一样的。如图，第一个元素计算出来是 6，会找到散列表中第 6 个格子。第二个值，运算之后，如果得出来的也是个 6，那么这个时候就会起散列冲突。

解决散列冲突有二种方案：

方案一：

有散列冲突的时候，会对散列表进行扩容，扩容后进行重新排序。

方案二：

在后面再加个列表。这样的话，第一个元素计算出来是 6，会找到散列表中第 6 个格子。

第二个值，运算之后，如果得出来的也是个 6，因为加了一个列表（这个列表可存储多个值），就不会起散列冲突了。

以上是字典，散列类型底层存储。

3.Python 里基础数据类型分为三大类

第一类，数值类型： 1 一个数只有单个元素，像这个 1 就是 1。

第二类，序列类型： 字符串、列表、元组。

第三类，散列类型： 字典、集合。特征：内部元素是无序的。

4.为什么会出现散列冲突？

举个栗子：

这两个数据通过哈希，计算散列值，取余后拿到的余数，如果是一样的话，在储存值的时候，就会造成散列冲突。

通过字典的键去哈希，把哈希值存在散列表里面。通过对应的键，然后找到列表中存储的对应元素的值。

集合相对于列表比较简单一些。集合没有键和值，直接拿到集合里面的值进行哈希操作。

四、可变和不可变元素：可哈希和不可哈希

1.可变类型的数据不可进行哈希运算，不可变的数据类型可进行哈希运算。

集合里面只能存储可哈希的对象。意思是集合里面只能存储不可变的数据类型。

例如：set2 = {1,2,3,[1,2]}

这个集合就报错了：

因为列表是可变类型。可变类型是不能进行哈希运算的。

数值类型、字符串、元组可以，列表、字典、集合不能作为元素储存在这个集合里面。

集合里面的元素通过哈希操作算出对应值，放到散列表里面。

2.集合为什么无序？

因为散列表里面存储元素的时候是没有顺序的，散列表也是会不断变化的（会变化长度、调整元素位置的），所以说散列类型是无序的。

3.散列类型为什么是无序的？

通过哈希算法算了之后，然后存到对应的散列表里面，散列表里面数据存储是没有固定顺序的。

五、性能分析

字典最占用内存，其次是集合。然后是列表、元组。元组是占用内存最少的。但是查找元素的时候，集合是速度最快的，然后是字典。

集合用起来不方便，如果知道哪个元素就好查找，但是不知道那个元素在哪里，就不方便从集合里去取那个元素。字典通过键取值，元组、列表通过下标。