Python 基础体系 · 第 9/112 篇。示例统一以 Python 3.14 为语言基线；第三方库使用与其兼容的现代稳定版本，版本敏感行为会单独说明。

Python dict 与 set：哈希、顺序、冲突、复杂度和键约束

dict 与 set 都建立在“哈希表”这一类数据结构之上，但它们解决的问题不同：

dict 保存 键到值的映射；
set 保存 不重复的元素集合；
两者都依赖元素的哈希值完成快速定位；
两者都要求参与查找的对象满足哈希约束；
dict 的迭代顺序有语言级保证，而 set 不提供元素顺序保证。

理解它们不能只记住“查找平均是 O(1)”。真正需要掌握的是：哈希值如何参与定位、冲突如何处理、相等性如何决定“是不是同一个键”、扩容为什么使插入具有摊销复杂度，以及对象为什么可能不可哈希。

1. 先区分三个概念：哈希、相等性与身份

1.1 身份：`is`

身份表示两个变量是否指向同一个对象：

a = []
b = a
c = []

print(a is b)  # True
print(a is c)  # False

is 比较的是对象身份，不调用用户定义的 __eq__()，也不能被普通类自定义。(docs.python.org)

1.2 相等性：`==`

相等性表示两个对象的值是否相等：

a = [1, 2]
b = [1, 2]

print(a == b)  # True
print(a is b)  # False

对于自定义类型，== 通常由 __eq__() 决定。两个对象可以不是同一个对象，但只要它们的值相等，就可能满足：

a == b

1.3 哈希值：`hash(x)`

哈希值是一个整数，由对象的 __hash__() 提供：

print(hash("python"))
print(hash((1, 2)))

哈希函数的目标不是为每个对象生成唯一整数，而是把对象映射到一个整数空间。由于对象数量可能远大于哈希值空间，哈希冲突必然可能发生。

哈希集合要求一个基本一致性条件：

x == y \Rightarrow hash(x) == hash(y)

也就是说，如果两个对象相等，它们必须具有相同的哈希值。反过来则不成立：

hash(x) == hash(y) \nRightarrow x == y

两个不同对象可以拥有相同哈希值，这就是冲突。Python 数据模型明确要求相等对象具有相同哈希值，但并不要求哈希值不同的对象才相等，也不强制所有自定义类自动满足这些一致性规则。(docs.python.org)

直观地说：

hash() 用于快速缩小搜索范围；
== 用于最终确认是否真的是同一个逻辑键；
is 只表示是否是同一个对象。

2. 哈希表究竟解决什么问题

假设要在一个列表中查找元素：

items = ["a", "b", "c", "d"]

如果不知道元素位于哪个位置，最直接的方法是从头到尾比较：

for item in items:
    if item == target:
        ...

最坏情况下需要比较 n 次，因此查找复杂度为：

O(n)

哈希表的思路是先通过哈希值计算一个候选位置。设底层表有 m 个槽位，理想化情况下可以使用：

index = hash(key) \bmod m

例如：

hash("python") = 37
m = 8

index = 37 % 8 = 5

于是，查找 "python" 时不必从第 0 个元素开始逐一比较，而是先到第 5 号槽位附近寻找。

实际哈希表不会简单地保证“一个哈希值对应一个唯一槽位”，因为：

不同对象可能哈希值相同；
不同哈希值经过取模后也可能落入同一个槽位；
表容量有限，而键的数量可能不断增长。

因此，哈希表的真实查找过程通常是：

计算键的哈希值；
根据哈希值找到初始槽位；
检查槽位是否为空；
如果槽位中的键哈希值不同，继续寻找；
如果哈希值相同，再通过 == 比较键；
找到相等键则命中，否则继续处理冲突。

这解释了为什么 dict 和 set 的查找不能只理解成“直接数组下标访问”：它们还必须处理冲突和相等性。

3. `dict`：从键到值的映射

3.1 基本结构

dict 的逻辑数据模型可以表示为：

\{key_1 \rightarrow value_1,\ key_2 \rightarrow value_2,\ \ldots\}

例如：

user = {
    "id": 1001,
    "name": "Alice",
    "active": True,
}

这里有三个键值对：

"id"     -> 1001
"name"   -> "Alice"
"active" -> True

键用于定位，值只是在命中键后返回的关联对象。值本身不需要可哈希，可以是列表、字典或其他可变对象：

data = {
    "items": [1, 2, 3],
    "metadata": {"source": "api"},
}

Python 文档将字典描述为把可哈希值映射到任意对象的可变映射。字典键不能是不可哈希对象；相等的键会指向同一个字典条目。(docs.python.org)

3.2 插入、查找与更新

scores = {}

scores["Alice"] = 90
scores["Bob"] = 85

print(scores["Alice"])  # 90

scores["Alice"] = 95
print(scores)           # {'Alice': 95, 'Bob': 85}

执行：

scores["Alice"] = 95

不是新增一个 "Alice"，而是：

计算 "Alice" 的哈希值；
定位候选槽位；
找到与 "Alice" 相等的已有键；
替换该键关联的值。

因此，字典中的键是唯一的，但值可以重复：

d = {"a": 1, "b": 1}
print(len(d))  # 2

构造字典时，如果输入中同一个键出现多次，最后一个值会覆盖前面的值。(docs.python.org)

3.3 `get()` 与 `[]` 的错误语义不同

users = {"alice": 1001}

print(users["alice"])  # 1001
print(users.get("alice"))  # 1001

对于不存在的键：

users["bob"]

会抛出：

KeyError: 'bob'

而：

users.get("bob")

返回 None：

print(users.get("bob"))  # None

也可以提供默认值：

print(users.get("bob", 0))  # 0

这两个接口表达了不同意图：

d[key]：这个键必须存在，不存在属于错误；
d.get(key)：这个键可能不存在，不存在是正常分支。

如果 None 本身也是合法值，应使用显式哨兵区分“键不存在”和“值为 None”：

missing = object()

value = users.get("bob", missing)

if value is missing:
    print("键不存在")

4. `set`：只有键，没有值

4.1 集合的逻辑结构

set 可以看作只有键而没有值的哈希表：

tags = {"python", "backend", "database"}

其核心问题不是：

key 对应什么 value？

而是：

key 是否存在？

因此，集合适合：

成员资格测试；
去重；
交集、并集、差集；
表示不允许重复的元素集合。

Python 文档将 set 定义为由不同的可哈希对象组成的无序集合。可变的 set 不能作为字典键或另一个集合的元素；不可变的 frozenset 可以。(docs.python.org)

4.2 集合去重

values = [1, 2, 2, 3, 1, 4]

unique_values = set(values)

print(unique_values)
print(len(unique_values))  # 4

集合中的重复元素只保留一份：

s = set()

s.add("python")
s.add("python")

print(s)       # {'python'}
print(len(s))  # 1

添加元素时，集合会根据哈希值和相等性判断元素是否已经存在。如果已有元素与新元素相等，集合不会增加新的元素。

4.3 集合运算

backend = {"python", "go", "java"}
data = {"python", "sql", "redis"}

print(backend & data)  # {'python'}
print(backend | data)  # {'python', 'go', 'java', 'sql', 'redis'}
print(backend - data)  # {'go', 'java'}
print(backend ^ data)  # {'go', 'java', 'sql', 'redis'}

这些运算分别表示：

&：交集；
|：并集；
-：差集；
^：对称差集，即只出现在一方的元素。

集合关系运算则表示子集或超集，而不是通常意义上的大小排序：

a = {1, 2}
b = {1, 2, 3}

print(a < b)  # True，a 是 b 的真子集
print(a <= b) # True

但：

{1, 2} < {2, 3}

为 False，因为两者互不为对方的子集。集合关系不是全序关系，因此不能把集合当作普通可排序对象使用。(docs.python.org)

5. 冲突：不同键为什么可以落到同一个位置

5.1 冲突的形式

设哈希表容量为 8：

key_a 的哈希值 = 5
key_b 的哈希值 = 13

虽然哈希值不同，但：

5  % 8 = 5
13 % 8 = 5

它们都会得到初始槽位 5，这就是由取模造成的槽位冲突。

更极端的情况是，两个对象直接返回相同哈希值：

class SameHash:
    def __init__(self, name):
        self.name = name

    def __hash__(self):
        return 42

    def __eq__(self, other):
        return isinstance(other, SameHash) and self.name == other.name

a = SameHash("a")
b = SameHash("b")

print(hash(a) == hash(b))  # True
print(a == b)              # False

将它们放入字典：

d = {a: "value-a", b: "value-b"}

print(len(d))      # 2
print(d[a])        # value-a
print(d[b])        # value-b

哈希相同并不会使两个键自动相等。哈希值只是第一步筛选条件，最终仍需通过相等性判断。

5.2 冲突处理的抽象过程

可以用下面的伪过程理解一次查找：

h = hash(key)
i = initial_slot(h)

重复：
    entry = table[i]

    如果 entry 为空：
        查找失败

    如果 entry.hash == h 且 entry.key == key：
        查找成功

    否则：
        i = next_probe(i, h)

其中：

h 是键的哈希值；
i 是当前探测位置；
entry.hash == h 用于快速排除明显不同的键；
entry.key == key 用于确认逻辑相等；
next_probe() 决定冲突后检查哪个槽位。

在 CPython 3.14 的实现中，字典和集合都使用哈希表，并通过探测序列处理冲突；字典实现还会在表接近满时扩容，以保证查找不会在过度拥挤的表上持续退化。具体探测公式和内存布局属于 CPython 实现细节，不是 Python 语言层面的可移植规范。(github.com)

5.3 为什么不能通过哈希值直接判断相等

下面的判断是错误的：

if hash(a) == hash(b):
    print("a 和 b 相等")

正确逻辑只能是：

if hash(a) == hash(b) and a == b:
    print("a 和 b 作为哈希键相等")

即使如此，实际容器还需要遵守对象比较协议，包括可能返回 NotImplemented 的自定义比较方法。工程代码通常不应手动复刻容器内部的完整比较过程。

6. 复杂度：为什么通常是 `O(1)`，但不是无条件保证

设容器中有 n 个元素。

6.1 平均复杂度

在以下假设下：

哈希函数分布较均匀；
表不会长期接近满载；
__hash__() 本身耗时可视为常数；
__eq__() 比较耗时可视为常数；

字典和集合的典型操作平均复杂度如下：

操作	平均复杂度
`key in d`	`O(1)`
`d[key]`	`O(1)`
`d[key] = value`	`O(1)`
`del d[key]`	`O(1)`
`x in s`	`O(1)`
`s.add(x)`	`O(1)`
`s.remove(x)`	`O(1)`

这里的 O(1) 表示平均情况下，探测的槽位数量不随 n 线性增长。

但这个复杂度不包含复杂的键本身。例如：

key = "a" * 10_000_000
hash(key)

字符串哈希需要处理字符串内容。对这种键，计算哈希值本身就可能与键长度有关。容器查找的复杂度分析通常把“计算键哈希值”和“键相等比较”的成本单独抽象掉。

6.2 最坏复杂度

如果大量键产生严重冲突，查找可能需要检查大量候选项，最坏情况下退化为：

O(n)

例如：

class BadKey:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        return 0

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

所有键都返回 0：

d = {BadKey(i): i for i in range(10_000)}

此时容器仍然能够保持语义正确，但冲突链会变长，查找和插入的常数成本显著增加，极端时可能接近线性复杂度。

因此，“dict 查找是 O(1)”应理解为：

在合理哈希分布和正常负载条件下，平均查找复杂度为 O(1)；它不是对任意自定义 __hash__() 和 __eq__() 实现的绝对最坏情况保证。

6.3 扩容与摊销复杂度

哈希表不能无限制地在固定容量上插入元素。随着元素增加，空槽变少，冲突概率上升，因此容器需要扩容。

一次扩容通常包含：

分配更大的底层表；
重新计算或重新安排已有条目；
将旧条目迁移到新表；
释放或替换旧表。

单次扩容可能需要：

O(n)

但扩容不是每次插入都发生。假设表容量大致按倍数增长：

容量：8 -> 16 -> 32 -> 64 -> ...

前面所有扩容迁移的总成本近似为：

8 + 16 + 32 + \cdots + 2^k < 2^{k+1}

如果最终插入了约 $n$ 个元素，那么所有扩容成本加起来是 O(n)。把这部分成本平均分摊到 n 次插入上，每次插入的摊销成本仍为：

O(1)

所以插入操作通常说是“平均 O(1)”或“摊销 O(1)”，而不是说每一次插入都严格只执行固定数量的机器操作。

7. `dict` 的顺序：有保证，但不是“按哈希槽位顺序”

7.1 Python 3.14 中的字典顺序

Python 3.14 语言文档保证：字典保持插入顺序。更新已有键不会改变其位置；删除后重新添加该键，则会把它放到末尾。(docs.python.org)

d = {
    "one": 1,
    "two": 2,
    "three": 3,
}

d["two"] = 22
print(list(d))  # ['one', 'two', 'three']

del d["two"]
d["two"] = 222

print(list(d))  # ['one', 'three', 'two']

这里需要区分两种行为：

d["two"] = 22

是更新已有条目，不改变顺序；

del d["two"]
d["two"] = 222

先删除再重新插入，因此 "two" 移动到末尾。

7.2 字典顺序与哈希表位置不是一回事

字典的逻辑迭代顺序是插入顺序，但底层哈希表仍然需要根据哈希值定位。

因此，下面两个概念不能混淆：

逻辑顺序：第一次插入键的先后顺序
物理位置：哈希表中用于查找该键的内部位置

扩容时，内部表可能重新布局，但这不应改变字典对外暴露的插入顺序。

这也是为什么不能根据字典的打印顺序推断哈希值，也不能根据哈希值推断字典遍历顺序。

7.3 字典视图是动态的

d.keys()、d.values() 和 d.items() 返回的是视图，而不是创建时的静态列表：

d = {"a": 1}
keys = d.keys()

print(list(keys))  # ['a']

d["b"] = 2

print(list(keys))  # ['a', 'b']

视图会反映底层字典后续的变化。字典键视图和满足条件的条目视图还支持集合式操作。(docs.python.org)

但是，在遍历视图时修改字典结构可能导致 RuntimeError，或者造成遍历结果不完整：

d = {"a": 1, "b": 2}

for key in d:
    del d[key]  # 可能触发 RuntimeError

如果需要修改结构，应先复制键：

for key in list(d):
    del d[key]

8. `set` 的顺序：不要依赖

集合是无序集合。它不记录元素的插入位置，也不支持索引和切片。(docs.python.org)

s = {"a", "b", "c"}

# s[0]  # TypeError: 'set' object is not subscriptable

下面的输出顺序不能作为契约：

print({"a", "b", "c"})

即使某个 CPython 版本、某次运行、某种哈希种子下恰好出现了稳定顺序，也不能据此认为集合有插入顺序。

如果需要稳定输出，应显式排序：

s = {"python", "go", "java"}

print(sorted(s))
# ['go', 'java', 'python']

但这会引入排序成本：

O(n \log n)

如果只需要去重并保留首次出现顺序，可以使用字典键：

values = ["b", "a", "b", "c", "a"]

unique = list(dict.fromkeys(values))

print(unique)  # ['b', 'a', 'c']

这个写法利用了字典键的唯一性和插入顺序保证，而不是依赖 set 的遍历顺序。

9. 哪些对象可以作为键或集合元素

9.1 可哈希对象

一个对象适合作为字典键或集合元素，需要满足：

可以调用 hash(obj)；
哈希值在对象参与容器期间保持稳定；
如果对象与另一个对象相等，它们的哈希值必须相同；
相等性判断应尽量稳定、对称且具有传递性。

常见可哈希对象包括：

42
3.14
"python"
b"bytes"
(1, 2, 3)
frozenset({1, 2})

常见不可哈希对象包括：

[]
{}
set()

示例：

d = {
    (1, 2): "tuple key",
    frozenset({1, 2}): "set-like key",
}

print(d[(1, 2)])

元组是否可哈希，取决于其中的元素是否都可哈希：

hash((1, 2))       # 成功
hash((1, []))      # TypeError

Python 文档明确指出，不可变序列如果包含不可哈希值，整体仍然不可哈希。(docs.python.org)

9.2 “不可变”与“可哈希”不是完全同义

通常，不可变对象更可能可哈希，但这不是简单的语法规则。

例如：

t = (1, [2, 3])

元组自身不能通过修改元组结构改变，但它包含列表，而列表不可哈希，因此：

hash(t)

仍会抛出 TypeError。

另一方面，用户自定义类默认继承 object 的哈希和相等性行为，默认情况下通常按对象身份进行比较，因此其实例通常可哈希：

class User:
    pass

u = User()

print(hash(u))
print(u == u)  # True

10. 自定义键：`eq()` 与 `hash()` 必须成对设计

10.1 正确的值对象实现

假设使用用户编号判断两个用户是否相等：

class UserId:
    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        if not isinstance(other, UserId):
            return NotImplemented
        return self.value == other.value

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

现在：

a = UserId(1001)
b = UserId(1001)

print(a == b)             # True
print(hash(a) == hash(b)) # True

d = {a: "Alice"}
print(d[b])               # Alice

查找 d[b] 时，字典虽然没有保存对象 b，但它发现：

hash(a) == hash(b)
a == b

因此认为 b 对应已有条目。

10.2 只重写 `eq()` 的结果

如果一个类重写了 __eq__() 却没有定义 __hash__()，Python 通常会把该类的 __hash__ 隐式设为 None，实例会被视为不可哈希：

class UserId:
    def __init__(self, value):
        self.value = value

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

user_id = UserId(1001)

print(UserId.__hash__)  # None

# hash(user_id)         # TypeError: unhashable type

这是合理的默认行为，因为类已经声明“对象相等性由值决定”，但没有声明如何为这个值计算稳定哈希。Python 数据模型对这种隐式禁用哈希的行为有明确说明。(docs.python.org)

10.3 可变键是危险的

下面的类存在严重问题：

class MutableKey:
    def __init__(self, value):
        self.value = value

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

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

使用它作为字典键：

key = MutableKey("before")
d = {key: "value"}

key.value = "after"

此时 key 的哈希值可能已经改变，但它仍然位于按照旧哈希值定位的内部位置。于是可能出现：

key in d

返回 False，或者：

d[key]

抛出 KeyError。

这不是字典忘记保存键，而是查找时使用了新的哈希值，无法再沿着正确的探测路径找到旧位置。

因此，参与 __eq__() 和 __hash__() 的状态必须在对象作为键或集合元素期间保持不变。官方数据模型也明确指出，如果对象的哈希值会变化，它会落在错误的哈希桶中。(docs.python.org)

更安全的做法是使用不可变类型：

from dataclasses import dataclass

@dataclass(frozen=True)
class UserId:
    value: int

user_id = UserId(1001)
d = {user_id: "Alice"}

print(d[UserId(1001)])  # Alice

这里的安全性来自对象状态不能被普通属性赋值修改，而不是来自 dataclass 这个装饰器本身具有某种特殊哈希魔法。

11. 数字键的一个重要边界：`1`、`1.0` 和 `True`

Python 中：

1 == 1.0 == True

结果为 True，并且它们的哈希值也一致：

print(1 == 1.0 == True)                 # True
print(hash(1), hash(1.0), hash(True))   # 通常相同

因此，它们在字典中会指向同一个逻辑条目：

d = {}

d[1] = "integer"
d[1.0] = "float"
d[True] = "boolean"

print(d)
print(len(d))  # 1

最后一次赋值覆盖了前面的值。

更细致地看：

d = {1: "integer"}

d[1.0] = "float"

print(d)       # {1: 'float'}
print(list(d)) # [1]

值被更新，但原有键对象仍表现为整数键，且位置不变。

这是因为字典键判定依赖“哈希一致性 + 相等性”，而不是依赖类型名称是否相同。Python 文档明确将 1、1.0 和 True 作为可互换索引同一字典条目的例子。(docs.python.org)

如果业务上必须区分它们，应显式把类型纳入键：

def typed_key(value):
    return type(value), value

d = {
    typed_key(1): "integer",
    typed_key(1.0): "float",
    typed_key(True): "boolean",
}

print(d)

此时键分别是：

(int, 1)
(float, 1.0)
(bool, True)

12. 特殊值：`NaN` 不适合作为普通业务键

浮点数 NaN 具有特殊比较语义：

x = float("nan")

print(x == x)  # False
print(hash(x))

这与普通对象的直觉不同。将 NaN 用作字典键时，必须注意：

x = float("nan")
d = {x: "value"}

print(d[x])  # 通常可以通过同一个对象找到
print(float("nan") in d)  # 不应按普通值相等来理解

这里涉及对象身份、哈希值以及浮点 NaN 的非自反相等性。业务代码不应把 NaN 当作普通的稳定值键；如果需要表达“缺失”，应使用明确的哨兵对象、None 或业务状态字段，而不是依赖 NaN。

13. 删除、`pop()`、`discard()` 与失败路径

字典和集合的删除接口在失败时语义不同。

字典

d = {"a": 1}

del d["a"]
# del d["a"]  # KeyError

pop() 可以在删除后返回值，也可以提供默认值：

d = {"a": 1}

value = d.pop("a")
print(value)  # 1

missing = d.pop("b", None)
print(missing)  # None

集合

s = {"a", "b"}

s.remove("a")
# s.remove("a")  # KeyError

discard() 在元素不存在时不抛出异常：

s.discard("a")
s.discard("a")  # 不报错

pop() 对集合不能表达“弹出第一个元素”，因为集合没有对外保证的顺序：

s = {"a", "b", "c"}
item = s.pop()

这里的 item 是某个元素，但不能把它解释为最早插入、最小、最大或固定位置的元素。

14. 并发与修改：单次操作安全不等于复合逻辑安全

在多线程程序中，不应把“某个内置操作不会破坏解释器内部结构”误解为“多步业务逻辑自动具有原子性”。

例如：

if key not in cache:
    cache[key] = build_value()

这包含两个步骤：

检查键是否存在；
不存在时写入值。

多个线程可能同时通过第一步，于是重复执行 build_value()。

如果业务要求“检查并初始化”具有一致性，应使用锁、专门的并发结构或重新设计流程，而不能只依赖 dict 的平均复杂度。

遍历过程中修改字典结构也有明确风险：

for key in d:
    d[key] = d[key] + 1

只更新已有值通常不会改变键集合结构；但新增或删除键可能导致运行时错误或遍历不完整。字典文档明确警告，在迭代视图时添加或删除条目可能抛出 RuntimeError，也可能无法遍历全部条目。(docs.python.org)

15. 字符串哈希的随机化与跨进程稳定性

Python 默认会对 str 和 bytes 的哈希值加入不可预测的随机盐值。因此，同一个字符串在不同进程中可能得到不同的哈希值：

print(hash("python"))

不要把 hash() 的结果当作：

跨进程稳定的 ID；
数据库存储键；
网络协议中的持久标识；
可复现的文件名；
跨机器缓存键。

如果需要稳定摘要，应使用明确的序列化和密码学或非密码学哈希算法，例如 hashlib 中的算法，并规定编码方式：

import hashlib

key = "python".encode("utf-8")
digest = hashlib.sha256(key).hexdigest()

print(digest)

hash() 的设计目标是服务于当前 Python 运行时中的哈希集合，而不是提供跨运行稳定的摘要值。数据模型文档特别指出，字符串和字节串哈希默认使用随机盐。(docs.python.org)

16. `dict`、`set`、`list` 的选择依据

可以从三个问题开始选择：

需要“按键取值”吗？

使用 dict：

user_by_id = {
    1001: {"name": "Alice"},
    1002: {"name": "Bob"},
}

只需要判断是否存在或去重吗？

使用 set：

allowed_ids = {1001, 1002, 1003}

if user_id in allowed_ids:
    ...

需要位置、重复项或切片吗？

使用 list：

events = ["start", "retry", "success"]
print(events[0])
print(events[1:])

不要因为 set 去重方便，就在需要顺序的场景中无条件使用它；也不要因为 dict 查找快，就把所有数据都包装成字典。容器选择取决于数据关系：

list：有序序列，允许重复，按位置访问
dict：键到值的映射，键唯一，保持插入顺序
set：唯一元素集合，不提供顺序保证

17. 一段可运行的综合示例

下面的程序同时演示顺序、更新、删除、去重、集合运算和可哈希约束：

def main():
    records = [
        ("alice", "python"),
        ("bob", "go"),
        ("alice", "python"),
        ("carol", "python"),
    ]

    # 1. 使用字典建立“用户名 -> 技术栈”映射
    user_to_skill = {}

    for username, skill in records:
        user_to_skill[username] = skill

    print(user_to_skill)
    # {'alice': 'python', 'bob': 'go', 'carol': 'python'}

    # 2. 字典键去重并保持首次插入顺序
    print(list(user_to_skill))
    # ['alice', 'bob', 'carol']

    # 3. 使用集合获取不同技术栈
    skills = set(user_to_skill.values())
    print(skills)
    # {'python', 'go'}，顺序不应依赖

    # 4. 集合成员测试
    print("python" in skills)  # True
    print("java" in skills)    # False

    # 5. 删除后重新插入，键移动到末尾
    del user_to_skill["bob"]
    user_to_skill["bob"] = "rust"

    print(list(user_to_skill))
    # ['alice', 'carol', 'bob']

    # 6. 不可哈希对象不能作为键
    try:
        invalid = {[1, 2]: "value"}
    except TypeError as exc:
        print(type(exc).__name__)
        # TypeError


if __name__ == "__main__":
    main()

每一步的关键原因是：

user_to_skill[username] = skill 使用用户名作为哈希键；
重复的 "alice" 不会增加新的字典条目；
set(...) 只保留不同的技术栈；
集合成员测试依赖哈希定位；
删除后再插入属于新插入，因此位置进入末尾；
列表不可哈希，不能作为字典键。

结语：把 `O(1)` 还原成完整机制

dict 和 set 的高效来自哈希表，但哈希表不是“魔法数组”。一次典型查找至少包含：

计算哈希值
    -> 定位初始槽位
    -> 检查冲突候选
    -> 调用相等性判断
    -> 命中或继续探测

由此可以得到几个必须同时记住的结论：

哈希相同不代表对象相等；
相等对象必须具有相同哈希；
自定义 __eq__() 时必须认真设计 __hash__()；
作为键或集合元素的对象，其哈希相关状态必须保持稳定；
dict 的插入顺序是 Python 3.14 的语言级保证；
set 不提供元素顺序保证；
dict 和 set 的查找通常平均为 O(1)，严重冲突时可能退化；
扩容导致单次操作可能很昂贵，但整体插入通常具有摊销 O(1) 复杂度；
hash() 适合当前运行时的容器定位，不适合作为跨进程稳定标识。

系列导航与关联阅读

系列入口：Python 完整学习路线：从语言模型、并发到 Web、数据、AI 与生产交付
上一篇：Python list、tuple 与 range：存储、切片、复杂度和选择
下一篇：Python 控制流：if、for、while、break、else 与作用域
延伸：Python collections：deque、Counter、defaultdict、ChainMap 与队列

官方资料

本文依据 Python 官方文档、相关 PEP 与生态项目官方文档重新梳理；正文、示例与工程清单由 WR BLOG 编写。