一文让你彻底搞懂 Python 字典是怎么实现的

楔子

上一篇文章我们介绍了列表的实现原理，那么本次就来聊一聊字典。

首先字典是一种映射型容器对象，保存了键(key)到值(value)的映射关系。在 Python 里面字典经过高度优化的，因为不光我们在用，底层的虚拟机也在大量使用，所以通过字典可以实现键到值的快速查找，并且 JSON 这种数据结构也是借鉴了 Python 的字典。

在 Python 里面我们要如何创建一个字典呢？

# 创建一个字典
d = {"a": 1, "b": 2}
print(d)
"""
{'a': 1, 'b': 2}
"""
# 或者我们还可以通过dict, 传入关键字参数即可
d = dict(a=1, b=2, c=3, d=4)
print(d)  
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""
# 当然dict里面还可以接收位置参数, 但是最多接收一个
d1 = dict({"a": 1, "b": 2}, c=3, d=4)
d2 = dict([("a", 1), ("b", 2)], c=3, d=4)
print(d1)  
print(d2)  
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""
# 还可以根据已有字典创建新的字典
d = {**{"a": 1, "b": 2}, "c": 3, **{"d": 4}}
print(d)  
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""
#当然通过dict也是可以的
#但是注意: **这种方式本质上是把字典变成多个关键字参数
#所以里面的key一定要符合Python的变量命名规范
d = dict(**{"a": 1, "b": 2}, c=3, **{"d": 4})
print(d)  
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""
try:
    # 这种是不合法的, 因为**{1: 1}等价于1=1
    d = dict(**{1: 1})
except Exception as e:
    print(e)  # keywords must be strings
# 但下面是合法的
d = {**{1: 1, 2: 2}, **{(1, 2, 3): "嘿嘿"}}
print(d)  
"""
{1: 1, 2: 2, (1, 2, 3): '嘿嘿'}
"""

字典的底层是借助哈希表实现的，什么是哈希表我们一会儿说，总之字典添加元素、删除元素、查找元素等操作的平均时间复杂度是 O(1)。当然了，在哈希不均匀的情况下，最坏时间复杂度是 O(n)，但这种情况很少发生。

那么哈希表到底是什么样的数据结构，为什么能这么快呢？下面来分析一下。

什么是哈希表？

映射型容器的使用场景非常广泛，基本上所有的主流语言都支持。例如：C++ 里面的 map 就是一种映射型容器，但它是基于红黑树实现的。红黑树是一种平衡二叉树，元素的插入、删除、查询等操作的时间复杂度均为 O(logN)，另外 Linux 的 epoll 也使用了红黑树。

而对于 Python 来讲，映射型容器指的就是字典，我们说字典在 Python 内部是被高度优化的。因为不光我们在用，虚拟机在运行时也在大量使用，比如：自定义类、以及其实例对象都有自己的属性字典，还有全局变量也是通过字典存储的。因此基于以上种种原因，Python 对字典的性能要求会更加苛刻。

所以 Python 字典采用的数据结构，在添加、删除、查询元素等方面肯定是要优于红黑树的，没错，就是哈希表。其原理是将 key 通过哈希函数进行运算，得到一个哈希值，再将这个哈希值映射成索引。

我们举例说明：

我们发现除了key、value之外，还有一个index，因为哈希表本质上也是使用了索引。虽然数组在遍历的时候是个时间复杂度为O(n)的操作，但通过索引定位元素则是一个时间复杂度为O(1)的操作，不管数组有多长，通过索引总是能瞬间定位到指定元素。

所以哈希表实际上也是使用了数组的思想，将key映射成一个数值，作为索引。至于它是怎么映射的，我们后面再谈，现在就假设是按照我们接下来说的方法映射的。

比如这里有一个能容纳 8 个元素的字典，如上图所示。我们先设置 d["koishi"]=79，那么会对 koishi 这个字符串进行哈希运算，得到一个哈希值，然后再让哈希值对当前的总容量进行取模，这样的话是不是能够得到一个小于 8 的数呢？假设是 3，那么就存在索引为 3 的位置。

然后d["scarlet"]=83，按照同样的规则运算得到 6，那么就存在索引为 6 的位置；同理第三次设置d["satori"]=80，对字符串 satori 进行哈希、取模，得到 1，那么存储在索引为 1 的位置。

同理当我们根据键来获取值的时候，比如：d["satori"]，那么同样会对字符串 satori 进行哈希、取模，得到索引发现是1，然后就把索引为 1 的 value 给取出来。

当然这种方式肯定存在缺陷，比如：

• 不同的key进行哈希、取模运算之后得到的结果一定是不同的吗？
  
• 在运算之后得到索引的时候，发现这个位置已经有人占了怎么办？
  
• 取值的时候，索引为1，可如果索引为 1 对应的 key 和我们指定的 key 不一致怎么办？
  
  

所以哈希运算是会冲突的，如果冲突，那么Python底层会改变策略重新映射，直到映射出来的索引没有人用。比如我们设置一个新的键值对d["tomoyo"]=88，可是 tomoyo 这个 key 映射之后得到的结果也是 1，而索引为 1 的地方已经被 key 为 satori 的键值对给占了，那么 Python 就会改变规则来对 tomoyo 重新运算，找到一个空位置进行添加。

但如果我们再次设置d["satori"]=100，那么对 satori 映射得到的结果也是 1，而 key 是一致的，那么就会把对应的值进行修改。

同理，当我们获取值的时候，比如 d["tomoyo"]，那么对 key 进行映射，得到索引。但是发现该索引位置对应的 key 不是 tomoyo 而是 satori，于是改变规则（这个规则跟设置key冲突时，采用的规则是一样的），重新映射，得到新的索引，然后发现 key 是一致的，于是将值取出来。

所以从这里就已经能说明问题了，就是把 key 转换成类似数组的索引。可能有人问，这些值貌似不是连续的啊。对的，肯定不是连续的。并不是说你先存，你的索引就小、就在前面，这是由 key 进行哈希运算之后的结果决定的。

另外哈希表、或者说字典也会扩容，并且它还不是像列表那样，容量不够才扩容，而当键值对个数达到容量的三分之二的时候就会扩容。

因为字典不可能会像列表那样，键值对之间是连续、一个一个挨在一起的。既然是哈希运算，得到的哈希值肯定是随机的，再根据哈希值映射出的索引也是随机的。那么在键值对个数达到容量三分之二的时候，计算出来的索引发生碰撞的概率会非常大，不可能等到容量不够了再去扩容，而是在键值对个数达到容量的三分之二时就要扩容，也就是申请一个更大的哈希表。

一句话总结：哈希表就是一种空间换时间的方法。

假设容量为 1024，那么就相当于数组的长度为1024个位置，每个 key 都会映射成索引，找到自己的位置，将键值对存在里面。但很明显各自的位置是不固定的，肯定会空出来很多，但是无所谓，只要保证通过索引能在相应的位置找到它即可。

大量的文字会有些枯燥，我们来用两张图来解释一下设置元素和获取元素的整个过程。

以上是设置元素，还是比较清晰的，果然图像是个好东西。再来看看获取元素：

以上就是哈希表的基本原理，这也是Python早期所采用的哈希表，但是它有一个严重的问题，就是内存浪费严重。接下来我们就来看看字典的底层结构，以及 Python 是如何对哈希表进行优化的。

字典的底层结构

下面我们来看看字典的底层实现，它对应的结构体是 PyDictObject，实现还是有点复杂的。

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    uint64_t ma_version_tag;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values;
} PyDictObject;

解释一下里面的字段的含义：

• PyObject_HEAD：定长对象的头部信息，里面包含了对象的引用计数和类型。
  
• ma_used：字典里面键值对的个数，它充当了 ob_size。
  
• ma_version_tag：字典的版本号，对字典的每一次修改都会导致其改变；除此之外还有一个全局的字典版本计数器pydict_global_version，任何一个字典的修改都会影响它；并且pydict_global_version会和最后操作的字典内部的ma_version_tag保持一致，当然这个成员我们没必要关注，没太大意义。
  
• ma_keys：从定义上来看它是一个指针，指向了PyDictKeysObject。而Python里面的哈希表分为两种，分别是combined table和split table，即结合表和分离表。如果是结合表，那么键值对全部由ma_keys维护，此时ma_values为NULL。
  
• ma_values：如果是分离表，那么键由ma_keys维护，值由ma_values维护。而ma_values是一个二级指针，指向PyObject * 类型的指针数组；
  
  

这里先解释一下结合表和分离表的由来。结合表的话，键和值就存在一起；分离表的话，键和值就存在不同的地方。那么问题来了，为什么要将哈希表分为两种呢？事实上，早期的哈希表只有结合表这一种，并且现在创建一个字典使用的也是结合表。

from ctypes import *
class PyObject(Structure):
    _fields_ = [("ob_refcnt", c_ssize_t),
                ("ob_type", c_void_p)]
class PyDictObject(PyObject):
    _fields_ = [("ma_used", c_ssize_t),
                ("ma_version_tag", c_uint64),
                ("ma_keys", c_void_p),
                ("ma_values", c_void_p)]
d = {"a": 1, "b": 2}
print(
    PyDictObject.from_address(id(d)).ma_values
)  # None

我们看到ma_values打印的结果是一个None，证明是结合表，值不是由ma_values维护，而是和键一起，都由ma_keys负责维护。

而分离表是在PEP-0412中被引入的，主要是为了提高内存使用率，也就是让不同的字典共享相同的一组key。比如我们自定义类的实例对象，它们默认都有自己的属性字典，如果对某个类多次实例化，那么改成分离表会更有效率。因为它们的属性名称是相同的，完全可以共享同一组key；如果是结合表，那么每个实例的属性字典都要将相同的key单独保存一次，这显然是一种浪费。

from ctypes import *
class PyObject(Structure):
    _fields_ = [("ob_refcnt", c_ssize_t),
                ("ob_type", c_void_p)]
class PyDictObject(PyObject):
    _fields_ = [("ma_used", c_ssize_t),
                ("ma_version_tag", c_uint64),
                ("ma_keys", c_void_p),
                ("ma_values", c_void_p)]
class A:
    pass
a1 = A()
a2 = A()
#因为类型我们指定的是 void *
#所以打印的就是一串地址
#我们看到输出不为None，说明采用的确实是分离表
print(
    PyDictObject.from_address(id(a1.__dict__)).ma_values,
    PyDictObject.from_address(id(a2.__dict__)).ma_values
)  # 2885727436352 2885727434960
#然后再查看ma_keys，既然是共享同一组key
#那么它们的地址应该是一样的
print(
    PyDictObject.from_address(id(a1.__dict__)).ma_keys,
    PyDictObject.from_address(id(a2.__dict__)).ma_keys
)  # 2886174469264 2886174469264
#结果确实是一样的
#不同实例对象的属性字典里面的key是共享的
#因为是同一个类的实例对象，属性字典的key是相同的
#所以没必要将同一组key保存多次

以上就是结合表和分离表之间的区别，只需要知道分离表是Python为了提高内存使用率而专门引入的即可。我们平时自己创建的字典，使用的都是结合表，因此我们的重点也将会放在结合表身上。

而结合表的话，键值都由ma_keys维护，它是一个指向PyDictKeysObject的指针，因此玄机就隐藏在这个结构体里面。

typedef struct _dictkeysobject PyDictKeysObject;
struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;
    dict_lookup_func dk_lookup;
    Py_ssize_t dk_usable;
    Py_ssize_t dk_nentries;
    char dk_indices[];  
};

字段含义如下：

• dk_refcnt：key的引用计数，也就是key被多少个字典所使用。如果是结合表，那么该成员始终是1，因为结合表独占一组key；如果是分离表，那么该成员大于等于1，因为分离表可以共享一组key；
  
• dk_size：哈希表大小，并且大小是2的n次方，这样可将模运算优化成按位与运算；
  
• dk_lookup：探测函数，基于key的哈希值映射成索引。一个好的探测函数应该能尽量少的避免冲突，因为它对哈希表的性能起着至关重要的作用。所以底层的探测函数有很多种，会根据对象的种类选择最合适的一个。
  
• dk_usable：键值对数组的长度，关于什么是键值对数组下面会解释。
  
• dk_nentries：哈希表中已使用的entry数量，这个entry你可以理解为键值对的载体，或者干脆就理解为键值对。
  
• dk_indices：哈希索引数组，后面会解释。
  
• dk_entries：键值对数组，虽然结构体里面没有写，但它确实存在，是一个PyDictKeyEntry类型的数组，用于存储键值对、也就是上面说的entry。所以这也说明了，字典的一个键值对，在底层就是一个PyDictKeyEntry结构体实例。
  
  

然后再来看看PyDictKeyEntry对象、也就是键值对长什么样子。

typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

显然me_key和me_value指向了键和值，我们之前说Python的变量、以及容器内部的元素都是泛型指针PyObject *，这里也得到了证明。但是我们看到entry除了有键和值之外，还有一个me_hash，它表示键对应的哈希值，这样可以避免重复计算。

至此，字典的整个底层结构就非常清晰了。

字典的真正实现藏在PyDictKeysObject中，它的内部包含两个关键数组：一个是哈希索引数组dk_indices，另一个是键值对数组dk_entries。

字典所维护的键值对(entry)会按照先来后到的顺序保存在键值对数组中，而哈希索引数组则保存键值对在键值对数组中的索引。另外，哈希索引数组中的一个位置我们称之为一个槽，比如图中的哈希索引数组便有8个槽，其数量由dk_size维护。

比如我们创建一个空字典，注意：虽然字典是空的，但是容量已经有了，然后往里面插入键值对"komeiji":99的时候，Python会执行以下步骤：

1. 将键值对保存在dk_entries中，由于初始字典是空的，所以会保存在dk_entries数组中索引为0的位置。
   
2. 通过哈希函数计算出"komeiji"的哈希值，然后将哈希值映射成索引，假设是5。
   
3. 将 "键值对" 在 "键值对数组" 中的索引0，保存在哈希索引数组中索引为5的槽里面。
   
   

然后当我们在查找键"komeiji"对应的值的时候，便可瞬间定位。过程如下：

1. 通过哈希函数计算出"komeiji"的哈希值，然后映射成索引。因为在设置的时候索引是5，所以在获取时，映射出来的索引肯定也是5。
   
2. 找到哈希索引数组中索引为5的槽，得到其保存的0，这里的0对应键值对数组的索引
   
3. 找到键值对数组中索引为0的位置存储的entry，先比较key、也就是entry->me_key是否一致，不一致则重新映射。如果一致，则取出me_value，然后返回。
   
   

由于哈希值计算以及数组索引查找均是O(1)的时间复杂度，所以字典的查询速度才会这么快。当然我们上面没有涉及到索引冲突，关于索引冲突我们会在后面详细说，但是键值对的存储和获取就是上面那个流程。

另外介绍哈希表的时候，为了避免牵扯太多，说的相对简化了。比如："xxx": 80，假设"xxx"映射出来的索引是2，那么键值对就直接存在索引为2的地方。这实际上是简化了，因为这相当于把哈希索引数组和键值对数组合在一块了，而早期的Python也确实是这么做的。

但是从上面字典的结构图中我们看到，实际上是先将键值对按照先来后到的顺序存在一个数组(键值对数组)中，然后再将它在键值对数组中的索引存放在另一个数组(哈希索引数组)的某个槽里面，因为"xxx"映射出来的是2，所以就存在索引为2的槽里面。

而在查找的时候，映射出来的索引2其实是哈希索引数组中的索引。然后索引为2的槽又存储了一个索引，这个索引是键值对数组中的索引，会再根据该索引从键值对数组里面获取指定的entry。最后比较key是否相同、如果相同则返回指定的value。

所以能看出两者整体思想是基本类似的，理解起来区别不大，甚至第一种方式实现起来还更简单一些。但为什么采用后者这种实现方式，以及这两者之间的区别，我们一会再专门分析，之所以采用后者主要是基于内存的考量。

容量策略

因为字典可以扩容，那么字典肯定和列表一样有着预分配机制，为了避免频繁申请内存，所以在扩容的是时候会将容量申请的比键值对个数要多一些。那么字典的容量策略是怎么样的呢？

在Object/dictobject.c源文件中我们可以看到一个宏定义：

#define PyDict_MINSIZE 8

从这个宏定义中我们可以得知，一个字典的最小容量是8，或者说内部哈希索引数组的长度最小是8。

哈希表越密集，索引冲突则越频繁，性能也就越差。因此哈希表必须是一种稀疏的表结构，越稀疏则性能越好。但由于内存开销的制约，哈希表也不可能无限地稀疏，所以需要在时间和空间上进行权衡。

而实践经验表明，一个1/2到2/3满的哈希表，性能较为理想，能以相对合理的内存换取相对高效的执行性能。所以为保证哈希表的稀疏程度，进而控制索引冲突的频率，Python通过宏USABLE_FRACTION将哈希表的元素控制在容量的2/3以内。

宏USABLE_FRACTION会根据哈希表的长度，计算哈希表可存储的元素个数，也就是键值对数组的长度。以长度为8的哈希表为例，最多可以保存5个键值对，超出则需要扩容。

#define USABLE_FRACTION(n) (((n) << 1)/3)

哈希表规模一定是2的n次方，也就是说Python采用翻倍扩容的策略。例如长度为8的哈希表扩容后，长度会变为16。另外，这里的哈希表长度和哈希索引数组的长度是等价的。

哈希表的内存优化

在早期，哈希表并没有分成两个数组实现，而是只由一个键值对数组实现，这个数组也承担哈希索引数组的角色：

我们看到这种结构不正是我们在介绍哈希表时说的吗？一个键值对数组既用来存储，又用来充当索引，无需分成两个步骤，而且这种方式也似乎更简单、更直观。没错，Python在早期确实是通过这种方式实现的哈希表，只是这种实现方式有一个弊端，就是太耗费内存了。

因为哈希表必须保持一定程度的稀疏，最多只有2/3满，这意味着至少要浪费1/3的空间。

所以Python为了尽量节省内存，将键值对数组压缩到原来的2/3，只用来存储，而对key进行映射得到的索引由另一个数组(哈希索引数组)来承载。假设映射的索引是4，那么就去找哈希索引数组中索引为4的槽，该槽存储的便是键值对在键值对数组中的索引。

之所以这么设计，是因为键值对数组里面一个元素要占用24字节，而哈希索引数组在容量不超过255的时候，里面一个元素只占一个字节；容量不超过65535的时候，里面一个元素只占两个字节，其它以此类推。

所以哈希索引数组里面的元素大小比键值对数组要小很多，将哈希表分成两个数组(避免键值对数组的浪费)来实现会更加的节省内存。我们可以举个例子计算一下，假设有一个容量为65535的哈希表。

如果是通过第一种方式，只用一个数组来存储的话：

# 总共需要1572840字节
>>> 65535 * 24
1572840  
# 除以3, 会浪费524280字节
>>> 65535  * 24 // 3
524280
>>>

如果是通过第二种方式，使用两个数组来存储的话：

#容量虽然是65535
#但键值对数组是容量的2 / 3
#然后加上哈希索引数组的大小
>>> 65535 * 24 * 2 // 3 + 65535 * 2
1179630
>>>

所以一个数组存储比两个数组存储要多用393210字节的内存，因此Python选择使用两个数组来存储。

最后再来提一下字典的顺序问题，Python从3.6开始，字典的遍历是有序的，那么这是怎么实现的呢？

其实很简单，在存储时，虽然映射之后的索引是随机的，但键值对本身始终是按照先来后到的顺序被添加进键值对数组中。而字典在for循环时，会直接遍历键值对数组，所以遍历的结果是有序的。但即便如此，我们也不应该依赖此特性。

所以通过研究字典的具体实现，我们可以得到以下结论：

• 字典是一种高效的映射型容器，能够以 O(1) 的时间复杂度执行查询和写入操作；
  
• 字典之所以这么快，是因为它由哈希表实现。但快是要付出代价的，哈希表必须保证一定的稀疏性，否则会频繁出现索引冲突，导致哈希表性能下降，因为在索引映射的时候是随机的；
  
• 既然哈希表要保证稀疏性，就意味着内存开销大，因为会有内存浪费。所以为平衡内存开销与搜索效率，哈希表最好在 1/2 到 2/3 满；
  
• 但 Python 为优化内存使用，选择使用两个数组来实现哈希表，通过避免键值对数组的浪费，来减少内存占用；
  

不过还没有结束，哈希表的背后还隐藏了很多细节。比如：key到底是如何映射成索引的？索引冲突了怎么办？哈希攻击又是什么？以及删除元素也会面临一些问题，又是如何解决的？

下面我们就来逐一回答。

对象的哈希值

Python内置函数hash可以计算对象的哈希值，哈希表依赖于哈希值。而根据哈希表的性质，我们知道键对象必须满足以下两个条件，否则它无法容纳在哈希表中。

• 哈希值在对象的整个生命周期内不可以改变；
  
• 可比较，如果两个对象相等，那么它们的哈希值一定相同；
  
  

满足这两个条件的对象便是可哈希(hashable)对象，只有可哈希对象才可以作为哈希表的键(key)。因此像字典、集合等底层由哈希表实现的数据结构，其元素必须是可哈希对象。

Python内置的不可变对象都是可哈希对象，比如：整数、浮点数、字符串、只包含不可变对象的元组等等；而像可变对象，比如列表、字典等等便不可作为哈希表的键。

#键是可哈希的就行，值是否可哈希则没有要求
>>> {1: 1, "xxx": [1, 2, 3], 3.14: 333}  
{1: 1, 'xxx': [1, 2, 3], 3.14: 333}
>>>
# 列表是可变对象，因此无法哈希
>>> {[]: 123}  
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>
# 元组也是可哈希的
>>> {(1, 2, 3): 123}  
{(1, 2, 3): 123}
#但如果元组里面包含了不可哈希的对象
#那么整体也会变成不可哈希对象
>>> {(1, 2, 3, []): 123} 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>

而我们自定义类的实例对象也是可哈希的，并且哈希值是通过对象的地址计算得到的。

class A:
    pass
a1 = A()
a2 = A()
print(hash(a1), hash(a2)) 
"""
141215868971 141215869022
"""

当然Python也支持我们重写哈希函数，比如：

class A:
    def __init__(self, name):
        self.name = name
    def __hash__(self):
        return 123
    def __repr__(self):
        return self.name
a1 = A("ping")
a2 = A("pong")
print(hash(a1), hash(a2))  # 123 123
print({a1: 1, a2: 2})  # {ping: 1, pong: 2}

我们看到虽然哈希值一样，但是在作为字典的键的时候，如果发生了冲突，会改变规则重新映射，因为类的实例对象之间默认是不相等的。

注意：我们自定义类的实例对象默认都是可哈希的，但如果类里面重写了__eq__方法，且没有重写__hash__方法的话，那么这个类的实例对象就不可哈希了。

class A:
    def __eq__(self, other):
        return True
a1 = A()
a2 = A()
try:
    print(hash(a1), hash(a2))
except Exception as e:
    print(e)  # unhashable type: 'A'

为什么会有这种现象呢？首先我们说，在没有重写__hash__的时候，哈希值默认是根据对象的地址计算得到的。而且对象如果相等，那么哈希值一定是一样的。

但是我们重写了__eq__，相当于控制了==操作符的比较结果，两个对象是否相等就是由我们来控制了，可哈希值却还是根据地址计算得到的。因此两个对象地址不同，哈希值不同，但是对象却可以相等、又可以不相等，这就导致了矛盾。所以在重写了__eq__、但是没有重写__hash__的情况下，其实例对象便不可哈希了。

但如果重写了__hash__，那么哈希值计算方式就不再通过地址计算了，因此此时是可以哈希的。

class A:
    def __init__(self, name):
        self.name = name
    def __hash__(self):
        return 123
    def __repr__(self):
        return self.name
    def __eq__(self, other):
        return True
a1 = A("ping")
a2 = A("pong")
print(hash(a1), hash(a2))  # 123 123
print({a1: 1, a2: 2})  # {ping: 2}

我们看到字典里面只有一个元素，因为重写了__hash__方法之后，计算得到哈希值都是一样的。如果没有重写__eq__，实例对象之间默认是不相等的。因此哈希值一样，但是对象不相等，那么会重新映射。但我们重写了__eq__，返回的结果是True，所以Python认为对象是相等的，由于key的不重复性，保留了后面的键值对。

class A:
    def __init__(self, name):
        self.name = name
    def __hash__(self):
        return 123
    def __repr__(self):
        return self.name
    def __eq__(self, other):
        return False
a1 = A("ping")
a2 = A("pong")
# 我们看到 a1 == a1 为 False
print(a1 == a1)  # False
# 但是只保留了一个key，原因是地址一样
# 在比较是否相等之前，会先判断地址是否一样
# 如果地址一样，那么认为是同一个key
print({a1: 1, a1: 2})  # {ping: 2}
# 此时会保留两个key
# 因为 a1 和 a2 地址不同，a1 == a2 也为False
# 所以哈希表认为这是两个不同的 key
# 但由于哈希值一样，那么映射出来的索引也一样
# 因此写入 a2:2 时相当于发生了索引冲突，于是会重新映射
# 但总之这两个key都会被保留
print({a1: 1, a2: 2})  # {ping: 1, pong: 2}

同样的，我们再来看一个Python字典的例子。

d = {1: 123}
d[1.0] = 234
print(d)  # {1: 234}
d[True] = 345
print(d)  # {1: 345}

天哪噜，这是咋回事？首先整数在计算哈希值的时候，得到结果就是其本身；而浮点数显然不是，但如果浮点数的小数点后面是0，那么它和整数是等价的。

因此1和1.0的哈希值一样，并且两者也是相等的，因此它们被视为同一个key，所以相当于是更新。同理True也一样，因为bool继承自int，所以它等价于1，比如：9 + True = 10。因此True和1相等，并且哈希值也相等，那么索引d[True] = 345同样相当于更新。

但是问题来了，值更新了我们可以理解，字典里面只有一个元素也可以理解，可为什么key一直是1呢？理论上最终结果应该是True才对啊。其实这算是Python偷了个懒吧(开个玩笑)，因为key的哈希值是一样的，并且也相等，所以Python不会对key进行替换。

从字典在设置元素的时候我们也知道，如果对key映射成索引之后，发现哈希索引数组的该槽没有人用，那么就按照先来后到的顺序将键值对存储在键值对数组中，再把它在键值对数组中的索引存在哈希索引数组的指定槽中。

但如果发现槽有人用了，那么根据槽里面存的索引，去键值对数组中查找指定的entry，然后比较两个key是否相等。如果对应的key不相等，则重新映射找一个新的槽；如果相等，则说明是同一个key，那么把value换掉即可。

所以在替换元素的整个过程中，根本没有涉及到对键的修改，因此上面那个例子的最终结果，value会变、但键依旧是1，而不是True。

总之理想的哈希函数必须保证哈希值尽量均匀地分布于整个哈希空间中，越是相近的值，其哈希值差别应该越大。还是那句话，哈希函数对哈希表的好坏起着至关重要的作用。

索引冲突

不同的对象，计算出的哈希值有可能相同，即使哈希值不同，映射出的索引也可能相同。因为与哈希值空间相比，哈希表的槽位是非常有限的。如果不同的对象在经过映射之后，得到的索引相同，或者说它们被映射到了同一个槽，那么便发生了索引冲突。

解决索引冲突的常用方法有两种：

• 分离链接法(separate chaining)
  
• 开放寻址法(open addressing)
  
  

其中Python采用的便是开放寻址法，下面来看看这两种做法之间的区别。

分离链接法

分离链接法为每个哈希槽维护一个链表，所有哈希到同一槽位的键都保存到对应的链表中：

如上图所示，哈希表的每一个槽都连接着一个链表，初始状态为空，映射到哈希表同一个槽的键则保存在对应的链表中。而使用分离链接法的哈希表，一般都是基于一个数组实现。

开放寻址法

首先依旧是将key映射成索引，并存在哈希索引数组的槽中，若发现槽被占了，那么就尝试另一个。

key2被映射到索引为3的槽时，发现这个坑被key1给占了，所以只能重新找个坑了。但是为什么找到5呢？显然在解决索引冲突的时候是有策略的，一般而言，如果是第i次尝试，那么会在首槽的基础上加上一个偏移量d(i)。比如映射之后的索引是n，那么首槽就是n，然而索引为n的槽被占了，于是重新映射，而重新映射之后的索引就是n+d(i)。

所以可以看出探测方式因函数d(i)而异，而常见的探测函数也有两种：

• 线性探测(linear probing)
  
• 平方探测(quadratic probing)
  
  

线性探测很好理解，d(i)是一个线性函数，例如d(i)=2*i+1

假设哈希之后对应的槽是1，但是被占了，这个时候会在首槽的基础上加一个偏移量d(i)。第1次尝试，偏移量是2；第2次尝试，偏移量是4；第3次尝试，偏移量是6。然后再加上首槽的1，所以尝试之后的位置分别是3、5、7。

平方探测也很好理解，d(i)是一个平方函数，比如 i 的平方。如果是平方探测，假设首槽还是 1，那么冲突之后重试的槽就是1 + 1、1 + 4、1+ 9。

线性探测和平方探测都比较简单，但从效果上来看，平方探测似乎更胜一筹。如果哈希表存在局部热点，线性探测很难快速跳过热点区域，而平方探测则可以解决这一点。但其实这两种方法其实都不够好，因为固定的探测序列加大了冲突的概率。比如：

key1和key2都映射到了索引为 1 的槽，而由于探测序列是相同的，因此后续可能出现多次冲突。

所以Python对此进行了优化，探测函数会参考对象哈希值，生成不同的探测序列，进一步降低索引冲突的可能性：

Python的这种做法被称为迭代探测，当然迭代探测也属于开放寻址法的一种。所以当出现索引冲突时，Python并不是简简单单地加上一个偏移量，而是使用专门设计的探测函数进行二次探查，也就是之前说的改变规则、重新映射，然后在函数内部会参考对象的哈希值来计算出一个新的索引。

探测函数

Python为哈希表搜索提供了多种探测函数，例如lookdict, lookdict_unicode, lookdict_index，一般通用的是 lookdict。

lookdict_unicode 是专门针对key为字符串的entry，lookdict_index针对key为整数的entry，可以把lookdict_unicode和lookdict_index看成是lookdict的特殊实现，只不过key是整数和字符串的场景非常常见，因此为其单独实现了一个函数。

当要存储一个键值对时，会通过探测函数为 key 寻找一个合适的槽，如果探测函数执行的时候发现索引冲突了，并且key还不相等，那么会改变规则重新映射。也就是说，在探测函数里面，会不断尝试解决冲突，直到映射出一个可用的索引。

函数的具体源代码，感兴趣的话可以自己去查看，我这里简单说一下大致流程。

先用哈希函数计算出 key 的哈希值，然后作为参数传递到探测函数中。在探测函数里面，会将哈希值和 mask 按位与得到索引。

mask 等于哈希表的容量减 1，这里涉及到了一个小技巧，如果 n 是 2 的整数次幂，那么 m % n 和 m & (n - 1) 是等价的，但按位与的速度要比取模快很多。所以哈希表的容量是 2 的整数次幂，就是为了在映射索引的时候，将取模优化成按位与。

理想情况下，得到的索引是不冲突的。但如果冲突了，那么探测函数内部会改变规则，重新映射，这里的规则如下：

//将当前哈希值右移PERTURB_SHIFT个位
perturb >>= PERTURB_SHIFT;
//然后将哈希值加上 i*5 + 1，这个 i 就是当前冲突的索引
//运算之后的结果再和mask按位与，得到一个新的 i
//然后判断变量 i 是否可用，不可用则重复当前逻辑
//直到出现一个可用的槽
i = (i*5 + perturb + 1) & mask;

至于为什么这么做，可以认为是Python总结出的经验，这种做法在避免索引冲突时的表现比较好。总之在重新映射的时候，会参考对象的哈希值，探测序列因哈希值而异。

哈希攻击

假设有一些想搞事的人向我们的接口传递了大量哈希值相同的key，会发生什么事情呢？显然哈希表将频繁发生索引冲突，探测函数会不断地重新映射，从而导致性能由O(1)急剧下降为O(N)，这便是哈希攻击。

哈希攻击是一种 DOS 攻击，一旦后端接口存在合适的攻击面，攻击者就能轻松让服务器陷入瘫痪。而Python在3.3以前，就存在这种漏洞，当时哈希函数只根据对象本身计算哈希值。因此只要解释器版本相同，对象哈希值也会相同，这是很危险的。

问题虽然很严重，但解决方法很简单，直接往对象身上撒把盐(salt)即可。解释器启动后，会产生一个随机数作为盐，哈希函数同时参考对象本身以及随机数计算哈希值。

这样一来，攻击者由于无法获取解释器内部的随机数，也就无法构造出哈希值相同的 key 了。Python自3.3以后，哈希函数均采用加盐模式，杜绝了哈希攻击的可能性。Python哈希算法在pyhash.c源文件中实现，有兴趣可以自己去了解一下，这里就不展开了。

我们只需要知道索引冲突时，Python是怎么做的即可，至于如何设计一个哈希函数，以及Python底层使用的哈希函数的具体逻辑，就不在我们的展开范围之内了。

哈希表能直接删除元素吗？

现在我们已经知道哈希表是先通过哈希函数计算出键的哈希值，然后将哈希值传递到探测函数中，再将哈希值映射为一个索引，最终通过索引去访问连续的内存区域。而哈希表这种数据结构，最终目的就是加速键的搜索过程。

并且我们知道，当键值对数量越多，在映射成索引之后就越容易出现冲突。而如果冲突了，就改变规则重新映射，这种方法叫做开放寻址法。当发生冲突时，在探测函数内部会参考哈希值以及冲突的索引，计算下一个候选位置，如果可用就设置进去。如果不可用，会继续重复此过程，直到找到一个可用的位置。

通过多次探测，可以从一个位置到达多个位置，我们认为这些位置就形成了一个冲突探测链(探测序列)。比如当我们插入一个key="satori"的键值对时，在位置a发现不行，又走到位置b，发现也被人占了，于是到达位置c，而位置c没有键值对，于是就存在了这里。

那么经过以上流程，a -> b -> c 便形成了一条冲突探测链，同理我们查找的时候也会按照这个顺序进行查找。

显然上面这些东西，现在理解起来已经没什么难度了，但是问题来了。

如果我此时把上面位置b的entry给删掉的话，会引发什么后果？

首先当我们获取d["satori"]时，肯定会先到达位置a，发现存在entry（键值对）、但key不是字符串satori，于是重新映射；然后走到位置b，发现还不对，再走到位置c，发现key是satori，于是就把值取出来了。显然这符合我们的预期，但是，我要说但是了。

如果我们把位置b上的entry删掉呢？那么老规矩，映射成索引，先走到位置a，但是发现坑被占；于是又走到位置b，结果发现居然没有entry，那么直接就报出了一个KeyError。

所以继续寻找的前提是，这个地方要存储了entry，并且存在的entry -> me_key和指定的key不相同；但如果没有的话，就说明根本没有这个key，直接KeyError。

然而satori这个key确实是存在的，因此这种情况我们称之为探测链断裂。本来应该走到位置c的，但由于位置b没有元素，导致探测函数在位置b就停止了。

因此我们发现，当一个元素只要位于任何一条探测链当中，在删除时都不能真正意义上的删除。所以元素的删除，其实是一种伪删除操作。

//一个键值对就是一个entry
//在底层就是一个 PyDictKeyEntry 实例
typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

而当一个PyDictObject对象发生变化时，其中的entry会在三种不同的状态之间进行切换：unused态、active态、dummy态。

unused态

当一个entry的me_key和me_value都是NULL的时候，entry处于unused态。unused态表明该entry中并没有存储key、value，并且在此之前也没有存储过它们，每一个entry在初始化的时候都会处于这个状态。

不过me_value的话，即使不是unused态也可能为NULL，更准确的说不管何时它都可能会为NULL，这取决于哈希表到底是结合表、还是分离表。

如果是分离表的话，value是不存在这里的，只有key存在这里，因此me_value永远是NULL。而如果是结合表，那么key和value都存在这里面。所以对于me_key，只在unused态的时候才可能为NULL。

active态

当entry存储了key时，那么此时entry便从unused态变成了active态。

dummy态

当某个key被删除时，它所在的entry便从active态变成dummy态，否则就会发生我们之前说的探测链断裂。至于这个dummy到底是啥，我们一会儿说。总之entry进入dummy态，就是我们刚才提到的伪删除技术。

当Python沿着某条探测链搜索时，如果发现一个entry处于dummy态，就会明白虽然当前的entry是无效的，但是后面的entry可能是有效的。所以不会报错，而是会继续搜索，这样就保证了探测链的连续性。

至于报错，是在找到了unused态的entry时才会报错，因为这里确实一直都没有存储过key。但索引又是当前这个位置，因此指定的key就真的不存在哈希表中，此时才会报错。

以上是三种状态之间的转换，unused态只能转换为active态；active态只能转换为dummy态；dummy态只能转化为active态。

当entry被使用时，它便由unused态转为active态，此时me_key由NULL变成非NULL；当删除某个key时，它所在的entry便由active态转为dummy态。

那么问题来了，dummy态转为active态，你能猜到会在什么时候发生吗？

很容易想到，如果新来了一个key，这个key在存储的时候发生冲突，也就是找到的entry存储了别的key，那么会沿着冲突探测链继续查找。在查找的时候要是遇到了处于dummy态的entry，那么该entry就会从dummy态变成active态。

换句话说，对于处于dummy态的entry，Python 不会主动处理它，只是说这个元素被标记为删除了，但内存还会继续占用。如果新来的key，没有发生冲突，一上来就有位置可以存储，那么不会理会dummy态的entry。

只有当发生冲突的时候，正好撞上了dummy态的entry，才会将dummy态的entry给替换掉。此时entry就变成了active态，然后内部维护的就是新的键值对。另外当哈希表满了发生扩容的时候，会将所有的active态的entry都搬过去，而处于dummy态的entry则直接丢弃。

之所以可以丢弃，原因是dummy态的entry存在是为了保证探测链不断裂，但现在所有active态的entry都拷贝到新的内存当中了，它们会形成一条新的探测链，因此也就不需要这些dummy态的entry了。

所以再让我们回顾一下字典的底层结构，它里面有一个ma_used字段，维护的是键值对的数量；还有一个dk_nentries，它维护键值对数组中已使用的entry数量，而这个entry又可以理解为键值对。那么问题来了，这两者有什么区别呢？

相信你已经猜到了，如果不涉及元素的删除，那么两者的值会是一样的。而一旦删除某个已存在的key，那么ma_used会减1，而dk_nentries则保持不变。

首先ma_used减1表示键值对数量相比之前少了一个，这显然符合我们在Python里面使用字典时的表现；但我们知道元素的删除其实是伪删除，会将对应的entry从active态变成dummy态，然而entry的总数量并没有改变。

也就是说，ma_used其实等于active态的entry总数；如果将dk_nentries减去dummy态的entry总数，那么得到的就是ma_used。所以这就是两者的区别，我们对一个字典使用len函数，获取的也是ma_used，而不是dk_nentries。

static Py_ssize_t
dict_length(PyDictObject *mp)
{
    return mp->ma_used;
}

小结

以上就是 Python 的字典，建议大家在工作中多多使用它，它的性能是非常高效的。因为不光我们在用，虚拟机本身也在大量使用。那么问题来了，虚拟机内部都有哪些结构使用了字典呢？这里随便举两个：

类和类的实例对象

class A:
    pass
# 类有自己的属性字典
print(type(A.__dict__))
"""
<class 'mappingproxy'>
"""
# mappingproxy 本质上是对字典的一个封装
# 屏蔽了字典增删改操作，只允许读取
# 类的实例对象有自己的属性字典
print(type(A().__dict__))
"""
<class 'dict'>
"""

全局名字空间

Python 的所有全局变量都保存在一个字典中，我们可以通过 globals 函数获取它。

# 等价于往字典中写入一个键值对
name = "古明地觉"
# 等价于从字典中获取
print(name)
print(globals()["name"])
"""
古明地觉
古明地觉
"""
globals()["address"] = "地灵殿"
print(address)
"""
地灵殿
"""

所以全局变量的存储和写入都是基于字典操作的，这就决定了字典必须经过高度优化。