CC++ & Algorithm

Python哈希表的应用

困难3
语言版本：C++Python
概述：通过三个实际例子展示哈希表（字典）在去重、计数和快速查找中的强大用处。

字典的妙用——去重、计数与快速查找

学会了字典的底层是哈希表，那它到底能帮我们解决什么问题呢？哈希表（Python字典）在编程里有很多聪明的用法，能帮我们轻松搞定重复数据、统计次数和快速判断。就像你有一个超级记事本：每页一个标题（key），下面记录内容（value），而且不管有多少页，都能瞬间翻到你要的那一页。下面我们用三个生活例子来学会字典的三种经典用法。

一、去重：去掉重复数据

为什么字典能做去重？

字典的 key 是唯一的，如果你向字典里放两个相同的 key，后面的会覆盖前面的。利用这个特性，我们可以快速过滤掉重复项，而且还能保留第一次出现时的顺序。

举个例子：班级点名册去重

假设你有一串学生名单，里面有些名字重复了，你想要一个不重复的名单。用列表的话要写很多循环，但利用字典的 key 不能重复的特性，一行代码就能解决。

# 原始名单，有重复
names = ["小明", "小红", "小刚", "小明", "小丽", "小红"]

# 用字典去重（字典的key自动过滤重复）
unique_names = list(dict.fromkeys(names))  # fromkeys会保留顺序
print("去重后的名单：", unique_names)

# 或者用更简单的集合（set），但集合不保证顺序
# 这里我们展示字典的用途

上面的 dict.fromkeys(names) 会创建一个字典，key 是所有名字（重复的只保留第一个），然后我们取它的 key 列表就得到了去重结果。

更贴近生活的例子：抽奖箱

你有一堆抽奖券编号 ["A001", "A002", "A001", "A003", "A002"]，你希望每个编号只出现一次，而且按第一次出现的顺序排列。用字典做去重：

tickets = ["A001", "A002", "A001", "A003", "A002"]
unique_tickets = list(dict.fromkeys(tickets))
print("不重复的抽奖券：", unique_tickets)  # 输出 ['A001', 'A002', 'A003']

新手常犯的错误

  • 错误：直接用 set(names) 去重，但集合不保留顺序。如果需要保持顺序，必须用 dict.fromkeys()。
  • 错误：误以为 list(set(names)) 也能保留顺序，其实集合的顺序是随机的（基于哈希值）。

二、计数：统计每个元素出现的次数

核心思想：key 记录“谁”，value 记录“几次”

老师想知道每个学生交了作业的次数。用字典存储“学生名字 -> 次数”非常方便。每次看到一个人，就给对应的次数加1。

submissions = ["小明", "小红", "小明", "小刚", "小明", "小红", "小丽"]
counts = {}

for name in submissions:
    if name in counts:        # 如果已经在字典里
        counts[name] += 1     # 次数加1
    else:                     # 如果第一次出现
        counts[name] = 1      # 初始化为1

print("交作业统计：", counts)
# 输出：{'小明': 3, '小红': 2, '小刚': 1, '小丽': 1}

这个套路在编程里非常常见，比如统计文章里每个单词出现的次数、统计商品销售数量等。

更多生活例子

  • 投票统计：全班同学投票选班长，每人投一票，统计每个候选人得票数。
  • 游戏得分：每次通关得一个宝物，统计每种宝物收集了多少个。
  • 零食柜：记录你吃了几包薯片、几根棒棒糖。

更简洁的写法：使用 get 方法

上面代码里的 if-else 可以用 dict.get() 简化：

counts = {}
for name in submissions:
    counts[name] = counts.get(name, 0) + 1  # 如果有就取值，没有就返回0，再+1
print(counts)  # 结果一样

这种写法更简洁，推荐掌握。

新手常犯的错误

  • 错误：先给字典赋初值 counts = {}，然后在循环里直接用 counts[name] += 1 会报 KeyError，因为第一次遇到一个名字时字典里还没有这个 key。
  • 错误：忘记重置计数器。如果多次运行同一个统计循环，要在开始前清空字典或重新创建。

三、快速查找：瞬间判断元素是否存在

哈希表的超能力：O(1) 时间查找

普通列表查找需要从头到尾遍历，如果列表很长（比如几万个号码），找一次要花很长时间。而字典（哈希表）能直接通过 key 计算出存储位置，无论字典多大，查找速度几乎不变（常数时间）。

例子：电话号码查询

给你一堆电话号码，你想知道某个号码是否在通讯录里。用字典可以瞬间判断。

# 模拟通讯录（电话号码作为key，名字作为value）
phone_book = {
    "13800138001": "小明",
    "13912345678": "小红",
    "13600001111": "小刚"
}

check_number = "13912345678"
if check_number in phone_book:
    print(f"找到了，这是{phone_book[check_number]}的电话")
else:
    print("未找到该号码")

更贴近生活的例子：单词词典

你想查一个英文单词是否在词典里，字典的 key 就是单词，value 是解释。

word_dict = {
    "apple": "苹果",
    "book": "书",
    "cat": "猫"
}

word = input("请输入要查的单词：")
if word in word_dict:
    print(f"{word} 的意思是：{word_dict[word]}")
else:
    print("词典中没有这个词")

新手常犯的错误

  • 错误：直接用 if phone_book[check_number]: 来判断存在。如果 key 不存在会直接报 KeyError，程序崩溃。正确做法是用 in 操作符。
  • 错误：认为 in 在列表和字典中一样快。实际上 in 在列表中是逐个比较（O(n)），在字典中是哈希查找（O(1)）。

完整示例：学生成绩管理系统

结合去重、计数和快速查找，做一个简单的成绩统计：

# 学生成绩列表（姓名，分数）
records = [
    ("小明", 90),
    ("小红", 85),
    ("小刚", 92),
    ("小明", 88),   # 小明有两次成绩？这里可能是补考或不同科目
    ("小丽", 95),
    ("小红", 89)
]

# 1. 去重：得到不重复的学生名单（按第一次出现顺序）
unique_students = list(dict.fromkeys([name for name, score in records]))
print("所有学生：", unique_students)

# 2. 计数：每个学生参加了几次考试
count_scores = {}
for name, score in records:
    count_scores[name] = count_scores.get(name, 0) + 1
print("考试次数统计：", count_scores)

# 3. 快速查找：查某个学生是否在名单中
check_name = "小刚"
if check_name in [name for name, score in records]:
    print(f"{check_name} 参加了考试")
else:
    print(f"{check_name} 没有参加考试")

运行结果：

所有学生： ['小明', '小红', '小刚', '小丽']
考试次数统计： {'小明': 2, '小红': 2, '小刚': 1, '小丽': 1}
小刚 参加了考试

总结与进阶指引

  • 去重：利用字典 key 唯一性，快速过滤重复数据，并保留顺序。
  • 计数：用 key 记录元素，value 累加次数，轻松统计频次。
  • 快速查找：利用哈希表的常数时间查找，判断元素是否存在。

就像生活中你有一个“快速索引”的工具，字典就是 Python 里最实用的库存管理器。下次遇到需要记录、统计或快速查找的问题时，第一个想到字典吧。

还想更高效？可以学习这些工具

  • collections.defaultdict：自动为不存在的 key 设置默认值，适合计数场景。
  • collections.Counter：专门用于计数的字典子类，一行就能完成统计。
  • 集合 set：纯粹的哈希表，只存 key 不存 value，用于去重和成员判断（但无序）。
  • 字典的 in 操作与列表的 in 操作的性能差异。

希望这篇文章能帮你把字典玩得溜溜的！

例题精讲

1单选题

在Python中，下列哪个选项可以作为字典的键？

A[1, 2, 3]
B(1, 2, 3)
C{1, 2, 3}
D{'a': 1}
2判断题

使用字典统计列表中元素出现次数时，可以使用 count_dict[key] = count_dict.get(key, 0) + 1 来更新计数。

3填空题
以下代码统计字符串列表 words 中每个单词出现的次数，请填空。\ncount_dict = {}\nfor word in words:\n    ___  # 填空1\n        count_dict[word] += 1\n    else:\n        ___  # 填空2\nprint(count_dict)
4单选题

关于Python字典（哈希表）查找操作的时间复杂度，下列说法正确的是：

A平均O(1)，最坏O(1)
B平均O(n)，最坏O(n)
C平均O(1)，最坏O(n)
D平均O(log n)，最坏O(n)
5填空题
以下代码使用字典实现“两数之和”问题：给定整数列表 nums 和目标值 target，返回两个数的下标（假设只有一组解）。请填空。\ndef two_sum(nums, target):\n    num_dict = {}\n    for i, num in enumerate(nums):\n        complement = target - num\n        if ___  # 填空1\n            return [num_dict[complement], i]\n        ___  # 填空2\n    return []