天天看点

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)。