Python的dict实现原理及与Java的比较探究

Python内部很地方都使用着dict这种结构,在对象属性dict就是一个字典,所以对其效率要求很高。

dict采用了哈希表,最低能在 O(1)时间内完成搜索。同样的java的HashMap也是采用了哈希表实现,不同是dict在发生哈希冲突的时候采用了开放寻址法,而HashMap采用了链接法。

开放寻址法

优点

1、记录更容易进行序列化(serialize)操作

2、如果记录总数可以预知,可以创建完美哈希函数,此时处理数据的效率是非常高的

缺点

1、存储记录的数目不能超过桶数组的长度,如果超过就需要扩容,而扩容会导致某次操作的时间成本飙升,这在实时或者交互式应用中可能会是一个严重的缺陷

2、使用探测序列,有可能其计算的时间成本过高,导致哈希表的处理性能降低

3、由于记录是存放在桶数组中的,而桶数组必然存在空槽,所以当记录本身尺寸(size)很大并且记录总数规模很大时,空槽占用的空间会导致明显的内存浪费

4、删除记录时,比较麻烦。比如需要删除记录a,记录b是在a之后插入桶数组的,但是和记录a有冲突,是通过探测序列再次跳转找到的地址,所以如果直接删除a,a的位置变为空槽,而空槽是查询记录失败的终止条件,这样会导致记录b在a的位置重新插入数据前不可见,所以不能直接删除a,而是设置删除标记。这就需要额外的空间和操作

想要自己实现一个dict可以继承 collection 的 UserDict,里面已经封装了常用的方法。 下面是我根据自己的理解去用python实现的字典,简化了很的功能,比如对象缓冲池、String哈希的优化等等,如果有错误的或者更好的实现方式请指出。因为python没有纯粹的数组结构,所以数组也是借用list实现的

链接法

优点

1、对于记录总数频繁可变的情况,处理的比较好(也就是避免了动态调整的开销) 2、由于记录存储在结点中,而结点是动态分配,不会造成内存的浪费,所以尤其适合那种记录本身尺寸(size)很大的情况,因为此时指针的开销可以忽略不计了

3、删除记录时,比较方便,直接通过指针操作即可

缺点

1、存储的记录是随机分布在内存中的,这样在查询记录时,相比结构紧凑的数据类型(比如数组),哈希表的跳转访问会带来额外的时间开销

2、如果所有的 key-value 对是可以提前预知,并之后不会发生变化时(即不允许插入和删除),可以人为创建一个不会产生冲突的完美哈希函数(perfect hash function),此时封闭散列的性能将远高于开放散列

3、由于使用指针,记录不容易进行序列化(serialize)操作

其中有很重要的两个参数影响其性能: 初始容量和加载因子

dict:默认初始容量为8,加载因子为2/3

HashMap: 默认初始容量为16, 加载因子为0.75

两者相同的是扩容的长度必需是2的N次方

本文作者

文武,技术爱好者

博客:zhihu.com/people/xiaomiba0904

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180304A13Z9O00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券