Python内核源码阅读(十三)

Python内核源码阅读(十三)

Python 中 PyDictObject 采用了散列表.
这是一种表现为存储形式如 key:value(键值对)的数据的数据结构,用户通过索引 Key 来获取对应的 value 值. 对于数组或者 list 来说,内部数据只能通过数字下标获取,但在 dict 中, key 则可以是 Python 下任意的对象.

Hash Table

Python 中 dict 对象的实现方式是一个 hash table:

/* Dictionary object implementation using a hash table */

PyDictObject 没有如 std::map 一样采用平衡二叉树,而采用了散列表(hash table), 因为理论上, 在最优的情况下,散列表提供 O(1) 复杂度的搜索效率.

平衡二叉树的好处在于在于存储空间和搜索效率之间的平衡,在最小的空间需求下,用户可以得到 O(longN) 的搜索时间复杂度.

但是由于 Python 内部大量的使用 dict, 所以这个时间复杂度是不可以被接受的,O(1)当然是最好的选择.

散列表的基本思想,是通过一定的函数将需搜索的键映射为一个整数(对象hash值的全部或者一部分),将这个整数视为索引值去访问某片连续的内存空间.

然而散列表有一个必须要面对的问题解决HASH冲突.由于预想被插入到散列表的数据是随机的,但散列函数所能得到的散列值是有限的.所以一定会发生冲突:前后插入列表的不同元素,经过相同的散列函数得到相同的散列值.

这个时候需要使用恰当的策略来应对: 其一是使用链表实现分离链接法,其二就是不使用链表的开放定址法.

前者将具有相同散列值的元素使用链表连接起来,后者则是 Python 中 dict 使用的散列冲突解决方法.

当产生 Hash 冲突时, Python 会通过一个二次探测函数 f , 计算下一个候选位置 addr , 如果位置 addr 可用则将待插入元素放到位置 addr; 如果 addr 不可用,则 Python 会再次使用 探测函数 f 获取下一个位置,如此不断的探测,总会找到一个可用的位置.

开放定址法的好处就是不使用链表,所有的元素都放在一个表中,所以才有可能达到 O(1) 的搜索时间复杂度. 其副作用是需要比实际用到的更大的存储空间:

一般来说, 对开放定址散列算法来说,装填因子应该低于 λ = 0.5.

Python 使用开放定址法的注意事项

在 Python 中 dict 中删除是需要策略的

通过多次使用探测函数 f ,从一个位置出发就可以依次到达多个位置,我们认为这些位置形成了一个"冲突探测链".

在这条冲突探测链中间位置的元素是不能被删除的,否则会导致其后的元素无法被索引.所以 Python 使用了一种伪删除的策略.

这种策略类似与数据库中的逻辑删除, 只是为数据打上了标记,但并不是真正的从数据库中删除.

这就是使得,即使元素被删除了,也依旧保留在冲突探测链上,以保证其后忽然元素能够被索引.

发表评论