Python第八天：哈希表笔记以及题目整理

1. 哈希表的核心思想

哈希表（Hash Table）是一种根据关键码（key）的值直接进行访问的数据结构，其主要作用是快速判断一个元素是否出现在集合中。

核心思想：在关键码（key）和存储位置之间建立一个确定的对应关系f，使得每个关键字 key 对应一个唯一的存储位置。

2. 哈希表的直观比喻

可以将哈希表想象成一个大抽屉，这个大抽屉里面有很多小格子，每个格子可以用来存放数据。

• 抽屉编号（key）：通过这个 key 可以找到对应的抽屉
• 散列函数（Hash Function）：将数据的名字（key）转换成一个数字，然后根据这个数字来选择对应的抽屉
• 抽屉里的物品：实际存储的数据
• 快速查找：通过名字（key）可以快速地找到对应的抽屉

3. 哈希表的数据结构选择

在解决问题时，哈希表一般选择以下三种数据结构：

1. 数组（列表）
2. 集合
3. 映射

4. 哈希冲突与解决

哈希冲突：不同的 key 经过散列函数可能得到相同的数字（即映射到同一个抽屉）

解决冲突的方法：

• 开放地址法
• 链地址法
• 再哈希法
• 建立公共溢出区

5. 哈希表的优势

1. 快速查找：平均时间复杂度 O(1)
2. 直接访问：通过 key 可以直接定位到存储位置
3. 避免重复比较：不需要像线性查找那样逐个比较

6. 应用场景

1. 快速查找元素是否存在
2. 数据去重
3. 缓存实现
4. 字典/映射关系存储
5. 统计频率

7. 实现要点

# 简单哈希表示例classSimpleHashTable:def__init__(self,size=10):self.size=size self.table=[[]for_inrange(size)]# 使用链地址法解决冲突defhash_function(self,key):"""简单的散列函数"""returnhash(key)%self.sizedefinsert(self,key,value):"""插入键值对"""index=self.hash_function(key)self.table[index].append((key,value))defsearch(self,key):"""查找键对应的值"""index=self.hash_function(key)fork,vinself.table[index]:ifk==key:returnvreturnNone

8. 注意事项

1. 散列函数设计：好的散列函数应该均匀分布，减少冲突
2. 负载因子：存储元素数量与哈希表大小的比值，影响性能
3. 冲突处理：选择合适的冲突解决方法
4. 动态扩容：当负载因子过高时需要考虑扩容

总结：哈希表通过建立 key 到存储位置的直接映射关系，实现了快速的数据访问和查找，是计算机科学中非常重要的数据结构之一。

9. 实践示例：统计字符串中出现次数最多的字母

下面是一个统计字符串中出现次数最多的字母的Python示例，以及常见的错误分析：

# 读取一个整数 n，表示接下来有 n 行字符串要处理n=int(input())# 循环 n 次，每次处理一行字符串foriinrange(n):# 读取当前行的字符串（题目保证只含小写字母，但为了安全，我们后面过滤）s=input()# 创建一个长度为 26 的列表，用来记录 a~z 每个字母出现的次数# 26 * [0] 和 [0] * 26 效果相同，都是生成包含 26 个 0 的列表count=26*[0]# 遍历字符串中的每一个字符forcharins:# 只处理小写字母（避免空格、数字、大写字母等干扰）if'a'<=char<='z':# 计算当前字母在 count 列表中的索引（a->0, b->1, ..., z->25）idx=ord(char)-ord('a')# 该字母出现次数加 1count[idx]+=1# 开始查找出现次数最多的字母max_freq=0# 当前最大出现次数，初始为 0max_idx=-1# 当前最大次数对应的字母索引，-1 表示尚未找到# 遍历 26 个字母的计数forminrange(26):ifcount[m]>max_freq:# 发现更大的出现次数，更新最大值和对应索引max_freq=count[m]max_idx=m# 注意：这里用的是 > 而不是 >=，所以当次数相同时不会更新# 这样就会保留索引较小的字母，也就是字母顺序更小的那个（符合题目默认要求）# 将索引转换回对应的字母# ord('a') + max_idx 得到该字母的 Unicode 编码，chr() 将其转成字符result=chr(ord('a')+max_idx)# 输出这一行的结果print(result)

常见错误分析

错误①：range(s) 使用字符串作为参数

错误代码：

forjinrange(s):

报错：

TypeError: 'str' object cannot be interpreted as an integer

原因：range()函数只接受整数参数，而s是字符串类型。

正确做法：想遍历字符串的每个字符，可以直接用for char in s:，或者用for i in range(len(s)):再通过索引取字符。

错误②：把变量名写成字符串字面量

错误代码：

ch=ord('char')-ord('a')

报错：

TypeError: ord() expected a character, but string of length 4 found

原因：'char'是一个长度为 4 的字符串（由 c、h、a、r 四个字符组成），而ord()函数要求传入单个字符。你本意是用循环变量char，却误加了引号变成了固定字符串。

正确做法：变量名不能加引号，应写成ord(char)。

哈希思想在本例中的应用

这个例子实际上使用了哈希思想：

1. 哈希函数：ord(char) - ord('a')将字母映射到 0-25 的索引
2. 直接访问：通过索引直接访问count数组中的对应位置
3. 快速统计：时间复杂度为 O(n)，其中 n 是字符串长度

这种方法比使用字典（Python 内置的哈希表实现）更高效，因为数组的访问速度更快，且空间固定为 26。