16. 字典和集合

字典和集合是 CPython 的主要哈希表容器。字典将键映射到值。集合存储没有关联值的键。

它们在 Python 中无处不在：```text id="cp7dx7" module globals class namespaces instance attributes keyword arguments function annotations import caches memoization tables membership indexes deduplication sets

## 16.1 字典语义

字典将可散列键映射到值。```python id="cvrlq9"
d = {
    "name": "Ada",
    "age": 36,
}

print(d["name"])    # Ada
```键必须是可散列的。值可以是任何对象。```python id="mb4tqx"
d = {}

d["x"] = []
d[42] = object()
d[(1, 2)] = "tuple key"
```当一个键具有稳定的哈希值并且支持与该哈希兼容的相等比较时，该键是可哈希的。```python id="100k2v"
hash("name")        # works
hash((1, 2))        # works
hash([1, 2])        # TypeError
```列表是不可散列的，因为它们的内容可以更改。

## 16.2 集合语义

集合存储唯一的可散列元素。```python id="a9i1rs"
seen = set()

seen.add("x")
seen.add("x")

print(seen)         # {'x'}
```当您需要成员资格测试、重复数据删除或集合代数时，集合非常有用。```python id="utkml3"
a = {"red", "green", "blue"}
b = {"green", "yellow"}

print(a & b)        # intersection
print(a | b)        # union
print(a - b)        # difference
```一个`frozenset`如果所有元素都是可散列的，则它是不可变且可散列的。```python id="8f3u4m"
key = frozenset(["read", "write"])
d = {key: "permissions"}
```## 16.3 哈希表

字典和集合都是哈希表。

哈希表使用哈希值来查找对象应位于内部表中的位置。

对于字典查找：```text id="kobvyn"
hash key
find candidate slot
compare stored key with lookup key
return value if equal
```对于集合成员资格：```text id="hbs3i1"
hash element
find candidate slot
compare stored element with lookup element
return present or absent
```平均情况查找是常数时间：```text id="qme3op"
d[key]      average O(1)
key in d    average O(1)
x in set    average O(1)
```当许多键发生冲突时，最坏情况的行为可能会降低，但 CPython 包含冲突处理和哈希随机化防御。

## 16.4 哈希和等式合约

哈希合约是：```text id="u4q6w3"
if a == b, then hash(a) == hash(b)
```不需要相反的操作：```text id="2ibsgd"
if hash(a) == hash(b), a may still be different from b
```当两个不相等的对象具有相同的哈希值时，就会发生冲突。

字典通过比较键来处理冲突。

自定义键示例：```python id="7h6xvk"
class Key:
    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        return isinstance(other, Key) and self.value == other.value

    def __hash__(self):
        return hash(self.value)
```如果你定义`__eq__`，定义一个兼容的`__hash__`仅当对象不可变到足以进行散列时。

## 16.5 可变键是危险的

当密钥位于字典或集合中时，密钥的哈希必须保持稳定。

这很糟糕：```python id="51z0wo"
class BadKey:
    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        return isinstance(other, BadKey) and self.value == other.value

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

k = BadKey("a")
d = {k: "value"}

k.value = "b"
```突变后，该对象可能不再在表中找到。```python id="u2wkp9"
print(d.get(k))     # may fail unexpectedly
```字典根据旧的哈希值放置密钥。查找使用新的哈希值。

使用不可变的关键数据。```python id="mzfzuj"
key = ("user", 123)
```## 16.6 字典对象布局

CPython 字典对象存储元数据并指向表数据。

从概念上讲：```text id="36zah2"
PyDictObject
    object header
    used count
    version tag
    keys table pointer
    values pointer for split-table dicts
```内部布局经过优化且特定于版本，但关键思想是：```text id="kpjby5"
dictionary object
    controls a hash table
    stores keys and values
    resizes as needed
```字典不会将键和值对象内嵌存储为原始值。它存储对 Python 对象的引用。```text id="jxgd18"
dict entry
    key pointer   ---> Python object
    value pointer ---> Python object
    hash value
```## 16.7 组合表和拆分表

CPython 字典可以使用不同的内部布局。

组合表将键和值存储在一起。```text id="kswrs2"
entry
    hash
    key pointer
    value pointer
```拆分表将共享键与每个实例的值分开。

这对于同一类对象的实例字典很有用。

例子：```python id="pr3ahp"
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

a = Point(1, 2)
b = Point(3, 4)
```两个实例都有属性`x`和`y`。

CPython 可以共享类实例布局的关键元数据，同时每个实例存储自己的值。

从概念上讲：```text id="4gdmgx"
shared keys table
    "x"
    "y"

instance a values
    1
    2

instance b values
    3
    4
```这减少了许多具有相同属性名称的实例的内存使用量。

## 16.8 广告订单

字典保留插入顺序。```python id="jf7ccx"
d = {}
d["a"] = 1
d["b"] = 2
d["c"] = 3

print(list(d))      # ['a', 'b', 'c']
```更新现有密钥不会移动它：```python id="2d4s8h"
d["b"] = 20
print(list(d))      # ['a', 'b', 'c']
```删除并重新插入会创建一个新的插入位置：```python id="2tmw4q"
del d["b"]
d["b"] = 200

print(list(d))      # ['a', 'c', 'b']
```插入顺序是现代 Python 中字典的语言行为，而不仅仅是一个偶然的 CPython 细节。

## 16.9 字典查找

字典查找有几个阶段。```python id="fq8zvc"
value = d[key]
```从概念上讲：```text id="5w58mp"
compute hash(key)
choose initial table slot
inspect slot
    if empty: key missing
    if stored hash differs: continue probing
    if stored key is key: found
    if stored key == key: found
    otherwise continue probing
```如果可能的话，在相等性之前检查身份。如果使用相同的对象作为键，查找可以避免相等工作。```python id="b3vf1x"
key = "name"
d = {key: "Ada"}

print(d[key])
```对于字符串，缓存的哈希值和驻留可以使查找速度特别快。

## 16.10 碰撞处理

不同的密钥可以具有相同的哈希值。```python id="u61im9"
class Collide:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        return 1

    def __eq__(self, other):
        return isinstance(other, Collide) and self.value == other.value
```所有实例散列到`1`。```python id="sn5hoa"
d = {}
for i in range(100):
    d[Collide(i)] = i
```该字典仍然有效，但性能会受到影响，因为需要进行许多探测和相等检查。

哈希随机化有助于保护类似字符串的密钥免受面向网络的程序中可预测的冲突攻击。

## 16.11 调整大小

当字典太满时，它会调整大小。

目标是通过在表中保留空白空间来保持查找效率。

从概念上讲：```text id="km324o"
insert key
    if table load is high:
        allocate larger table
        reinsert active entries
    insert new key
```调整规模成本`O(n)`目前确实发生了这种情况，但插入平均而言仍然有效。

这在本质上与列表超额分配类似。容器使用额外的内存来保持常见操作的快速运行。

## 16.12 删除和虚拟条目

删除字典键并不总是将槽标记为空。

为什么？

因为查找可能依赖于探针链。如果删除破坏了链条，则后续的密钥可能会变得无法访问。

因此哈希表通常对已删除的槽使用虚拟标记。

从概念上讲：```text id="o8jbeg"
active slot
    contains key and value

empty slot
    never used

dummy slot
    used before, now deleted
```插入可以重复使用虚拟插槽。查找必须跳过它们。

太多的虚拟插槽会损害性能，因此调整大小或重建可以清理它们。

## 16.13 字典视图

字典视图对象公开键、值或项目的动态视图。```python id="ovth2c"
d = {"a": 1, "b": 2}

keys = d.keys()
values = d.values()
items = d.items()
```视图反映了后来的突变：```python id="bjim9l"
keys = d.keys()

d["c"] = 3

print(keys)     # dict_keys(['a', 'b', 'c'])
```视图避免复制。它们是指向字典的轻量级对象。

要制作快照，请显式复制：```python id="k65165"
keys_snapshot = list(d.keys())
```## 16.14 迭代字典

迭代字典会产生键。```python id="ra7i88"
for key in d:
    print(key)
```相等的：```python id="4hpn52"
for key in d.keys():
    print(key)
```在迭代期间，更改字典的大小会引发错误：```python id="4085f6"
for key in d:
    d["new"] = 1      # RuntimeError
```通常允许在不更改键的情况下改变值：```python id="t0n9jz"
for key in d:
    d[key] += 1
```迭代器依赖于字典结构保持一致。

## 16.15 词典版本标签

CPython 字典可以维护当字典更改时也会更改的版本信息。

版本标签对于运行时优化非常有用，尤其是缓存。

例如，属性查找和全局查找可以在字典保持不变时缓存信息。

从概念上讲：```text id="pfdsrf"
dict version = 100
cache lookup result for name "x"

later:
    if dict version still 100:
        cached result may be valid
    else:
        redo lookup
```这是一个在不改变 Python 语义的情况下加速动态查找的主要工具。

## 16.16 全局变量是字典

模块的全局命名空间是一个字典。```python id="h0m5e5"
x = 10

globals()["x"] = 20

print(x)        # 20
```当 Python 代码读取全局变量时，CPython 在模块全局中执行字典查找，并回退到内置变量。

从概念上讲：```text id="v5m31f"
LOAD_GLOBAL name
    look in globals dict
    if missing, look in builtins dict
```因为全局变量是字典，所以全局变量访问取决于字典的性能。 CPython 使用内联缓存和版本标签来加速此路径。

## 16.17 实例属性通常是字典

普通对象实例通常将属性存储在字典中。```python id="zdzzxk"
class User:
    pass

u = User()
u.name = "Ada"
u.age = 36

print(u.__dict__)
```输出：```text id="ijc7p2"
{'name': 'Ada', 'age': 36}
```属性访问：```python id="6pnbk6"
u.name
```在描述符检查和类型级查找之后，通常会变成字典查找。

CPython 通过分割字典、共享密钥和属性缓存对此进行了大量优化。

## 16.18 类命名空间是字典

类体在命名空间映射中执行。```python id="d3f5st"
class User:
    species = "human"

    def greet(self):
        return "hello"
```类命名空间收集：```text id="y3ded7"
species
greet
__module__
__qualname__
```然后元类从该命名空间创建类对象。

生成的类具有类似字典的属性映射。```python id="mtwgd9"
print(User.__dict__)
```类字典通过只读方式公开`mappingproxy`看法。

## 16.19`mappingproxy`一个`mappingproxy`是映射的只读视图。```python id="t40d69"
class C:
    x = 1

print(C.__dict__)
```您不能直接通过mappingproxy进行分配：```python id="a5po6e"
C.__dict__["y"] = 2      # TypeError
```但您可以通过普通的类属性语法进行分配：```python id="j36rbw"
C.y = 2
```代理可以防止内部类字典的直接突变，同时仍然允许内省。

## 16.20 关键字参数

关键字参数使用类似映射的机制来表示。```python id="7yetex"
def f(**kwargs):
    print(kwargs)

f(a=1, b=2)
```在函数内部，`kwargs`是一本字典。

关键字参数传递对性能敏感，因为调用很常见。

CPython 有专门的调用约定来尽可能避免不必要的字典创建，但是当`**kwargs`需要的话，字典就具体化了。

## 16.21 集合也使用哈希表

集合类似于没有值的字典。```python id="j5dt5t"
s = {"a", "b", "c"}
```从概念上讲：```text id="1c2tu2"
set table entry
    hash
    key pointer
```会员资格：```python id="gc0h7j"
"x" in s
```使用散列和探测，如字典查找。

设置调整大小和处理碰撞在概念上类似。

## 16.22 集合运算

集合操作在内部使用哈希表成员资格。```python id="d85y3h"
a = {1, 2, 3}
b = {3, 4, 5}

print(a & b)    # {3}
print(a | b)    # {1, 2, 3, 4, 5}
print(a - b)    # {1, 2}
```性能取决于输入大小。

对于交集，通常最好迭代较小的集合并测试较大集合中的成员资格。

从概念上讲：```text id="s5h98o"
intersection(a, b)
    for each item in smaller set:
        if item in larger set:
            add to result
```CPython 的实现使用了这些类型的大小感知策略。

## 16.23 设置迭代顺序

集合不承诺插入顺序。```python id="fmu4b8"
s = {"a", "b", "c"}
print(list(s))
```该顺序可能取决于哈希值、表大小、插入历史记录和运行时哈希随机化。

不要编写依赖于设置的迭代顺序的代码。

如果顺序很重要，请使用字典作为有序成员资格映射或显式排序。```python id="jc3ogv"
ordered_unique = list(dict.fromkeys(items))
```## 16.24`dict.fromkeys`常见的重复数据删除模式：```python id="0og08r"
items = ["b", "a", "b", "c", "a"]

unique = list(dict.fromkeys(items))

print(unique)   # ['b', 'a', 'c']
```这使用字典插入顺序来保留第一次出现。

一组会删除重复但会丢失顺序：```python id="nozz18"
set(items)
```使用语义符合要求的容器。

## 16.25 默认值和缺失键

多个字典 API 可以处理丢失的键。```python id="860ztd"
d.get("key", default)

get返回默认值而不插入。```python id="kkfpw8" d.setdefault("key", [])

`setdefault`如果密钥丢失，则插入默认值。

常见模式：```python id="t4jd1i"
groups = {}

for item in items:
    groups.setdefault(item.category, []).append(item)
```对于重复分组，`collections.defaultdict`通常更清楚：```python id="27x3y1"
from collections import defaultdict

groups = defaultdict(list)

for item in items:
    groups[item.category].append(item)
```## 16.26 字典推导式

字典理解从可迭代对象构建字典。```python id="uxw8zk"
squares = {x: x * x for x in range(10)}
```如果出现重复的键，则后面的值将替换前面的值，同时保留第一个键的插入位置。```python id="yct6sa"
d = {x % 2: x for x in range(5)}

print(d)        # {0: 4, 1: 3}
```钥匙`0`和`1`提前插入，然后更新值。

## 16.27 集合推导式

集合理解构建了一个集合。```python id="3sgagh"
mods = {x % 10 for x in range(100)}
```重复崩溃。

集合推导对于提取唯一的计算值非常有用。```python id="n3vtrw"
domains = {url.split("/")[2] for url in urls}
```再次强调，迭代顺序并不是语义保证。

## 16.28 哈希随机化

CPython 对某些可哈希类型（例如字符串和字节）使用哈希随机化。

这意味着进程之间的哈希值可能不同。```python id="og1g48"
print(hash("name"))
```运行程序两次，值可能会有所不同。

不要坚持`hash()`跨流程的价值。不要将它们用作稳定 ID。

对于稳定的哈希，请使用定义的哈希函数：```python id="0clx65"
import hashlib

digest = hashlib.sha256(b"name").hexdigest()

hash()适用于进程内哈希表，而不是持久身份。

16.29 常见性能模式

16.30 常见错误

使用频繁成员资格列表：python id="89pu6v" if user_id in user_ids: ... 如果user_ids很大并且查找经常发生，使用集合。python id="2yd104" user_ids = set(user_ids) 使用可变对象作为概念键：python id="wotz0s" key = [1, 2] d[key] = "value" # TypeError 使用元组：python id="lpvy37" key = (1, 2) d[key] = "value" 根据设定顺序：```python id="hmuq1q" first = next(iter(my_set))

坚持`hash()`:

```python id="pchqlg"
id_value = hash(username)
```请改用稳定的哈希函数。

## 16.31 C API 草图

创建字典：```c id="eclt1e"
PyObject *d = PyDict_New();
if (d == NULL) {
    return NULL;
}
```设置项目：```c id="lk7i25"
PyObject *key = PyUnicode_FromString("name");
PyObject *value = PyUnicode_FromString("Ada");

if (key == NULL || value == NULL) {
    Py_XDECREF(key);
    Py_XDECREF(value);
    Py_DECREF(d);
    return NULL;
}

if (PyDict_SetItem(d, key, value) < 0) {
    Py_DECREF(key);
    Py_DECREF(value);
    Py_DECREF(d);
    return NULL;
}

Py_DECREF(key);
Py_DECREF(value);

PyDict_SetItem不窃取引用。它会增加它存储的内容。调用者必须释放其拥有的引用。

获取项目可以返回借用的引用，具体取决于 API：```c id="m18ydq" PyObject *value = PyDict_GetItemWithError(d, key); if (value == NULL) { if (PyErr_Occurred()) { return NULL; } Py_RETURN_NONE; }

/* borrowed reference */ Py_INCREF(value); return value;

## 16.32 设置 C API 草图

创建一个集合：```c id="l7rkf0"
PyObject *s = PySet_New(NULL);
if (s == NULL) {
    return NULL;
}
```添加一个项目：```c id="gjqb0m"
PyObject *item = PyUnicode_FromString("x");
if (item == NULL) {
    Py_DECREF(s);
    return NULL;
}

if (PySet_Add(s, item) < 0) {
    Py_DECREF(item);
    Py_DECREF(s);
    return NULL;
}

Py_DECREF(item);
```该集合在插入后拥有自己的引用。本地参考仍然发布。

会员资格：```c id="b4gg5h"
int present = PySet_Contains(s, item);
if (present < 0) {
    return NULL;
}
```结果是：```text id="eari3m"
1 if present
0 if absent
-1 on error
```## 16.33 心智模型

使用这个模型：```text id="78tgbw"
dict
    hash table mapping keys to values
    keys must be hashable
    insertion order preserved
    stores references to keys and values
    used throughout CPython runtime

set
    hash table storing keys only
    keys must be hashable
    no insertion-order guarantee
    optimized for membership and set algebra
```对于两个容器：```text id="e36bns"
hash chooses where to look
equality confirms the key
collisions are handled by probing
resizing keeps lookup efficient
mutation changes table structure
iteration depends on table state
```## 16.34 总结

字典和集合是哈希表容器。字典将可散列键映射到值并保留插入顺序。集合存储唯一的可哈希元素并优化成员资格测试和集合操作。

CPython 使用字典作为全局变量、属性、类、模块、关键字参数和缓存的核心运行时结构。它们的实现包括哈希缓存、冲突处理、调整大小、拆分表布局、版本标签和顺序保存。

了解字典和集合可以解释 Python 的速度、对象模型、属性查找、命名空间行为和常见性能模式的大部分内容。