从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}哈希表原理魔法背后的科学哈希表是一种基于键值对存储数据的数据结构。它的工作流程如下哈希计算当你插入一个键值对时Python会对键进行哈希运算得到一个整数哈希值。索引映射哈希值经过处理转换成数组中的索引位置。存储值将对应的值存储在这个索引位置。查找当需要根据键查找值时重复步骤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方法直接修改了原列表没有创建新对象实用技巧字典的安全查找直接访问不存在的键会引发KeyErrord {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字典保持插入顺序但不如列表灵活内存非常受限简单的数据集合用列表或元组更合适