python 字典的内部实现原理介绍

2021年09月15日 阅读数:1
这篇文章主要向大家介绍python 字典的内部实现原理介绍,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

python 的字典内部使用的数据结构是 hash 表python

1、hash 表相关概念
算法

哈希表实际上是一个稀疏数组(老是有空白元素的数组称为稀疏数组)。它是一种根据关键码值(Key-value)直接访问在内存存储位置的数据结构。数组


哈希函数:也称为是散列函数,是Hash表的映射函数,它能够把任意长度的输入变换成固定长度的输出,该输出就是哈希值。经过使用哈希函数来肯定元素在哈希表的存储位置,哈希函数能使对一个数据序列的访问过程变得更加迅速有效,经过哈希函数,数据元素可以被很快的进行定位。微信


散列表里的单元一般叫做表元(bucket)。在 dict 的散列表当中,每一个键值对都占用一个表元,每一个表元都有两个部分,一个是对键的引用,另外一个是对值的引用。由于全部表元的大小一致,因此能够经过偏移量来读取某个表元。数据结构


2、字典dict查找值的原理函数

经过字典的 key 来获取其 value值能够经过 dict.get(key) 或者 dict[key]来查找,可是其内部实现原理是怎样的呢?spa


Python 首先会调用hash(search_key)来计算 search_key 的散列值,把这个值最低的几位数字看成偏移量,在散列表里查找表元(具体取几位,得看当前散列表的大小)。若找到的表元是空的,则抛出KeyError 异常。若不是空的,则表元里会有一对 found_key:found_value。这时候 Python 会检验 search_key == found_key 是否为真,若是它们相等的话,就会返回 found_value。.net




若是 search_key 和 found_key 不匹配的话,这种状况称为散列冲突。发生这种状况是由于,散列表所作的实际上是把随机的元素映射到只有几位的数字上,而散列表自己的索引又只依赖于这个数字的一部分。为了解决散列冲突,算法会在散列值中另外再取几位,而后用特殊的方法处理一下,把新获得的数字再看成索引来寻找表元。若此次找到的表元是空的,则一样抛出 KeyError;若非空,或者键匹配,则返回这个值;或者又发现了散列冲突,则重复以上的步骤。orm


3、字典dict新增和修改对象

字典添加新元素和更新现有键值的操做几乎跟查找操做同样。只不过对于新增,在发现空表元的时候会放入一个新元素;对于更新操做,在找到相对应的表元后,原表里的值对象会被替换成新值。


另外在插入新值时,Python 可能会按照散列表的拥挤程度来决定是否要从新分配内存为它扩容。若是增长了散列表的大小,那散列值所占的位数和用做索引的位数都会随之增长,这样作的目的是为了减小发生散列冲突的几率。


4、字典dict的特色总结

因为字典使用了散列表,而散列表又必须是稀疏的,这致使它在空间上的效率低下。举例而言,若是你须要存放数量巨大的记录,那么放在由元组或是具名元组构成的列表中会是比较好的选择;最好不要根据 JSON 的风格,用由字典组成的列表来存放这些记录。用元组取代字典就能节省空间的缘由有两个:


其一是避免了散列表所耗费的空间,

其二是无需把记录中字段的名字在每一个元素里都存一遍。


dict 的实现是典型的空间换时间:字典类型有着巨大的内存开销,但它们提供了无视数据量大小的快速访问——只要字典能被装在内存里。


不管什么时候往字典里添加新的键,Python 解释器均可能作出为字典扩容的决定。扩容致使的结果就是要新建一个更大的散列表,并把字典里已有的元素添加到新表里。这个过程当中可能会发生新的散列冲突,致使新散列表中键的次序变化。


上面提到的这些变化是否会发生以及如何发生,都依赖于字典背后的具体实现,所以你不能很自信地说本身知道背后发生了什么。若是你在迭代一个字典的全部键的过程当中同时对字典进行修改,那么这个循环颇有可能会跳过一些键——甚至是跳过那些字典中已经有的键。


由此可知,不要对字典同时进行迭代和修改。若是想扫描并修改一个字典,最好分红两步来进行:首先对字典迭代,以得出须要添加的内容,把这些内容放在一个新字典里;迭代结束以后再对原有字典进行更新。





本文分享自微信公众号 - pythonista的平常(gh_fc70d5d98d3f)。
若有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一块儿分享。