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，包括以下元素：
字典对象的属性，包括大小、版本标签以及键和值
一个字典的键表对象，
PyDictKeysObject，包含所有条目的键和哈希值
PyDictObject 有如下属性：
ma_keys
PyDictKeysObject*
字典键对象
ma_used
Py_ssize_t
字典中的条目数
ma_values
PyObject**
可选的值数组（见注）
ma_version_tag
uint64_t
字典的版本号
字典键表，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()。
字典查找需要考虑三种情况：
键的内存地址存在于键表中；
键的哈希值存在于键表中；
字典中不存在该键。
下面是查找函数的执行顺序：
获取
ob的哈希值；在字典键中查找
ob的哈希值，并得到索引，ix；如果
ix是空的，返回DKIX_EMPTY(未找到)；获取给定索引的键条目，
ep；如果键值与
ep->me_key相同，说明ob和ep是同一个指针，返回对应结果；如果键的哈希值与
ep->me_hash相同，需要一个个对比key与ep->me_key。
Last updated