从O(n)到O(1)，字典是如何实现飞速查找的？

你是否曾经好奇过，为什么Python中的字典（dict）查找速度如此之快？为什么我们不能用列表作为字典的键？今天，让我们一起揭开字典背后的秘密——哈希表。

从查字典说起

想象一下，你要在一本没有索引的字典里查找一个生僻字。怎么办？你只能从第一页开始，一页一页地翻，直到找到目标。这就是O(n)的时间复杂度——随着字典页数增加，查找时间线性增长。

但如果你手头是一本带有偏旁部首索引的字典呢？先通过偏旁找到对应的页码，然后直接翻到那一页。这就是O(1)的时间复杂度——无论字典多厚，查找时间基本恒定。

Python的字典就像那本带索引的书，只不过它的索引系统更强大——哈希表。

初识字典：基础操作

# 创建字典
d = {'Michael': 95, 'Bob': 75, 'Tracy': 85}

# 查找
print(d['Michael'])  # 输出: 95

# 添加/修改
d['Adam'] = 67      # 添加新键值对
d['Jack'] = 90      # 再添加一个
d['Jack'] = 88      # 修改已存在的键

print(d['Jack'])    # 输出: 88

# 删除
d.pop('Bob')        # 删除键为'Bob'的条目

# 查看当前字典
print(d)  # {'Michael': 95, 'Tracy': 85, 'Adam': 67, 'Jack': 88}

哈希表原理：魔法背后的科学

哈希表是一种基于键值对存储数据的数据结构。它的工作流程如下：

1. 哈希计算：当你插入一个键值对时，Python会对键进行哈希运算，得到一个整数（哈希值）。

2. 索引映射：哈希值经过处理，转换成数组中的索引位置。

3. 存储值：将对应的值存储在这个索引位置。

4. 查找：当需要根据键查找值时，重复步骤1-2，直接定位到存储位置。

这个过程就像你有一个巨大的储物柜，每个格子都有编号。你根据物品名称（键）计算出格子编号（索引），然后直接打开那个格子取出物品（值）。

字典 vs 列表：两种不同的设计哲学

特性	字典 (dict)	列表 (list)
查找速度	O(1) 极快	O(n) 随元素增加而变慢
内存占用	大（空间换时间）	小
适用场景	快速查找、数据关联	有序存储、遍历操作

# 列表查找示例
my_list = [95, 75, 85]  # 对应 Michael, Bob, Tracy
# 要找到Bob的分数，需要遍历整个列表
for i, score in enumerate(my_list):
    if i == 1:  # 假设我们知道Bob在索引1
        print(score)  # 这其实还是需要索引知识

# 字典查找示例
my_dict = {'Michael': 95, 'Bob': 75, 'Tracy': 85}
print(my_dict['Bob'])  # 直接命中，O(1)操作

为什么键必须是不可变对象？

你有没有试过用列表作为字典的键？会得到这样的错误：

key = [1, 2, 3]
d = {}
d[key] = 'a list'  # TypeError: unhashable type: 'list'

为什么？

字典依赖键的哈希值来确定存储位置。如果键是可变的（比如列表），那么：

• 修改列表内容后，它的哈希值可能会改变

• 哈希值改变后，就无法找到原来的存储位置

• 字典的整个结构就会混乱

因此，字典的键必须是可哈希的（hashable），也就是不可变类型：

• ✅ 字符串 (str)

• ✅ 整数 (int)

• ✅ 浮点数 (float)

• ✅ 元组 (tuple) - 前提是元组内的元素也都是不可变的

• ❌ 列表 (list)

• ❌ 字典 (dict)

# 合法的键
valid_dict = {
    'name': 'Alice',      # 字符串作为键
    42: 'answer',         # 整数作为键
    (1, 2): 'point'       # 元组作为键
}

# 不合法的键
# invalid_dict = {
#     [1, 2]: 'list key'   # 会报错
# }

Set集合：没有值的字典

Set和字典非常相似，可以理解为只有键没有值的字典。

# 创建set的两种方式
s1 = {1, 2, 3}                    # 直接使用花括号
s2 = set([1, 2, 3, 2, 5])         # 从列表创建，自动去重

print(s2)  # {1, 2, 3, 5} - 注意重复的2只保留一个

# 添加元素
s1.add(4)
print(s1)  # {1, 2, 3, 4}

# 删除元素
s1.remove(4)

# 集合运算
set1 = {1, 2, 3}
set2 = {2, 3, 4}

print(set1 & set2)  # 交集: {2, 3}
print(set1 | set2)  # 并集: {1, 2, 3, 4}

再谈不可变对象：你真的理解了吗？

很多初学者对"不可变对象"存在误解。看这个例子：

a = 'abc'
print(id(a))  # 假设输出: 140234567890

a = 'def'
print(id(a))  # 输出不同: 140234567999
# a现在指向了新的字符串对象，原来的'abc'没有被修改

关键点：变量可以被重新赋值，但字符串对象本身是不可变的。

s = 'abc'
print(s.replace('a', 'A'))  # 输出: 'Abc'
print(s)                     # 输出: 'abc' - 原字符串没变！

# replace方法返回了一个新的字符串对象，而不是修改原来的

对比可变对象：

lst = ['c', 'b', 'a']
print(id(lst))        # 假设: 140234568000
lst.sort()
print(id(lst))        # 相同地址: 140234568000
# sort方法直接修改了原列表，没有创建新对象

实用技巧：字典的安全查找

直接访问不存在的键会引发KeyError：

d = {'Michael': 95}
# print(d['Bob'])  # KeyError: 'Bob'

# 安全方式1: 使用in操作符
if 'Bob' in d:
    print(d['Bob'])

# 安全方式2: 使用get方法
print(d.get('Bob'))        # 返回None
print(d.get('Bob', -1))    # 返回-1（自定义默认值）
print(d.get('Michael', -1)) # 返回95，因为键存在

总结：何时使用字典？

适合使用字典的场景：

• 需要快速查找（如用户信息缓存）

• 数据之间有明确的对应关系（如学生→成绩）

• 需要动态增删键值对

不适合使用字典的场景：

• 需要保持顺序（Python 3.7+字典保持插入顺序，但不如列表灵活）

• 内存非常受限

• 简单的数据集合，用列表或元组更合适