一、今日学习目标

掌握哈希表的核心理论（哈希函数、哈希碰撞及解决方法），理解数组、set、map 三种哈希结构的适用场景，并通过「两个数组的交集」「快乐数」「两数之和」三道题目，实战掌握哈希表在快速查找、去重、键值映射等场景的应用。

二、核心理论知识

1、哈希表的数学本质

理论知识

哈希表是一种通过「关键码直接访问数据」的数据结构，其核心是哈希函数—— 将关键码（如数值、字符串）映射为哈希表的索引，实现 O (1) 级别的快速访问。从数学角度看，哈希函数可表示为：
index=hashFunction(key) mod tableSize

2、哈希碰撞与解决方法

当不同关键码映射到同一索引时，产生哈希碰撞，常见解决方法：

• 拉链法：在碰撞索引处构建链表，存储所有冲突元素（如 Java 的 HashMap）。需合理设置tableSize，避免链表过长影响效率。
• 线性探测法：当碰撞发生时，依次检查下一个索引（index+1, index+2...），要求tableSize > dataSize（数据量），确保有足够空位。

3、三种常见的哈希结构对比

结构	底层实现	使用场景
数组	连续内存	关键码范围小且连续
set	红黑树、哈希表	需去重且无需存储额外信息
map	红黑树、哈希表	需存储键值对

三、实战解题

1、有效的字母异位词

题目描述

LeetCode 242 有效的字母异位词

代码实现

文章讲解

Python代码

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""record = [0]*26for i in s:record[ord(i)-ord('a')] += 1for i in t:record[ord(i)-ord('a')] -= 1for i in range(26):if record[i] != 0:return  Falsereturn True

调试过程

通过调试发现，看似简单的计数逻辑，需重点关注输入合法性（长度、字符范围）和效率优化（提前终止），这也是哈希表类问题的通用调试要点 —— 既要保证逻辑正确，也要兼顾边界场景和性能。

2、两个数组的交集

题目描述

LeetCode 349 两个数组的交集

代码实现

文章讲解

Python代码

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""table = {}for num in nums1:table[num] = table.get(num, 0)+1res = set()for num in nums2:if num in table:res.add(num)del table[num]return list(res)

调试过程

最初尝试用列表存储结果，未考虑去重，导致输出包含重复元素（如示例中 nums2 的两个 4）。改用 set 存储结果后，自动去重问题解决。

3、快乐数

题目描述

LeetCode 202 快乐数

代码实现

文章讲解

Python代码

class Solution(object):def isHappy(self, n):""":type n: int:rtype: bool"""seen = []while n != 1:n = sum(int(i)**2 for i in str(n))if n in seen:return Falseseen.append(n)return True

调试过程

最初忽略了「无限循环」的本质，未用 set 记录中间结果，导致程序陷入死循环。加入 set 后，当检测到重复的 n 时，可直接判断为非快乐数。

4、两数之和

题目描述

LeetCode 1 两数之和

代码实现

文章讲解

Python代码

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""records = dict()for index, value in enumerate(nums):if target - value in records:return [records[target - value], index]records[value] = indexreturn []

调试过程

通过调试发现，该解法的关键在于哈希表存储元素与索引的映射，并利用遍历顺序确保重复元素的索引正确性。需注意的边界条件包括：

1. 重复元素：哈希表覆盖索引的行为因遍历顺序而不影响结果；

2. 无解情况：需确保代码返回空列表而非报错；

3. 特殊数值：负数、零等需验证哈希表查询逻辑。

四、易错点总结

题目	易错点	解决方法
两个数组的交集	结果未去重；用数组导致空间浪费	用 set 存储结果；数值范围不确定时优先用 set
快乐数	未检测循环导致死循环；求和时漏处理个位	用 set 记录中间结果；用 divmod 统一处理各位
两数之和	用 set 无法存储下标；忽略元素重复情况	用 map 存储键值对；依赖遍历顺序避免重复使用

五、扩展思考

1.** 哈希函数设计 ：好的哈希函数应尽量减少碰撞，可结合数论中的「素数取模」（如 HashMap 的容量为 2ⁿ，减少碰撞概率）。
2. 时间复杂度对比 **：

• 数组：查询 O (1)，但空间复杂度 O (M)（M 为最大可能值）；

• unordered_set/map：查询 O (1)（平均），空间 O (n)，适合大数据量；

• set/map（红黑树）：查询 O (logn)，但有序，适合需排序的场景。