12.7 字典类型

字典是一种快速且灵活的映射类型。它们被开发者用来存储和映射数据，也被 Python 对象用来存储属性和方法。

Python 字典也被用于局部和全局变量、关键字参数，此外还有其他很多用途。

Python 字典是紧凑的（compact），这意味着哈希表只存储映射的值。

所有内置的不可变类型的哈希算法都很快，这也是 Python 字典快的原因。

哈希

所有不可变的内置类型都提供一个哈希函数，这是在 tp_hash 类型槽中去实现的。对于自定义类型，则会使用 __hash__() 魔术方法。哈希值的大小与指针相同(64 位系统为 64 位，32 位系统为 32 位)，但它们并不代表其值的内存地址。

任何 Python 对象的哈希值在它的生命周期内都不应该改变。两个具有相同值的不可变对象实例的哈希值应该是相等的。

>>> "hello".__hash__() == ("hel" + "lo").__hash__()
True

哈希函数不应该有碰撞。两个具有不同值的对象不应该产生相同的哈希值。

有些哈希很简单，比如 Python 的整数：

>>> (401).__hash__()
401

更大的整数的哈希值会变得更加复杂。

>>> (401123124389798989898).__hash__()
2212283795829936375

许多内置类型使用 Python/pyhash.c 模块，它提供了以下哈希辅助函数。

• 字节：_Py_HashBytes(constvoid*,Py_ssize_t)

• 双精度浮点数：_Py_HashDouble(double)

• 指针：_Py_HashPointer(void*)

例如，Unicode 字符串，使用 _Py_HashBytes() 来哈希字符串的字节数据。

>>> ("hello").__hash__()
4894421526362833592

自定义类可以通过实现 __hash__() 来定义一个哈希函数。自定义类应该使用一个独特的属性，而不是实现一个自定义的哈希。通过使其属性只读来确保它是不可改变的，然后使用内置的 hash() 进行哈希。

class User:
    def __init__(self, id: int, name: str, address: str):
        self._id = id

    def __hash__(self):
        return hash(self._id)

    @property
    def id(self):
        return self._id

现在，这个类的实例可以被哈希了。

>>> bob = User(123884, "Bob Smith", "Townsville, QLD")
>>> hash(bob)
123884

这个实例也可以被用作字典的键了。

>>> sally = User(123823, "Sally Smith", "Cairns, QLD")
>>> near_reef = {bob: False, sally: True}
>>> near_reef[bob]
False

集合可以消除具有相同哈希值的实例。

>>> {bob, bob}
{<__main__.User object at 0x10df244b0>}

相关源文件

和字典相关的源文件有：

文件	用途
Include/dictobject.h	字典对象的 API 定义
Include/cpython dictobject.h	字典对象类型的定义
Objects/dictobject.c	字典对象的实现
Objects/dict-common.h	键和键对象的定义
Python/pyhash.c	内部哈希算法

字典结构

一个字典对象，PyDictObject，包括以下元素：

1. 字典对象的属性，包括大小、版本标签以及键和值

2. 一个字典的键表对象，PyDictKeysObject，包含所有条目的键和哈希值

字典结构

PyDictObject 有如下属性：

字段	类型	用途
ma_keys	PyDictKeysObject*	字典键对象
ma_used	Py_ssize_t	字典中的条目数
ma_values	PyObject**	可选的值数组（见注）
ma_version_tag	uint64_t	字典的版本号

注

字典有两种存储方式：合并表或者分离表。当字典使用合并表存储时，指向字典值的指针被存储在键对象中。

当字典使用分离表存储时，值被存储在一个额外的属性 ma_values 中，作为 PyObject* 的一个值表。

字典键表，PyDictKeysObject，有以下属性。

字段	类型	用途
dk_entries	PyDictKeyEntry[]	用于字典键条目的数组
dk_indices	char[]	映射到 dk_entries 的哈希表
dk_lookup	dict_lookup_func	查找函数（见下一节）
dk_nentries	Py_ssize_t	条目表中已使用的条目的数量
dk_refcnt	Py_ssize_t	引用计数
dk_size	Py_ssize_t	哈希表的大小
dk_usable	Py_ssize_t	条目表中可用的条目的数量，为 0 时调整字典的大小

一个字典的键条目，PyDictKeyEntry，包含以下属性：

字段	类型	用途
me_hash	Py_ssize_t	me_key 的哈希值的缓存
me_key	PyObject*	指向键对象的指针
me_value	PyObject*	指向值对象的指针（如果是合并表）

查找

对于一个给定的键对象，有一个通用的查询函数：lookdict()。

字典查找需要考虑三种情况：

1. 键的内存地址存在于键表中；

2. 键的哈希值存在于键表中；

3. 字典中不存在该键。

参见

这个查找函数基于 Donald Knuth 著名的著作《计算机编程的艺术》第 6 章第 4 节关于哈希的内容。

下面是查找函数的执行顺序：

1. 获取 ob 的哈希值；

2. 在字典键中查找 ob 的哈希值，并得到索引，ix；

3. 如果 ix 是空的，返回 DKIX_EMPTY (未找到)；

4. 获取给定索引的键条目，ep；

5. 如果键值与 ep->me_key 相同，说明 ob 和 ep 是同一个指针，返回对应结果；

6. 如果键的哈希值与 ep->me_hash 相同，需要一个个对比 key 与 ep->me_key。

注

lookupdict() 是 CPython 源代码中少数几个热点函数之一。

hot 属性用来告诉编译器一个函数是热点。该函数会被更激进地优化，在许多编译目标上，热点代码被放在代码段的一个特殊的子段中，提高了局部性。

—— GCC文档，"常用函数属性"

这是 GNU C 编译器所特有的，但当用 PGO 编译时，这个函数可能会被编译器自动优化。