Python中dict和set实现原理

November 5, 2017

3552 views

1015 字数

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

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

dict内部实现是根据哈西表来实现的：

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

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、添加数据有可能改变已有数据的顺序。