python中字典的内部实现原理是什么


这期内容当中小编将会给大家带来有关python中字典的内部实现原理是什么,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。python 的字典内部使用的数据结构是 hash 表一、hash 表相关概念
哈希表其实是一个稀疏数组(总是有空白元素的数组称为稀疏数组)。它是一种根据关键码值(Key-value)直接访问在内存存储位置的数据结构。哈希函数:也称为是散列函数,是H 香港云主机ash表的映射函数,它可以把任意长度的输入变换成固定长度的输出,该输出就是哈希值。通过使用哈希函数来确定元素在哈希表的存储位置,哈希函数能使对一个数据序列的访问过程变得更加迅速有效,通过哈希函数,数据元素能够被很快的进行定位。散列表里的单元通常叫作表元(bucket)。在 dict 的散列表当中,每个键值对都占用一个表元,每个表元都有两个部分,一个是对键的引用,另一个是对值的引用。因为所有表元的大小一致,所以可以通过偏移量来读取某个表元。二、字典dict查找值的原理通过字典的 key 来获取其 value值可以通过 dict.get(key)或者 dict[key]来查找,但是其内部实现原理是怎样的呢?Python 首先会调用hash(search_key)来计算 search_key 的散列值,把这个值最低的几位数字当作偏移量,在散列表里查找表元(具体取几位,得看当前散列表的大小)。若找到的表元是空的,则抛出KeyError 异常。若不是空的,则表元里会有一对 found_key:found_value。这时候 Python 会检验 search_key == found_key 是否为真,如果它们相等的话,就会返回 found_value。如果 search_key 和 found_key 不匹配的话,这种情况称为散列冲突。发生这种情况是因为,散列表所做的其实是把随机的元素映射到只有几位的数字上,而散列表本身的索引又只依赖于这个数字的一部分。为了解决散列冲突,算法会在散列值中另外再取几位,然后用特殊的方法处理一下,把新得到的数字再当作索引来寻找表元。若这次找到的表元是空的,则同样抛出 KeyError;若非空,或者键匹配,则返回这个值;或者又发现了散列冲突,则重复以上的步骤。三、字典dict新增和修改字典添加新元素和更新现有键值的操作几乎跟查找操作一样。只不过对于新增,在发现空表元的时候会放入一个新元素;对于更新操作,在找到相对应的表元后,原表里的值对象会被替换成新值。另外在插入新值时,Python 可能会按照散列表的拥挤程度来决定是否要重新分配内存为它扩容。如果增加了散列表的大小,那散列值所占的位数和用作索引的位数都会随之增加,这样做的目的是为了减少发生散列冲突的概率。四、字典dict的特点总结
由于字典使用了散列表,而散列表又必须是稀疏的,这导致它在空间上的效率低下。举例而言,如果你需要存放数量巨大的记录,那么放在由元组或是具名元组构成的列表中会是比较好的选择;最好不要根据 JSON 的风格,用由字典组成的列表来存放这些记录。用元组取代字典就能节省空间的原因有两个:其一是避免了散列表所耗费的空间,其二是无需把记录中字段的名字在每个元素里都存一遍。dict 的实现是典型的空间换时间:字典类型有着巨大的内存开销,但它们提供了无视数据量大小的快速访问——只要字典能被装在内存里。无论何时往字典里添加新的键,Python 解释器都可能做出为字典扩容的决定。扩容导致的结果就是要新建一个更大的散列表,并把字典里已有的元素添加到新表里。这个过程中可能会发生新的散列冲突,导致新散列表中键的次序变化。上面提到的这些变化是否会发生以及如何发生,都依赖于字典背后的具体实现,因此你不能很自信地说自己知道背后发生了什么。如果你在迭代一个字典的所有键的过程中同时对字典进行修改,那么这个循环很有可能会跳过一些键——甚至是跳过那些字典中已经有的键。上述就是小编为大家分享的python中字典的内部实现原理是什么了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注开发云行业资讯频道。

相关推荐: Javascript怎么实现网页抢红包功能

本文小编为大家详细介绍“Javascript怎么实现网页抢红包功能”,内容详细,步骤清晰,细节处理妥当,希望这篇“Javascript怎么实现网页抢红包功能”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。一开始用Firefox加Fir…

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 07/27 14:20
下一篇 07/27 15:24

相关推荐