python中的数据结构与算法(2):字典与集合

python数据结构:字典与集合

1. 字典是什么

字典是便于信息检索的一种数据结构,鉴于信息检索在程序中无处不在,字典的使用场景也非常广泛,包括许多 python 内部机制的实现,也依赖字典结构,比如命名空间的管理等。

检索一般是根据关键字查找与它关联的信息,这些关键字应该是固定的,否则就会使原来保存的数据失效,也就是说,关键字必须是不可变对象。当然,在具体实现上,我们知道,python 是根据是否存在 __hash__ 方法来判断一个对象是否可以作为关键字的,用户可以自行实现这个方法,但也承担相应的风险。

对于信息检索来说,效率往往是关键考虑因素。如果是一个静态字典,主要考虑的是创建和查找的效率问题,而对于更常用的动态字典来说,在其中插入和删除数据的效率也很重要。

下面,我们从使用者的角度看一下字典所需要支持的操作,然后简单讨论字典的实现技术。当然,它需要支持的操作决定了它应该采用的实现技术。


从使用者的角度,我可以梳理一下字典需要支持的操作。

1.1 创建字典

python 字典提供了多种创建方式:

# 1. 直接使用大括号
a = {'one': 1, 'two': 2, 'three': 3}

# 2. dict(**kwargs) 方式,只能使用有效的 Python 标识符作为键
a = dict(one=1, two=2, three=3)

# 3. dict(mapping, **kwargs) 方式
a = dict({'three': 3, 'one': 1, 'two': 2})

# 4. dict(iterable, **kwargs) 方式
a = dict([('two', 2), ('one', 1), ('three', 3)])
a = dict(zip(['one', 'two', 'three'], [1, 2, 3]))

# 5. 使用类方法 fromkeys(iterable[, value]),只能指定固定值,默认为None
a = dict.fromkeys(['one', 'two', 'three'])

# 6. 使用字典推导式
a = {k:v for k,v in zip(['one', 'two', 'three'], [1, 2, 3])}

1.2 检查字典对象

# 1. 检查项数
length = len(a_dict)

# 2. 判断键是否存在
if key in a_dict: pass
if key not in a_dict: pass

1.3 字典取值

# 使用键取值,如果键不存在,将抛出 KeyError 异常
value = a_dict[key]

# 使用 get 方法不会抛出 KeyError 异常,键不存在且没有指定默认值时,返回 None
value = a_dict.get(key)

1.4 修改字典内容

# 插入或修改键值
a_dict[key] = value
# 使用 setdefault 方法时,如果键已存在,会返回其值,不会修改
a_dict.setdefault(key, default_value)

# pop方法会删除该项并返回
value = a_dict.pop(key)  # 返回值
item = a_dict.popitem()  # 以元组的方式返回键值对

# 删除字典项,不存在时抛出 KeyError
del a_dict[key]

# 移除所有字典项
a_dict.clear()

# 字典间操作
b_dict = a_dict.copy()
a_dict.update(b_dict)

1.5 遍历

在处理遍历时,python 提供了一个字典视图对象,这种对象提供的是一个动态视图。也就是说,如果字典的内容发生了变化,视图也会随之变化:

# 以下方法提供的是字典视图对象
a_dict.keys()
a_dict.values()
a_dict.items()
iter(a_dict)  # 等价于 iter(a_dict.keys())

# 视图对象是动态的
>>> a = {'one': 1}
>>> keys = a.keys()
>>> keys
dict_keys(['one'])
>>> a['two'] = 2
>>> keys
dict_keys(['one', 'two'])  # 内容发生了变化


2. 字典的实现技术

2.1 基于线性表

显然,我们可以用列表来保存字典的键和关联的数据对象。

使用普通线性表时,数据检索的效率是 O(n) ,因为必须一一比对,直到找到键值,或者确定表中不存在该键值。如果我们改进结构,采用有序表,那么,通过二分法,可以以 O(logn) 的效率找到数据,是比较快的。不过,数据并不一定都可以排序,在实践中,甚至需要使用不同类型的对象作为字典的键,这时使用有序表就会遇到一些障碍。

而对数据插入和删除来说,基于线性表实现的字典在效率上是不能让人满意的。如果采用普通线性表,添加数据的时间复杂度是 O(1),删除数据则为 O(n);如果采用有序表,则插入和删除数据都是 O(n) 的时间复杂度。

线性表的另一个问题是需要连续的存储空间,对于规模较大的字典来说,也会造成一些困难。

总的来说,对于频繁变动,需要支持众多类型的键,或者规模较大的字典来说,线性表可能不是最好的选择。


2.2 基于树形结构

树形结构是检索系统的常用数据结构。它不需要连续的存储空间,可以支持大规模的数据,如果设计科学,也可以实现高效的检索和修改。

理论上说,普通二叉树可以实现平均意义上的 O(logn) 检索效率和修改效率。但这种效率是没有保证的,如果没有及时控制和调整,普通二叉树很有可能在持续的数据变动过程中发生结构退化,某个分支无限延伸,导致检索和操作效率往 O(n) 靠近。

解决结构退化问题的思路,是在数据变动过程中,不断调整其结构,使其保持相对平衡。因此,在实践中可以采用平衡二叉树,或者红黑树,从而实现稳定的 O(logn) 的检索和操作效率。

如我们所知,除了二叉树,实践中也常常使用多分支排序树,或者说 N叉树。考虑到从磁盘读取数据时,其实是按块读取的,在一个节点上存储更多数据有利于减少磁盘读写操作,因此,多分支排序树在数据库系统中得到很好的应用。比如 MySQL 的 InNoDB 引擎,采用 B+ 树作为索引结构,如果以整数字段作为索引,每个节点大约可以有 1200 个分支。

当然,python 中的字典和集合采用的并不是基于树形结构的实现,而是基于哈希表的实现,在理想情况下,可以实现 O(1) 复杂度的检索和修改。


2.3 基于哈希表

哈希表也叫散列表,本质上是一个线性表。线性表一定有一个下标区间,比如说一个可以存放 8 个元素的列表,其下标区间就是 0-7,如果我们可以设计一种函数,把字典的键映射为这个区间内的一个整数,就可以直接根据键计算得到它存储的具体位置,因而就可以实现快速访问和修改了,这个函数就是散列函数,或者哈希函数。

散列函数的设计有很多专业的研究,总的来说,它需要实现的基本性质包括:

  • 对于同一个对象,应该得到同样的散列结果;
  • 散列得到的结果范围应该尽量覆盖整个下标空间,否则就会造成空间浪费;
  • 不同键的散列结果应该在整个下标空间均匀分布,否则就会出现严重的冲突问题;
  • 函数的计算最好比较简单,从而减少计算开销;

容易发现,采用散列表技术实现字典,会有两个绕不过去的问题:

  • 第一个问题是,空间是有限的,也就是说,和列表一样,随着字典内容的增长,一定会出现空间扩展的问题;
  • 第二个问题是,由于空间是有限的,不论我们采用哪种散列技术,总是会碰到不同的键,散列结果为同一个整数的情况,也就是说,出现冲突;

对于第一个问题,python 字典采用的空间扩展策略和列表的空间扩展策略类似。当我们创建一个空字典或者很小的字典时,初始分配的存储区可以容纳 8 个元素,当存储区的使用超过 2/3 时,字典会更换更大的存储区,并把之前保存的内容重新散列到新存储里。当元素个数低于 50000 个时,新扩展的存储区是原存储区的 4 倍,超过之后则调整为 2 倍。

为什么元素个数超过 2/3 就进行扩展呢?这个问题涉及到散列表的冲突处理技术。简单地说,由于 python 采用的是内部消解技术,为保持散列表的平均检索速度接近常数,需要控制其负载因子,也就是元素占空间可存储元素数量的比重低于 0.7 到 0.75。


3. 冲突处理

哈希表一定会有哈希值冲突问题。比如说,一个可以存放 8 个元素的表,不同键计算得到的哈希值都是 5,这时该怎么处理呢?

一种解决方案是使用外部空间,叫外部消解技术。比如说,对于所有出现冲突的键值,可以统一放到外部的某个列表,检索的时候,如果发现地址为 5 的空间存储的不是需要的键,就到外部列表查找,如果外部列表也没有找到,就判定这个键不存在。或者说,我们在哈希表中不直接保存对象(或者对象的引用),而保存一个列表的引用,所有哈希值为 5 的对象(或其引用)都保存在这个列表里等。具体实现可以采用多种不同的策略。

另一种解决方案是内部消解技术,也就是说,如果出现冲突,后进来的值依然会保存在内部空间,只是存储的位置做了调整。具体的调整策略可以多种多样,比如说,直接使用下一个空地址,或者再次进行散列操作等。这样,检索键值的时候,如果原有位置存储着其它键,就按规则继续检索,直到找到,或者遇到一个未使用的空间,从而判断该键不存在。

python 字典采用的是内消解技术。

不论如何,哈希值冲突都是我们希望尽量避免的,最坏情况下,所有键值都冲突,哈希表就会退化为一个线性表,数据检索复杂度会从 O(1) 上升为 O(n)。

事实上,由于哈希表必然出现冲突,因此在安全领域,有哈希碰撞攻击的思路。通过精心构造的、哈希值一致的数据,对同一个 API 发起请求,导致服务器 CPU 都消耗在数据检索上,无法快速响应请求,从而实现 DOS 的目的。


4. 进阶字典对象

在 python 中,除了内置的字典,collections 模块还提供了另外两种常用的字典: defautdictOrderDict

defaultdict 实际上只是扩展了字典的 __missing__ 方法,支持用户提供一个 default_factory 函数,用于默认值的生成。当我们从字典取值时,如果字典没有对应的键,就会调用 __missing__ 方法,如果未定义这个方法,则直接返回 KeyError 。值得注意的是,__missing__ 方法不会被 __getitem__ 以外的方法调用,也就是说,如果我们使用 get() 函数取值,依然会返回指定的默认值或 None。

和常规字典相比,OrderDict 对象内部维护着一个根据键插入顺序排序的双向链表,新插入的元素会被放到链表的尾部,从而实现记住插入顺序的功能。不过,python3.7 版本之后,内置字典已经实现了一样的能力,并在 python3.8 版本提供了 __reversed__() 方法,因此,OrderDict 已经没什么存在的必要了。

进一步了解可以参考官方文档


5. 集合

python 提供了两种内置集合类型:setfrozenset。它们的实现技术与字典是一致的,当然,frozenset 是不可变对象,其实现不需要考虑空间扩展的问题。

fronzensetset 的关系有点类似于 tuplelist 的关系,形式上分为不可变和可变,底层技术基本一致,在实践中却往往用于完全不同的场景。

和字典不一样的地方在于,集合需要考虑数学中的集合类计算,如交集、并集、差集与对称差集等等。如果有兴趣,也可以直接查看官方文档


END

公众号:ReadingPython


发表评论

评论列表,共 0 条评论