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

![字典结构](/files/9ykT3huDUSm7BbpKaTiS)

`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 %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hai-shi.gitbook.io/cpython-internals/12-objects-types/12.7-the-dictionary-type.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.