Python源码分析-PyDictObject

目前Cpython使用最多,下面分析下python中字典的源码实现

数据结构

1. PyDictObject

PyDictObject是python字典对应的C对象,本质上是一个hash表基本元素的组合,包含3个元素:

  • 一个table(可以看成是一个数组)
  • hash函数
  • 表格中的每一项:entry

  1. PyDictObject包含了一个PyObject_HEAD, 任何python的对象都含他的指针。PyObject_HEAD包含一个双向链表, 一个引用计算器, 一个对象描述(typeobject)。这个对象其实主要的作用是垃圾回收。
  2. ma_tablema_smalltable对应的是hash表中的table,但这里为啥有两个table呢?因为Python源码中使用了大量PyDictOject,但是dict中元素的数量一般比较少,为了方便,每次创建该对象时都会创建Pydict_MINISIZE个entry空间。当table中元素的个数超过一定数量时就会自动调整table的长度。所以,ma_table初始时等于ma_smalltable,当entry个数增加时,会调整 ma_table的长度。
  3. Py_ssize_t ma_mask是用于计算hash值的,它的值等于table的长度减一。这个属性的理解非常重要,直接关系到是否能完全理Python的哈希函数以及hash值的计算。Python字典的哈希函数非常简单,如下:
  4. ma_lookup 函数用于根据 key查找 val。既然hash函数这么简单,那么为什么还需一个特殊的查找函数呢?因为table中的entry不是简单的一个数字或者字符串,而是一个对象PyDictEntry,这个对象有自己的生命周期,所以i在查找时稍微复杂一点。
  5. ma_fillma_used:上面说过PyDictEntry有自己的生命周期,包括3个状态:unusedactive, dummy。ma_fill表示table中已使用的个数(=active+dummy),active表示当前正在使用的个数,dummy表示插入以后删除的个数。

2. PyDictEntry

PyDictEntry是table中的具体元素项。

  1. me_hash是hash值, me_key是储存的对象(可以是任意类型,因为python中一切皆对象,这些对象都是PyObject),me_value是存储的值。

hash函数分析

理解一个hash表的实现,最重要的是理解其中的hash函数的实现,以及发生碰撞时的解决方法。

1. hash函数的实现

上面介绍过hash函数的实现

  1. PyDictObject本身的hash函数很简单,因为key是经过一次hash的值,即get_key函数就是获取一个对象(包括字符串,整数和更复杂对象)的hash值。Python源码中的原型如下:
举例分析怎么获取string对象的hash
  1. string对象的hash值获取,先看string对象的定义

    • 每个string对象有一个 ob_shash,这个值就是该string的hash值。这个值就是通过tp_hash获取的。具体可以参考源码Object/stringobject.c中的 static long string_hash()函数

综上:hash函数进行散列之前,会先获取每个对象的hash值,如果该对象有实现tp_hash函数,就调用该函数,如果没有就使用该对象的内存地址的值作为hash值,然后用该值对 ma_mask取余获取该对象存储到table中的位置。

2. 碰撞时的解决方式

hash散列发生碰撞的解决方法主要有:

  • 开放地址法,
  • 再散列法,
  • 链地址法等等。

python字典中使用的是再散列法,函数如下:

其中,perturb初始值是对象的hash值,

3. table大小的重新调整

什么时候需要重新调整table的大小呢, hash表的性能主要表现在装填因子上,

python的字典实现中,当装填因子大于 2/3 时就进行重现调整table的大小,调整的过程其实就是新开辟一个计算得出的新大小的table空间,然后将旧table中的entry重新计算写入新table中。

值得注意的是: 上面提到的fillma_fill(ma_fill=active+dummy)。也就是说这个装填因子的计算考虑到了那些delete 的对象,就是删除了,仍然计算在内。

PyDictObject对象的创建,插入与删除

这部分内容比较简单,直接看源码就行,后面再分析

1 1 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部