《Python编程从0到1 视频教学版》_深入Python设计的本质_3.3 散列表

【摘要】 本书摘自《Python编程从0到1 视频教学版》一书中第3章，第3节，作者是张頔。

3.3 散列表

如果希望同时获得常数时间复杂度O(1)的插入和查找性能，就需要付出额外的存储空 间代价，使用基于散列表 (hash table)的数据结构，如 Python 的内建数据结构字典 (dict) 和集合 (set)。 散列表是基于关联数组的存储结构，适合存储“键值对” (key-value pair) 数据。散列表用某种哈希函数实现对象到数组索引的映射，再辅以某种碰撞处理策略，就能以空间开销换来高效的查找、插入和删除操作。③

【学习目标】

· 了解散列结构的工作原理；

· 了解散列结构和线性结构的权衡；

· 掌 握Python 的内建结构字典和集合；

· 了解散列结构的部分应用场景；

· 了解散列表的简单实现。

3.3.1 基本原理

散列表将对象键值(“键”是对象中能够唯一标识该对象的属性，比如对于个人信息 来说身份证号码就是键①)经哈希函数 (hash function)②转换为整数与数组索引对应。散 列表工作原理，如图3.20所示。数组则用来存放对象引用。每个引用位置被称为“槽位” (slot)。 理想状况下，对象经由哈希函数计算出唯一槽位，从而实现查找、插入、删除的 O(1)时间复杂度。

然而现实是在绝大多数的情况下，哈希函数的计算结果会重叠，这被称为“哈希碰撞” (hash collision)。 综上所述，散列表的设计需要考虑两个基本问题：

· 采用何种哈希函数；

· 如何处理哈希碰撞。

前者要求设计者针对使用场景挑选合适的映射函数由键值计算数组索引值，后者用以 在计算结果重复时进行某种处理。

1. 哈希函数

Python 内建的 hash 函数可以将不可变对象映射为整数，再使用求余运算即可获得任 意整数区间的索引值。

>>> hash('abc')

9099314653799480214

>>> hash(123)

123

>>> hash('123')

1780214211919182149

>>> hash((1,2,3))

2528502973977326415

在实际应用中，往往要通过试验保证所选取的哈希策略能够均匀分布对象于各个槽位。 设计较为通用的 hash 函数超出了本书的讨论范围，那需要针对整数、浮点数和字符串分 别设计 hash 策略后再整合起来[10]。

2. 哈希碰撞

当哈希值冲突时就需要某种策略进行处理，大体方法有二：或以链表形式置于同样的 槽位(链式法),或另行计算索引值(开放寻址法)。链表法是简单地将发生哈希碰撞的 对象串成链表(简单地说，重叠了就挂在一起),如图3.21 所示。开放寻址法则需要通 过设计更复杂的哈希函数，实现为同一对象多次计算不同哈希值的目的(简单地说， 一个 位置不行就再计算一个新位置),如图3.22所示。

3. 权衡不同数据结构

“权衡” (trade-off) 是工程师在处理问题时面临的取舍抉择问题，为了某种性能而放 弃另一种性能。以数据的查找为例：如果没有时间性能限制，可以使用无序数组存放数据， 在付出 O(n)的查找和删除复杂度的同时，获得了最节省空间的存储方案；如果存储容量 非常宽裕，则可以使用散列表，在付出足够大的空间复杂度后获得 O(1)的查找、插入和删除时间复杂度。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。