python的内置类型(3)---字典和集合

文章目录

• • • 1. 字典集合简介
    • 2. 字典常用的内置函数
    • 3. 集合常用的内置函数
    • 4. 字典的排序
    • 5. 插入 查找 删除操作

1. 字典集合简介

• 字典是一系列无序元素的组合，其长度大小可变，元素可以任意地删减和改变。这里的元素，是一对键（key）和值（value）的配对。
• 相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。
• 而集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合。

• 集合并不支持索引操作，因为集合本质上是一个哈希表，和列表不一样

2. 字典常用的内置函数

方法	说明
dict代表字典对象
dict.clear()	清空字典
dict.pop(key)	移除键，同时返回此键所对应的值(字典是无序的,随机移除,慎用)
dict.copy()	返回字典D的副本,只复制一层(浅拷贝)
dict.update(D2)	将字典 D2 合并到D中，如果键相同，则此键的值取D2的值作为新值
dict.get(key, default=None)	返回键key所对应的值,如果没有此键，则返回default
dict.keys()	返回可迭代的 dict_keys 集合对象
dict.values()	返回可迭代的 dict_values 值对象
dict.items()	返回可迭代的 dict_items 对象

3. 集合常用的内置函数

方法	说明
S表示集合对象
S.add(e)	在集合中添加一个新的元素e；如果元素已经存在，则不添加
S.remove(e)	从集合中删除一个元素，如果元素不存在于集合中，则会产生一个KeyError错误
S.discard(e)	从集合S中移除一个元素e,在元素e不存在时什么都不做;
S.clear()	清空集合内的所有元素
S.copy()	将集合进行一次浅拷贝
S.pop()	从集合S中删除一个随机元素;如果此集合为空，则引发KeyError异常
S.update(s2)	等同于 S l= s2, 用 S与s2得到的全集更新变量S
S.difference(s2)	S - s2 补集运算，返回存在于在S中，但不在s2中的所有元素的集合
S.difference_update(s2)	等同于 S -= s2
S.intersection(s2)	等同于 S & s2
S.intersection_update(s2)	等同于S &= s2
S.isdisjoint(s2)	如果S与s2交集为空返回True,非空则返回False
S.issubset(s2)	如果S与s2交集为非空返回True,空则返回False
S.issuperset(…)	如果S为s2的超集返回True,否则返回False
S.symmetric_difference(s2)	返回对称补集, 等同于 S ^ s2
S.symmetric_difference_update(s2)	等同于 S ^= s2, 用 S 与 s2 的对称补集更新 S
S.union(s2)	生成 S 与 s2的全集, 等同于 S += S2

4. 字典的排序

可以参考我的另一篇文章:

python中sort排序与sorted排序(列表 字典排序)

5. 插入 查找 删除操作

• 插入操作

  每次向字典或集合插入一个元素时，Python会首先计算键的哈希值（hash(key)），再和 mask =PyDicMinSize - 1做与操作，计算这个元素应该插入哈希表的位置index = hash(key) & mask。如果哈希表中此位置是空的，那么这个元素就会被插入其中。而如果此位置已被占用，Python便会比较两个元素的哈希值和键是否相等。若两者都相等，则表明这个元素已经存在，如果值不同，则更新值。若两者中有一个不相等，这种情况我们通常称为哈希冲突（hash collision），意思是两个元素的键不相等，但是哈希值相等。这种情况下，Python便会继续寻找表中空余的位置，直到找到位置为止。

  值得一提的是，通常来说，遇到这种情况，最简单的方式是线性寻找，即从这个位置开始，挨个往后寻找空位。当然，Python内部对此进行了优化让这个步骤更加高效。

• 查找操作

  查找操作和前面的插入操作类似，Python会根据哈希值，找到其应该处于的位置；然后，比较哈希表这个位置中元素的哈希值和键，与需要查找的元素是否相等。如果相等，则直接返回；如果不等，则继续查找，直到找到空位或者抛出异常为止。

• 删除操作

  删除操作对于删除操作，Python会暂时对这个位置的元素，赋于一个特殊的值，等到重新调整哈希表的大小时，再将其删除。不难理解，哈希冲突的发生，往往会降低字典和集合操作的速度。因此，为了保证其高效性，字典和集合内的哈希表，通常会保证其至少留有1/3的剩余空间。随着元素的不停插入，当剩余空间小于1/3时，Python会重新获取更大的内存空间，扩充哈希表。不过，这种情况下，表内所有的元素位置都会被重新排放。虽然哈希冲突和哈希表大小的调整，都会导致速度减缓，但是这种情况发生的次数极少。所以，平均情况下，这仍能保证插入、查找和删除的时间复杂度为O(1)。