# 12.7 字典类型

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

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

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

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

## 哈希

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

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

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

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

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

```py
>>> (401).__hash__()
401
```

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

```py
>>> (401123124389798989898).__hash__()
2212283795829936375
```

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

* **字节**：`_Py_HashBytes(constvoid*,Py_ssize_t)`
* **双精度浮点数**：`_Py_HashDouble(double)`
* **指针**：`_Py_HashPointer(void*)`

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

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

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

```python
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
```

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

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

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

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

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

```py
>>> {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`，包含所有条目的键和哈希值

![字典结构](https://1029588898-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FJhewUmzI3BNeGgeFH9Rv%2Fuploads%2Fgit-blob-b45f6e5a9d18fd99814172a4fe9a55facba2ff39%2F%E5%9B%BE12.7%20%E5%AD%97%E5%85%B8%E7%BB%93%E6%9E%84.jpg?alt=media)

`PyDictObject` 有如下属性：

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

{% hint style="info" %}
**注**

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

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

字典键表，`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. 字典中不存在该键。

{% hint style="info" %}
**参见**

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

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

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`。

{% hint style="info" %}
**注**

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

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

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