Python中dict和set实现原理

python的dict和set设计上是很巧妙的,底层是用c语言编写,哈希表实现,这样确保了高效的数据处理。

1、dict的性能远高于list
2、list的查询消耗随着查询数量的增大而增大
3、dict的查询消耗并不会随着查询数量的增大而增大

dict内部实现是根据哈西表来实现的:
20180407100709_810.png

1、当申明dict变量的时候,就会在内存中开辟一个连续的数组空间。
2、连续的空间是允许存在空白的,这是为了后续能够实现在原空间内插入数据。
3、如果在后续插入数据的时候,发现原空间中空白的比例小于原空间的三分之一,就会再申请开辟一段连续啊的空间用于存储,将原有的数据搬迁出来和新的数据一起插入新的空间中。(这时候顺序会打乱)
4、dict查找时,会根据key值计算出在hash表中的位置,hash表中的键值对位置是唯一的。计算的方式是根据key值的后一位组合元素进行计算,计算过程中如果发现hash表中已经存在值,就加上key值前一位进行计算,最终找出value值的位置。如下:
20180407102108_979.png
abc —— key ,根据c来计算位置,如果计算结果被别的值占据,则用bc来计算。

5、dict查找性能快的原因是,直接对key值进行hash计算,因为开辟的数组空间是连续的,有偏移量的,直接将偏移量返回,就能马上找到value值在哪里。


原理概要
1、dict或者set的值,都必须是可以hash的,不可变的值都是可以被hash的,如str、fronzenset、tuple,或者自己定义的类,实现了__hash__这个魔法方法的,都可以被hash。
2、dict的内存花销大,但是查询速度快,自定义的对象或者python的内部对象都是用dict来包装的。
3、dict的存储顺序和元素的添加顺序有关。
4、添加数据有可能改变已有数据的顺序。

Last modification:November 25th, 2019 at 05:07 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment