Python中的字典和集合为什么能够如此高效？

前言

前面我们学习了Python中的列表和元组（Python——列表和元组的使用场景），了解他们的相同点和不同点并知道了使用场景。今天，我们进行学习两个常见和常用的数据结构：字典（dict）和集合（set）

什么是字典和集合？

字典是一系列由键（key）和值（value）配对组成的元素的集合。

相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。而集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合。

字典和集合的工作原理

字典和集合为什么能够如此高效，特别是查找、插入和删除操作？这当然和字典、集合内部的数据结构密不可分。字典和集合的内部结构都是一张哈希表。

对于字典而言，这张表存储了哈希值（hash）、键和值这 3 个元素。

而对集合来说，区别就是哈希表内没有键和值的配对，只有单一的元素了。

字典和集合性能

我说了，字典和集合是进行过性能高度优化的数据结构，特别是对于查找、添加和删除操作。我们看看，它们在具体场景下的性能表现，以及与列表等其他数据结构的对比。

比如电商企业的后台，存储了每件产品的 ID、名称和价格。现在的需求是，给定某件商品的 ID，我们要找出其价格。

假设列表有 n 个元素，而查找的过程要遍历列表，那么时间复杂度就为 O(n)。即使我们先对列表进行排序，然后使用二分查找，也会需要 O(logn) 的时间复杂度，更何况，列表的排序还需要 O(nlogn) 的时间。

但如果我们用字典来存储这些数据，那么查找就会非常便捷高效，只需 O(1) 的时间复杂度就可以完成。原因也很简单，字典的内部组成是一张哈希表，你可以直接通过键的哈希值，找到其对应的值。

如果现在需求变成，要找出这些商品有多少种不同的价格。我们还用同样的方法来比较一下。

如果还是选择使用列表，对应的代码如下，其中，A 和 B 是两层循环。同样假设原始列表有 n 个元素，那么，在最差情况下，需要 O(n^2) 的时间复杂度。

但如果我们选择使用集合这个数据结构，由于集合是高度优化的哈希表，里面元素不能重复，并且其添加和查找操作只需 O(1) 的复杂度，那么，总的时间复杂度就只有 O(n)。

实际应用

为了对它们的时间复杂度有直观的认识，我可以举一个实际工作场景中的例子，让你来感受一下。

下面的代码，初始化了含有 100,000 个元素的产品，并分别计算了使用列表和集合来统计产品价格数量的运行时间：

你可以看到，仅仅十万的数据量，两者的速度差异就如此之大。事实上，大型企业的后台数据往往有上亿乃至十亿数量级，如果使用了不合适的数据结构，就很容易造成服务器的崩溃，不但影响用户体验，并且会给公司带来巨大的财产损失。