Python算法精讲：一文吃透哈希表（底层原理+基础语法+梯度例题全覆盖）

前言

在算法刷题的世界里，哈希表是当之无愧的效率神器，也是数组、双指针之外，面试和笔试中出现频率最高的数据结构。绝大多数需要快速查找、快速去重、统计频次的算法题目，用哈希表都可以直接把时间复杂度从暴力解法的O(n²)优化到O(n)，解题效率实现质的飞跃。

很多Python初学者刷题时，只会无脑遍历列表，不会活用哈希表，导致代码超时、逻辑冗余。本文从零开始讲解哈希表，不堆砌晦涩理论，结合Python原生语法，从基础概念、底层原理、基础写法，再到三道由易到难的真实算法例题，手把手带你掌握哈希表解题套路，全文可直接收藏作为算法刷题笔记。

一、哈希表基础介绍：什么是哈希表？

alt

1.1 通俗定义

哈希表（Hash Table）也叫散列表，是一种**键值对（key-value）**存储的数据结构，核心作用是：通过key可以在常数时间内，直接定位到value，完成查询、插入、删除操作。

我们可以用生活场景通俗理解：

数组：像一排连续的储物柜，只能通过柜子编号（下标）找物品，不知道编号就只能一个个挨个翻找，查找很慢；
哈希表：像快递驿站取件系统，你输入取件码（key），系统瞬间就能找到你的快递（value），不需要遍历所有包裹，查找速度恒定不变。

1.2 哈希表核心时间复杂度

理想状态下，哈希表的插入、删除、查询操作时间复杂度均为O(1)，这是它碾压数组、链表最大的优势。对比常见数据结构效率：

数据结构	查询	插入	删除
数组/列表	O(n)	O(1)	O(n)
链表	O(n)	O(1)	O(n)
哈希表	O(1)	O(1)	O(1)

1.3 两大核心底层概念

（1）哈希函数

哈希函数的作用：把任意长度的key，转换成固定长度的数组下标，从而直接定位存储位置。Python中内置hash()函数即可完成哈希计算。

（2）哈希冲突

不同的key经过哈希计算后，得到了同一个下标，就会产生哈希冲突。Python底层采用开放寻址法解决哈希冲突，开发者无需手动处理，这也是Python使用哈希表极其便捷的原因。

1.4 Python中的哈希表

Python中的字典dict，就是原生封装好的哈希表。除此之外，集合set底层同样是哈希表，仅存储key，不存储value，适合快速去重场景。日常算法刷题，90%场景我们都直接使用字典实现哈希表逻辑。

二、Python哈希表（字典）基础语法与基本写法

本节梳理算法刷题中必用的哈希表基础操作，所有代码均可直接复制运行，覆盖增、删、改、查、遍历五大核心操作。

2.1 哈希表初始化

# 方式1：空哈希表（最常用，刷题首选）
hash_map = {}

# 方式2：内置函数初始化
hash_map = dict()

# 方式3：直接初始化带键值对的哈希表
hash_map = {"a":1, "b":2, "c":3}

2.2 增/改操作

hash_map = {}
# 新增键值对：key不存在则新增
hash_map["name"] = "张三"
# 修改键值对：key存在则覆盖value
hash_map["name"] = "李四"
print(hash_map) # 输出：{'name': '李四'}

2.3 查询操作（刷题重中之重）

算法刷题禁止直接使用hash\_map\[key\]查询，容易出现键不存在报错，推荐两种安全查询方式：

hash_map = {"age":18}

# 方法1：get方法（推荐，无key返回默认值None）
print(hash_map.get("age"))      # 存在key，返回18
print(hash_map.get("score",0))  # 不存在key，返回自定义默认值0

# 方法2：in判断key是否存在（高频用于查找）
if "age" in hash_map:
    print("键存在")

2.4 删除操作

hash_map = {"a":1, "b":2}
del hash_map["a"]   # 根据key删除指定元素
hash_map.pop("b")   # 删除并返回对应value
hash_map.clear()    # 清空整个哈希表

2.5 哈希表遍历（刷题常用）

hash_map = {"语文":90, "数学":95}
# 遍历所有key
for key in hash_map:
    print(key)

# 遍历所有键值对（算法题最常用）
for key,value in hash_map.items():
    print(key,value)

2.6 刷题专属快捷方法：collections.defaultdict

普通字典查询不存在的key会报错，而defaultdict可以给不存在的key设置默认值，统计数字频次、字符频次时极度好用，是算法刷题必备工具：

from collections import defaultdict
# 不存在的key，默认value为0
count_map = defaultdict(int)
count_map["a"] += 1
print(count_map["a"]) # 输出1，无需提前初始化key

三、哈希表解题通用核心思路

在正式讲解例题前，先总结哈希表万能解题模板，所有哈希表题目都离不开三步：

遍历数组/字符串：逐个取出当前遍历元素；
判断目标值是否存在哈希表中：存在则直接返回答案，利用O(1)查询提速；
不存在则存入哈希表：记录当前元素和对应下标/频次，供后续遍历查询。

接下来从入门、进阶、高阶面试三个梯度，搭配LeetCode真题实战讲解，循序渐进吃透用法。

四、梯度算法例题实战讲解（由易到难）

例题1：入门级 LeetCode 1.两数之和（哈希表入门必刷）

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，数组中同一个元素不能使用两遍。 alt

解题思路对比

暴力解法：两层for循环遍历，时间复杂度O(n²)，数组长度过大直接超时；
哈希表解法：一层循环遍历，用哈希表存储遍历过的数字和下标，每次只需要查找target \- 当前数字是否存在表中，时间复杂度优化为O(n)。

完整代码+逐行注释

def twoSum(nums, target):
    # 初始化哈希表：key=数组数值，value=数值对应下标
    hash_map = {}
    # 遍历数组，enumerate同时获取下标和值
    for idx, num in enumerate(nums):
        # 计算需要寻找的互补数值
        complement = target - num
        # 判断互补值是否已经存在于哈希表
        if complement in hash_map:
            # 存在则直接返回两个下标
            return [hash_map[complement], idx]
        # 不存在，把当前数值和下标存入哈希表
        hash_map[num] = idx
    # 题目保证一定有解，此处返回仅补齐语法
    return []

# 测试用例
nums = [2,7,11,15]
target = 9
print(twoSum(nums,target)) # 输出：[0,1]

复杂度分析

时间复杂度：O(n)，仅遍历数组一次；
空间复杂度：O(n)，最差情况需要存储全部数组元素，空间换时间。

题目小结

这是哈希表最基础的空间换时间思想：用额外的哈希表存储空间，消除一层循环，大幅降低时间复杂度，也是所有哈希表题目的底层逻辑。

例题2：进阶级 LeetCode 242.有效的字母异位词（哈希表统计频次）

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。 alt

解题思路

本题核心需求是统计字符出现频次，完美适配哈希表：第一个字符串遍历统计每个字符出现次数，第二个字符串遍历依次抵消频次，最后判断哈希表所有频次是否都为0即可。

完整代码+逐行注释

from collections import defaultdict

def isAnagram(s: str, t: str) -> bool:
    # 长度不一致直接返回False，提前剪枝
    if len(s) != len(t):
        return False
    # 初始化频次哈希表，默认值为0
    char_count = defaultdict(int)
    # 遍历第一个字符串，字符频次+1
    for char in s:
        char_count[char] += 1
    # 遍历第二个字符串，字符频次-1
    for char in t:
        char_count[char] -= 1
        # 提前优化：出现负数直接返回False，无需后续遍历
        if char_count[char] < 0:
            return False
    # 判断所有字符频次是否归零
    for count in char_count.values():
        if count != 0:
            return False
    return True

# 测试用例
print(isAnagram("anagram","nagaram")) # True
print(isAnagram("rat","car")) # False

复杂度分析

时间复杂度：O(n)，n为字符串长度，仅两次线性遍历；
空间复杂度：O(1)，字符串仅包含26个小写字母，哈希表最多存储26个键值对，属于常数空间。

题目小结

哈希表最常用场景之二：元素频次统计。遇到统计数字、字符、元素出现次数的题目，优先用defaultdict构建频次哈希表，代码简洁且效率极高。

例题3：高阶面试题 LeetCode 3.无重复字符的最长子串（哈希表+滑动窗口）

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

解题思路

本题是面试高频算法题，单纯滑动窗口无法快速判断字符是否重复，需要滑动窗口+哈希表结合：哈希表存储字符最后一次出现的下标，当窗口内出现重复字符时，直接快速移动左边界，避免无效遍历，保证窗口内始终无重复字符。

完整代码+逐行注释

def lengthOfLongestSubstring(s: str) -> int:
    # 哈希表：key=字符，value=字符最新下标
    hash_map = {}
    # 左窗口边界、最长子串长度初始化
    left = 0
    max_len = 0
    # 右窗口边界遍历整个字符串
    for right, char in enumerate(s):
        # 核心判断：字符已存在 且 字符下标在当前窗口内
        if char in hash_map and hash_map[char] >= left:
            # 左窗口直接跳到重复字符下一位，收缩窗口
            left = hash_map[char] + 1
        # 更新当前字符最新下标
        hash_map[char] = right
        # 更新最长无重复子串长度
        max_len = max(max_len, right - left + 1)
    return max_len

# 测试用例
print(lengthOfLongestSubstring("abcabcbb")) # 输出3
print(lengthOfLongestSubstring("bbbbb"))    # 输出1

复杂度分析

时间复杂度：O(n)，左右指针均只遍历字符串一次；
空间复杂度：O(1)，字符集有限，哈希表存储空间为常数级别。

题目小结

这道题体现了哈希表的进阶用法：记录元素位置，辅助双指针/滑动窗口快速跳转边界。在双指针类题目中，哈希表可以快速记录历史信息，省去回头遍历的时间，是算法进阶必备组合技巧。

五、Python哈希表刷题常见避坑指南

不要直接用[]取值：未知key时优先用get()方法，避免KeyError报错；
可变类型不能做key：列表list、字典dict无法哈希，不能作为哈希表的键，字符串、数字、元组可以作为key；
区分字典和集合：只需要去重不用存数值，直接用set集合，代码更简洁；
空间换时间是核心：哈希表本质是牺牲内存换取查询速度，数据量极小时，数组遍历反而更省空间。

六、全文总结

本文从理论、基础语法、梯度真题三个维度，完整讲解了Python算法中的哈希表，我们可以把哈希表的核心价值和适用场景总结为一句话：但凡需要快速查找、去重、统计频次、记录元素位置的算法题，优先考虑哈希表。

回顾全文三大核心知识点：

底层原理：Python字典就是哈希表，依靠哈希函数实现O(1)常数级查询，核心思想是空间换时间；
基础用法：掌握字典增删改查、defaultdict默认字典、in关键字判断键存在，满足99%刷题需求；
三类解题场景：两数之和类快速查找、字母异位词类频次统计、滑动窗口类位置记录。

很多初学者刷题只会暴力循环，本质是没有养成哈希表的解题思维。后续刷题遇到超时问题，第一时间思考：是否可以用哈希表记录已经遍历过的数据，从而消除一层循环。坚持练习梯度真题，就能彻底摆脱暴力解法，写出高效简洁的Python算法代码。