深入底层了解Python字典和集合,一眼看穿他们的本质!
字典和集合是进行过性能高度优化的数据结构,特别是对于查找、添加和删除操作。本节将结合实例介绍它们在具体场景下的性能表现,以及与列表等其他数据结构的对比。
例如,有一个存储产品信息(产品 ID、名称和价格)的列表,现在的需求是,借助某件产品的ID找出其价格。则实现代码如下:
但如果用字典来存储这些数据,那么查找就会非常便捷高效,只需
有些读者可能对时间复杂度并没有直观的认识,没关系,再给大家列举一个实例。下面的代码中,初始化了含有 100,000 个元素的产品,并分别计算出了使用列表和集合来统计产品价格数量的运行时间:
那么,字典和集合为什么能如此高效,特别是查找、插入和删除操作呢?
对于之前版本的 Python 来说,它的哈希表结构如下所示:
在此基础上,上面的字典在新哈希表结构下的存储形式为:
清楚了具体的设计结构,接下来再分析一下如何使用哈希表完成对数据的插入、查找和删除操作。
例如:
如果哈希表中此位置是空的,那么此元素就可以直接插入其中;反之,如果此位置已被其他元素占用,那么 Python 会比较这两个元素的哈希值和键是否相等:
需要注意的是,哈希冲突的发生往往会降低字典和集合操作的速度。因此,为了保证其高效性,字典和集合内的哈希表,通常会保证其至少留有 1/3 的剩余空间。随着元素的不停插入,当剩余空间小于 1/3 时,Python 会重新获取更大的内存空间,扩充哈希表,与此同时,表内所有的元素位置都会被重新排放。
虽然哈希冲突和哈希表大小的调整,都会导致速度减缓,但是这种情况发生的次数极少。所以,平均情况下,仍能保证插入、查找和删除的时间复杂度为
例如,有一个存储产品信息(产品 ID、名称和价格)的列表,现在的需求是,借助某件产品的ID找出其价格。则实现代码如下:
def find_product_price(products, product_id): for id, price in products: if id == product_id: return price return None products = [ (111, 100), (222, 30), (333, 150) ] print('The price of product 222 is {}'.format(find_product_price(products, 222)))运行结果为:
The price of product 222 is 30
在上面程序的基础上,如果列表有 n 个元素,因为查找的过程需要遍历列表,那么最坏情况下的时间复杂度就为O(n)
。即使先对列表进行排序,再使用二分查找算法,也需要 O(logn)
的时间复杂度,更何况列表的排序还需要 O(nlogn)
的时间。但如果用字典来存储这些数据,那么查找就会非常便捷高效,只需
O(1)
的时间复杂度就可以完成,因为可以直接通过键的哈希值,找到其对应的值,而不需要对字典做遍历操作,实现代码如下:products = { 111: 100, 222: 30, 333: 150 } print('The price of product 222 is {}'.format(products[222]))运行结果为:
The price of product 222 is 30
有些读者可能对时间复杂度并没有直观的认识,没关系,再给大家列举一个实例。下面的代码中,初始化了含有 100,000 个元素的产品,并分别计算出了使用列表和集合来统计产品价格数量的运行时间:
#统计时间需要用到 time 模块中的函数,了解即可 import time def find_unique_price_using_list(products): unique_price_list = [] for _, price in products: # A if price not in unique_price_list: #B unique_price_list.append(price) return len(unique_price_list) id = [x for x in range(0, 100000)] price = [x for x in range(200000, 300000)] products = list(zip(id, price)) # 计算列表版本的时间 start_using_list = time.perf_counter() find_unique_price_using_list(products) end_using_list = time.perf_counter() print("time elapse using list: {}".format(end_using_list - start_using_list)) #使用集合完成同样的工作 def find_unique_price_using_set(products): unique_price_set = set() for _, price in products: unique_price_set.add(price) return len(unique_price_set) # 计算集合版本的时间 start_using_set = time.perf_counter() find_unique_price_using_set(products) end_using_set = time.perf_counter() print("time elapse using set: {}".format(end_using_set - start_using_set))运行结果为:
time elapse using list: 68.78650900000001
time elapse using set: 0.010747099999989018
那么,字典和集合为什么能如此高效,特别是查找、插入和删除操作呢?
字典和集合的工作原理
字典和集合能如此高效,和它们内部的数据结构密不可分。不同于其他数据结构,字典和集合的内部结构都是一张哈希表:- 对于字典而言,这张表存储了哈希值(hash)、键和值这 3 个元素。
- 而对集合来说,哈希表内只存储单一的元素。
对于之前版本的 Python 来说,它的哈希表结构如下所示:
| 哈希值 (hash) 键 (key) 值 (value) . | ... 0 | hash0 key0 value0 . | ... 1 | hash1 key1 value1 . | ... 2 | hash2 key2 value2 . | ...这种结构的弊端是,随着哈希表的扩张,它会变得越来越稀疏。比如,有这样一个字典:
{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}
那么它会存储为类似下面的形式:entries = [ ['--', '--', '--'] [-230273521, 'dob', '1999-01-01'], ['--', '--', '--'], ['--', '--', '--'], [1231236123, 'name', 'mike'], ['--', '--', '--'], [9371539127, 'gender', 'male'] ]显然,这样非常浪费存储空间。为了提高存储空间的利用率,现在的哈希表除了字典本身的结构,会把索引和哈希值、键、值单独分开,也就是采用如下这种结构:
Indices ---------------------------------------------------- None | index | None | None | index | None | index ... ---------------------------------------------------- Entries -------------------- hash0 key0 value0 --------------------- hash1 key1 value1 --------------------- hash2 key2 value2 --------------------- ... ---------------------
在此基础上,上面的字典在新哈希表结构下的存储形式为:
indices = [None, 1, None, None, 0, None, 2] entries = [ [1231236123, 'name', 'mike'], [-230273521, 'dob', '1999-01-01'], [9371539127, 'gender', 'male'] ]通过对比可以发现,空间利用率得到很大的提高。
清楚了具体的设计结构,接下来再分析一下如何使用哈希表完成对数据的插入、查找和删除操作。
哈希表插入数据
当向字典中插入数据时,Python 会首先根据键(key)计算出对应的哈希值(通过 hash(key) 函数),而向集合中插入数据时,Python会根据该元素本身计算对应的哈希值(通过 hash(valuse) 函数)。例如:
dic = {"name":1} print(hash("name")) setDemo = {1} print(hash(1))运行结果为:
8230115042008314683
1
如果哈希表中此位置是空的,那么此元素就可以直接插入其中;反之,如果此位置已被其他元素占用,那么 Python 会比较这两个元素的哈希值和键是否相等:
- 如果相等,则表明该元素已经存在,再比较他们的值,不相等就进行更新;
- 如果不相等,这种情况称为哈希冲突(即两个元素的键不同,但求得的哈希值相同)。这种情况下,Python 会使用开放定址法、再哈希法等继续寻找哈希表中空余的位置,直到找到位置。
具体遇到哈希冲突时,各解决方法的具体含义可阅读《哈希表详解》一节做详细了解。
哈希表查找数据
在哈希表中查找数据,和插入操作类似,Python 会根据哈希值,找到该元素应该存储到哈希表中的位置,然后和该位置的元素比较其哈希值和键(集合直接比较元素值):- 如果相等,则证明找到;
- 反之,则证明当初存储该元素时,遇到了哈希冲突,需要继续使用当初解决哈希冲突的方法进行查找,直到找到该元素或者找到空位为止。
这里的找到空位,表示哈希表中没有存储目标元素。
哈希表删除元素
对于删除操作,Python 会暂时对这个位置的元素赋于一个特殊的值,等到重新调整哈希表的大小时,再将其删除。需要注意的是,哈希冲突的发生往往会降低字典和集合操作的速度。因此,为了保证其高效性,字典和集合内的哈希表,通常会保证其至少留有 1/3 的剩余空间。随着元素的不停插入,当剩余空间小于 1/3 时,Python 会重新获取更大的内存空间,扩充哈希表,与此同时,表内所有的元素位置都会被重新排放。
虽然哈希冲突和哈希表大小的调整,都会导致速度减缓,但是这种情况发生的次数极少。所以,平均情况下,仍能保证插入、查找和删除的时间复杂度为
O(1)
。所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频