4.9 【大牛讲坛】算法进阶，字典和集合背后的秘密

数据结构和Python里面提到的基本数据类型是有本质区别的。前者是计算机数据存储的基本形式，也是所有编程语言都要涉及的，而后者是Python中的内置对象，且仅存在于Python中。

数据结构和算法是相辅相成的关系，抛开数据结构谈算法是空中楼阁、无源之水。所以下面就要进一步了解基础的数据结构。数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。在图4-6中，常用的数据结构有数组、栈、链表、队列、树、图、堆、散列表等。我们已经掌握了数组、栈、链表、队列、堆的用法，也介绍了树和图的概念。

任何可以被散列的类型都可以成为索引对象，索引对象通常会是一个字符串。如果有一些无关联的数据，它们都可以被唯一的索引对象来引用，那么集合和字典就是理想的数据结构。索引对象被称为“键”，而数据被称为“值”。字典和集合结构很像，只是集合实际上并不包含值，所以也有人会说集合只不过是一堆键的组合。

图4-6 数据结构分类

字典和集合的性能是很高效的，这和它们内部的数据结构密不可分。不同于其他数据结构，字典和集合的内部结构都是一张哈希表。对于字典而言，这张表存储了哈希值（hash）、键和值3个元素；而对集合来说，哈希表内只存储单一的元素。

使用字典和集合有其代价，它们会占用更多的内存，通俗点讲就是以空间换时间。虽然插入和查询的时间复杂度是O（1），但是实际的速度取决于其使用的散列函数。如果散列函数的运行速度较慢，那么在字典和集合上进行的任何操作也会变慢。

4.9.1 哈希表插入数据

当向字典中插入数据时，Python会首先根据键key计算出对应的哈希值hash key，而向集合中插入数据时，Python会根据该元素本身计算对应的哈希值。

例4-31 字典的哈希值

得到哈希值hash之后，再结合字典或集合要存储数据的个数n，就可以得到该元素应该插入到哈希表中的位置。比如，可以用hash%n类似的算法来计算位置数据。

如果哈希表中此位置是空的，那么此元素就可以直接插入其中；反之，如果此位置已被其他元素占用，那么Python会比较这两个元素的哈希值和键是否相等。如果相等，则表明该元素已经存在，再比较他们的值，不相等就进行更新；如果不相等，这种情况称为哈希冲突，即两个元素的键不同，但求得的哈希值相同。这种情况下，Python会使用开放定址法、再哈希法等继续寻找哈希表中空余的位置，直到找到位置。这个算法并不重要，了解即可，不必深究。

4.9.2 哈希表查找数据

在哈希表中查找数据和插入操作类似，Python会根据哈希值，找到该元素应该存储到哈希表中的位置，然后和该位置的元素比较其哈希值和键。如果相等，则证明找到；反之，则证明当初存储该元素时，遇到了哈希冲突，需要继续使用当初解决哈希冲突的方法进行查找，直到找到该元素或者找到空位为止。

4.9.3 哈希表删除数据

对于删除操作，Python会暂时对这个位置的元素赋予一个特殊的值，等到重新调整哈希表的大小时，再将其删除。需要注意的是，哈希冲突的发生往往会降低字典和集合操作的速度。因此，为了保证其高效性，字典和集合内的哈希表，通常会保证其至少留有1/3的剩余空间。随着元素的不停插入，当剩余空间小于1/3时，Python会重新获取更大的内存空间，扩充哈希表，与此同时，表内所有的元素位置都会被重新排放。

虽然哈希冲突和哈希表大小的调整，都会导致速度减缓，但是这种情况发生的次数极少。所以，平均情况下，仍能保证插入、查找和删除的时间复杂度为O（1）。

学习编程语言虽然很重要，但是学习计算机算法和理论更重要。虽然计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等。这些基础课程是“内功”，新的语言、技术、标准是“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。