python 字典实现原理

引言

Python中dict对象是表明了其是一个原始的Python数据类型，按照键值对的方式存储，其中文名字翻译为字典，顾名思义其通过键名查找对应的值会有很高的效率，时间复杂度在常数级别O(1).本文针对其实现的数据结构进行原理性说明和拓展，不涉及Python的源码剖析。

dict底层实现

在Python2中，dict的底层是依靠哈希表(Hash Table)进行实现的，使用开放地址法解决冲突.

所以其查找的时间复杂度会是O(1)，下文会具体讲解哈希表的工作原理和解决冲突时的具体方法。

哈希表

哈希表是key-value类型的数据结构，通过关键码值直接进行访问。通过散列函数进行键和数组的下标映射从而决定该键值应该放在哪个位置，**哈希表可以理解为一个键值需要按一定规则存放的数组，而哈希函数就是这个规则。**此处提出几个专业名词后面会一一进行介绍。

哈希函数
装填因子
冲突

1.哈希表产生的原因

假设我们存在一个简单的键值对结构，键-员工号，值-是否在岗。现在需要这样一个功能，输入员工号，返回该员工是否在岗，理想的方法是创建一个长度为Max(员工号)的数组，数组下标就是员工号，数组中的值用0和1对是否在岗进行区分，这样只需要O(1)的时间复杂度就可以完成操作，但是扩展性不强，存在以下问题。

1.假设新进员工的员工号比Max(员工号)还要大，这就需要重新申请数组进行迁移操作。

2.假设一种极端的情况，存在两个员工，员工号分别是1和100000000001，这样子的话按照先前的设计思路，是会浪费很大的存储空间的。

上面两点，第一点是因为数组的固定申请大小的属性所决定，而第二点就是引入哈希表的原因，会不会存在一个方法，让一个大员工号变小而而且没有标记，哈希函数便产生，假设此处的哈希规则是除3取模，则员工1得到的哈希值是1，员工100000000001得到的哈希值是2，这样的话按照设计思路，只需要一个大小为2的数组便可以覆盖了，这就是哈希思想。

算法中时间和空间是不能兼得的，哈希表就是一种用合理的时间消耗去减少大量空间消耗的操作，这取决于具体的功能要求。

2.哈希函数

上面的例子中哈希函数的设计很随意，但是从这个例子中我们也可以得到信息：

哈希函数就是一个映射，因此哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可；

并不是所有的输入都只对应唯一一个输出，也就是哈希函数不可能做成一个一对一的映射关系，其本质是一个多对一的映射，这也就引出了下面一个概念–冲突。

3.冲突

只要不是一对一的映射关系，冲突就必然会发生，还是上面的极端例子，这时新加了一个员工号为2的员工，先不考虑我们的数组大小已经定为2了，按照之前的哈希函数，工号为2的员工哈希值也是2，这与100000000001的员工一样了，这就是一个冲突，针对不同的解决思路，提出三个不同的解决方法。

4.冲突解决方法

4.1 开放地址

开放地址的意思是除了哈希函数得出的地址可用，当出现冲突的时候其他的地址也一样可用，常见的开放地址思想的方法有线性探测再散列，二次探测再散列，这些方法都是在第一选择被占用的情况下的解决方法。

4.2 再哈希法

这个方法是按顺序规定多个哈希函数，每次查询的时候按顺序调用哈希函数，调用到第一个为空的时候返回不存在，调用到此键的时候返回其值。

4.3 链地址法

将所有关键字哈希值相同的记录都存在同一线性链表中，这样不需要占用其他的哈希地址，相同的哈希值在一条链表上，按顺序遍历就可以找到。

4.4公共溢出区

其基本思想是：所有关键字和基本表中关键字为相同哈希值的记录，不管他们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

5.装填因子α

一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子定义为表中填入的记录数和哈希表长度的壁纸，也就是标志着哈希表的装满程度。直观看来，α越小，发生冲突的可能性就越小，反之越大。一般0.75比较合适，涉及数学推导。

实现细节

CPython使用伪随机探测(pseudo-random probing)的散列表(hash table)作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键。

Python中所有不可变的内置类型都是可哈希的。

可变类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。

字典的三个基本操作（添加元素，获取元素和删除元素）的平均事件复杂度为O(1)，但是他们的平摊最坏情况复杂度要高得多，为O(N).