Python中的字典和集合


Python标准库中的所有映射类型都是使用dict来实现的,因此他们都有一个共同的限制,即只有可散列的数据类型才可以作为映射的键,那么什么是可散列的数据类型呢?下面介绍下:
在python词汇表中,关于可散列类型的定义有这么一段话:

如果一个对象是可散列的,那么在这个对象的生命周期中,他的可散列值是不变的,而且这个对象需要实现hash()方法。另外可散列对象还要有__eq__()方法,这样才可以和别的键做比较,如果两个可散列对象的值是相等的,那么他们的散列值一定是相等的。

原子不可变数据类型(strbytes和数值类型)都是可散列类型,frozenset也是可散列的,因为根据其定义,frozonset里只能容纳可散列类型。元组的话,只有当一个元组敖汉的所有元素都是可散列类型的情况下,它才是可散列的。一般来讲,用户自定义的类型都是可散列的,散列值就是他们的id()函数返回值,所以所有这些对象在比较的时候都是不相等的。如果一个对象内部实现了__eq__方法并且在方法内部用到了这个对象的内部状态的话那么只有当所有内部状态都是不可变的情况下,这个对象才是可散列的。

处理找不到的键

当字典d[k]找不到正确的键时,Python会抛出异常,虽然我们可以使用d.get(k,default)来代替d[k],给找不到的键一个默认的返回值,但是在更新时候,效率还是很低的,在这种情况下,可以使用dict.setdefault,使用方法如下:

>>> d={}
>>> d['k1']='v1'
>>> d
{'k1': 'v1'}
>>> d.setdefault('k2','empty')
'empty'
>>> d
{'k1': 'v1', 'k2': 'empty'}
>>> d.setdefault('k1','empty')
'v1'
>>> d
{'k1': 'v1', 'k2': 'empty'}

setdefault的作用是若字典有键k则直接返回k所对应的值,若无,则让d[k]=default,然后返回default。 有时候为了方便,当某个键在映射里面不存在,我们也希望可以通过这个键读取值的时候获取一个默认值,有两种途径可以解决这个问题,一个是使用defaultdict这个类型而不是普通的dict,另一个就是自己定义一个dict的子类,实现__missing__方法。下面分别介绍下:

defaultdict方式

在实例化一个defaultdict的时候,需要给构造方法提供一个可调用的对象,这个可调用对象会在__getitem__找不到键的时候调用,如下所示:

>>> import collections
>>> d=collections.defaultdict(list)
>>> d
defaultdict(<class 'list'>, {})
>>> d['key']
[]
>>> d
defaultdict(<class 'list'>, {'key': []})
>>> d['k1']=[1,2]
>>> d
defaultdict(<class 'list'>, {'key': [], 'k1': [1, 2]})
>>> d['k3']
[]
>>> d
defaultdict(<class 'list'>, {'key': [], 'k1': [1, 2], 'k3': []})

在当键'key'dd中不存在的时候,表达式d['key']会按照以下的步骤来处理:

  • 调用list()来建立一个新列表
  • 把这个新列表作为值,'key'作为键,放在d中
  • 返回这个列表的引用

如果在创建defautdict的时候,没有指定default_factory ,查询不到的键会触发KeyError.

特殊方法__missing__

所有映射类型在处理找不到的键时候,都会牵扯到__missing__方法,__missing__方法只会被__getitem__调用,提供__missing__方法对get或者__contains__这些方法的使用没有影响。

其他类型的字典

标准库中的collections模块中,除了defaultdict还有别的不同的映射类型,下面简单介绍下。

  • collections.OrderedDict
    这个类型在添加键的时候会保持顺序,因此键的迭代次序总是一致的。
  • collections.ChainMap
    这个类型可以容纳数个不同的映射对象,然后在进行键查找操作时候,这些对象会被当作一个整体被逐个查找,直到键被找到位置。
  • collections.Counter
    这个映射类型会给键准备一个证书计数器,每次更新一个键的时候都会增加这个计数器。
  • collections.UserDict
    这个类其实就是把标准dict用纯Python又实现了一遍,这个类型主要是让用户继承写子类的。

集合

集合的本质是许多唯一对象的聚集,因此,集合经常被用来去重。另外,集合还实现了许多基础的中缀运算符,比如给的两个集合a和b,a|b返回他们的合集,a&b返回他们的交集,而a-b返回他们的差集。

字典中的散列表

散列表其实是一个稀疏数组(总是有空白元素的数组成为稀疏数组)。三列表的单元通常称为表元。在dict的散列表中,每个键值对都占用一个表元,每个表元都有两部分,一个是对键的引用,另一个是对值的引用,因为所有表元的大小一致,因此可以通过偏移量来读取某个表元。

散列表算法

为了获取dict[key]背后的值,Python首先会调用hash(key)来计算key的散列值,把这个值最低的几位作为偏移量,在散列表中查找表元,若找到的表元为空的,则抛出KeyError异常,若不是空的,则表元里会有一对found_key:found_value,这时候python会检查key==found_key是否为真,如果相等的情况下,会返回found_value. 如果keyfound_key不相等的话,这种情况称为散列冲突,解决这种方法是算法会在散列值上另外再取几位,然后用特殊的方法处理下,把新得到的数字再当作索引来查找表元。

dict的实现及其导致的结果

下面介绍下使用散列表给dict带来的优势和限制。

  • 键必须是可散列的 一个可散列的对象必须满足以下几个条件:
    • 支持hash()函数,并且通过__hash__()方法所得到的散列值是不变的。
    • 支持__eq__()方法来检测相等性。
    • a==b为真,则hash(a)==hash(b)也为真。
  • 字典在内存开销巨大
    由于字典使用散列表,而散列表又必须是稀疏的,这导致在空间上效率低下。
  • 键查询很快。
  • 键的次序取决于添加次序。
  • 字典添加新键可能会改变已有的键的顺序。
    如果在迭代一个字典所有键的同时对字典进行修改,那么循环可能会跳过一些键,甚至是跳过字典中已有的键。