Python字典查找函数工作原理及可变类型作为键的可行性问询

嘿，这个问题问得相当到位，刚好能把Python字典和C++里的map/unordered_map的核心差异给你掰明白～

咱先从底层说起：Python的字典是基于哈希表实现的。当你用一个键去查找值的时候，流程大概是这样的：

1. 调用键的__hash__()方法计算哈希值；
2. 根据哈希值找到哈希表对应的“桶”位置；
3. 在桶里用__eq__()方法对比键，找到匹配的键值对。

这就要求键必须是**可哈希（hashable）**的——简单说就是，这个对象的哈希值在生命周期里不能变，而且能和其他对象做相等比较。

像list、dict这种可变类型，它们的内容随时能改，而哈希值是基于内容计算的。举个极端点的例子：
你把一个list([1,2])当键存了值，之后你把list改成[3,4]，它的哈希值直接变了。下次你再用修改后的list去查找，根本找不到原来的桶位置；甚至更糟的是，原来的桶里还留着旧的哈希值对应的键，这会把字典的结构彻底搞乱。所以Python干脆直接禁止可变类型作为字典的键，从根源避免这种问题。

你说的没错：

• C++的std::map是基于红黑树实现的，它根本不需要哈希，只要求键支持比较操作（比如operator<）。所以不管是vector还是array，只要能比大小，就能当键用——本质是靠排序来定位元素的。
• 而std::unordered_map和Python字典是一路货，都是哈希表，但它允许用户自定义哈希函数。像array这种固定大小的容器，你可以给它写个哈希函数，告诉unordered_map怎么计算它的哈希值，自然就能把它当键用了。

虽然Python默认不让可变类型当键，但我们有变通方案：

• 用不可变等效类型替代：比如把list转成tuple（tuple只要里面的元素都是可哈希的，它自己就是可哈希的）。比如：

my_dict = {}
my_dict[(1, 2, 3)] = "这是用tuple当键的值"
print(my_dict[(1, 2, 3)])  # 正常输出对应值

这就相当于用了C++里array的不可变版本当键，完全符合要求。

• 自定义可哈希的包装类：如果你一定要用自定义的可变类型（比如自己写的数组类），可以给类实现__hash__()和__eq__()方法，但必须保证对象的哈希值不会随内容变化而变——比如把核心数据存在不可变的容器里：

class MyImmutableArray:
    def __init__(self, data):
        # 把传入的可变数据转成不可变的tuple存起来
        self._data = tuple(data)
    
    def __hash__(self):
        # 基于不可变的_data计算哈希值
        return hash(self._data)
    
    def __eq__(self, other):
        # 定义两个对象相等的条件
        return isinstance(other, MyImmutableArray) and self._data == other._data

# 测试一下
my_dict = {}
my_dict[MyImmutableArray([1,2,3])] = "自定义类当键的测试值"
print(my_dict[MyImmutableArray([1,2,3])])  # 正常输出

• 用dataclasses快速创建不可变类：Python 3.7+的dataclasses模块加个frozen=True参数，就能自动生成不可变的类，还会帮你搞定__hash__和__eq__方法：

from dataclasses import dataclass

@dataclass(frozen=True)
class FrozenArray:
    data: tuple

my_dict = {}
my_dict[FrozenArray((1,2,3))] = "用dataclass实现的不可变数组键"
print(my_dict[FrozenArray((1,2,3))])

总结一下：Python字典靠哈希表吃饭，所以要求键可哈希；C的map靠排序，unordered_map靠自定义哈希；Python可以通过转不可变类型或者自定义可哈希包装类，实现类似C用array当unordered_map键的效果。

内容的提问来源于stack exchange，提问作者Srini