Python中的dict对象表示它是一种原始的Python数据类型，以键值对的形式存储，其中文名称翻译成字典。效率高，时间复杂度恒定O(1)。本文对其实现的数据结构原理进行讲解和扩展，不涉及Python的源码分析。dict底层是用Python2实现的。dict底层是通过哈希表（HashTable）实现的，采用地址开放的方式来解决冲突。因此，其查找的时间复杂度会是O(1)，后面会详细解释hash。表如何工作以及如何解决冲突。哈希表哈希表是key-value类型的数据结构，可以直接通过键码值访问。哈希函数用于将键的下标与数组进行映射，从而确定键值应该放在哪里。**哈希表可以理解为需要按照一定规则存储key值的数组，哈希函数就是这个规则。**这里提出几个专业术语，后面会一一介绍。1.哈希函数2.填充因子3.碰撞1.哈希表的产生原因假设我们有一个简单的键值对结构，键-员工编号，值-是否在职。现在我们需要这样一个函数，输入员工编号，返回员工是否在职，理想的方式是创建一个长度为Max（员工编号）的数组，数组下标为员工编号，取值数组中有0和1来匹配员工是否在职区分，这样可以只用O(1)的时间复杂度完成运算，但是可扩展性不强，存在以下问题。1、假设新员工的员工号大于Max（员工号），需要重新申请数组进行迁移操作。2、假设一个极端情况，有两个员工，员工编号分别为1和100000000001。在这种情况下，按照之前的设计思路，会浪费大量的存储空间。以上两点，第一点是由数组固定应用大小的属性决定的，第二点是哈希表引入的原因。有没有办法让大员工号变小而不打标？生成哈希函数。假设这里的哈希规则除以3取模，员工1得到的哈希值为1，员工100000000001得到的哈希值为2。这种情况下，按照设计思路，只有一个大小为一个数组of2是可以覆盖的，这就是散列的思想。在算法中，时间和空间是不能结合的。哈希表是一种使用合理的时间消耗来减少大量空间消耗的操作，这取决于具体的功能需求。2.哈希函数上面例子中哈希函数的设计很随意，但是从这个例子中我们也可以得到信息：哈希函数是一个映射，所以哈希函数的设置非常灵活，只要任意关键字得到的哈希函数值都在表长允许的范围内；并不是所有的输入都只对应一个输出，即哈希函数不能做成一对一的映射关系。它的本质是一个多对一的映射，这就导致了下面的概念冲突。3.冲突只要不是一对一的映射关系，就必然会发生冲突。还是上面那个极端的例子。这时候新增了一个员工编号为2的员工，不管我们的数组大小已经设置为2。根据前面的哈希函数，工号为2的员工的哈希值也为2，和100000000001的employee是一样的，这是冲突。针对不同的解决方案，提出了三种不同的解决方案。4.冲突解决方法4.1开放地址开放地址是指发生冲突时，除了哈希函数得到的地址可用外，其他地址也可用。开放地址思维常用的方法是线性检测，然后哈希。Probe然后hash，这些方法都是第一个选择被占用时的解法。4.2重新散列法这种方法是依次指定多个散列函数，每次查询时依次调用散列函数。当第一个被调用为空时，它将返回不存在。价值。4.3链地址法将所有具有相同关键字哈希值的记录存储在同一个线性链表中，这样就不需要其他的哈希地址，在一个链表上依次遍历就可以找到相同的哈希值。4.4公共溢出区的基本思想是：所有关键字与基础表中的关键字哈希值相同的记录，无论哈希函数得到的哈希地址是什么，一旦发生冲突，将填写在溢出表中。5.填充因子α一般来说，对于冲突处理方式相同的哈希表，平均查找长度取决于哈希表的填充因子。哈希表的填充因子定义为表中填充的记录数与哈希表长度的墙纸，即哈希表的填充程度。直观上，α越小，冲突的可能性越小，反之亦然。一般0.75比较合适，涉及数学推导。实现细节CPython使用伪随机探测哈希表作为字典的底层数据结构。由于这个实现细节，只有可散列的对象可以用作字典键。Python中所有不可变的内置类型都是可哈希的。可变类型（例如列表、字典和集合）不可散列，因此不能用作字典键。字典的三个基本操作（添加元素、获取元素和删除元素）的平均情况复杂度为O(1)，但它们的分摊最坏情况复杂度要高得多，为O(N)。
