Python底层是怎么实现字典的?
2023-04-18 12:47:28 时间
前言
上次我们分享了列表的底层原理,今天我们继续分享另外一个常用的Python数据结构,字典。字典的键值对,可以让我们可以很轻松的完成数据查询、添加和删除,说到键值对,我又不经意想到了散列表(哈希表)。
今天可以明确的告诉你,字典就是用到了哈希表的思想,全剧终。开玩笑哈,那废话不多说,开整。
哈希表
在说字典的具体实现之前,我们还是简单介绍下哈希表的原理,大可放心,我尽量讲的通俗些。
之前我们介绍过数组,通过索引我们能快速获取元素值。哈希表也是一样,但是数组的索引是0到n-1,但是哈希表是键值对,所以,哈希函数来了。
我们把键通过哈希函数转换为哈希值(这样就可以是个整数),然后将对应的值存在数组中这个哈希值索引的位置上。
dict = {}
dict['name'] = 'lisi'
当然哈希表没有这么简单,还会涉及哈希冲突,扩容等等问题,这里就不过多介绍了。
字典
不会吧,都2021年了,不会还有人说字典是无序的吧。
确实,在python3.6之前,字典是无序的,但是在python3.7开始,字典就有序了,这有序无序,恰恰就说明字典的底层发生了变化,我们来一探究竟。
无序
在python3.6之前,哈希表结构如下所示,每一行存储了哈希值(hash)、键(key)、值(value)3个元素。
table = [
['--', '--', '--'],
[hash, key, value],
['--', '--', '--'],
['--', '--', '--'],
[hash, key, value],
]
例如dict['name'] = 'lisi',假设name计算的hash值为1,则存储如下。
dict = [
['--', '--', '--'],
[1, 'name', 'lisi'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
]
所以我们没办法保证下一个插入的键值对能保证在1的后面,hash值计算出来是多少,就存储在什么位置,没法做到有序,而却这种方法也很容易让哈希表稀疏,占用大量内存。
有序
有序的字典把索引和哈希值、键、值单独分开,如下所示。
indices = [None, None, index,]
table = [
[hash0, key0, value0],
[hash1, key1, value1],
[hash2, key2, value2]
]
所以前面的例子在这里保存就是这样的。
indices = [None, 0, None]
table = [
[1, 'name', 'lisi'],
]
这样确保了有序。
总结
当然,Python具体用的是什么hash函数,又是怎么解决哈希冲突和扩容的,这些就留给读者了,今天的分享就到这了,我们下期再见~
相关文章
- Python轻松查看微信撤回消息,秘密无处可藏
- 面临中国禁售:苹果走上专利战末路?
- 梦幻西游这么火,Python也不甘示弱,Python写游戏辅助软件!
- 如何用iPad运行Python代码?
- 用Python及深度学习实现iPhone X的FaceID功能
- SQL Server在存储过程中编写事务处理代码的三种方法
- 学会这五种编程语言,再来研究DevOps也不迟
- 谷歌向开发者推送的安卓8.1来了!10大新功能!
- Android 8.1开发者预览版发布 启用全新安全协议“DNS over TLS
- 挨踢部落故事汇(30):我与Python的相爱相杀
- 挨踢部落坐诊第九期: Java、Python、PHP他们都说很简单
- 神经网络中 BP 算法的原理与 Python 实现源码解析
- 挨踢部落故事汇(15):不断拓新成为科技大潮中的弄潮儿
- 面向Python语言的三大顶级机器学习库
- TensorFlow 1.0:在智能手机端解锁机器学习
- 学习Python:做数据科学还是网站开发?
- flowable异步任务加锁流程
- Teradata天睿公司在业内率先将DevOps扩展至数据仓库
- 时延检测利器-uftrace
- 八个 Python 数据生态圈的前沿项目