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

1. 哈希表的核心思想哈希表Hash Table是一种根据关键码key的值直接进行访问的数据结构其主要作用是快速判断一个元素是否出现在集合中。核心思想在关键码key和存储位置之间建立一个确定的对应关系f使得每个关键字 key 对应一个唯一的存储位置。2. 哈希表的直观比喻可以将哈希表想象成一个大抽屉这个大抽屉里面有很多小格子每个格子可以用来存放数据。抽屉编号key通过这个 key 可以找到对应的抽屉散列函数Hash Function将数据的名字key转换成一个数字然后根据这个数字来选择对应的抽屉抽屉里的物品实际存储的数据快速查找通过名字key可以快速地找到对应的抽屉3. 哈希表的数据结构选择在解决问题时哈希表一般选择以下三种数据结构数组列表集合映射4. 哈希冲突与解决哈希冲突不同的 key 经过散列函数可能得到相同的数字即映射到同一个抽屉解决冲突的方法开放地址法链地址法再哈希法建立公共溢出区5. 哈希表的优势快速查找平均时间复杂度 O(1)直接访问通过 key 可以直接定位到存储位置避免重复比较不需要像线性查找那样逐个比较6. 应用场景快速查找元素是否存在数据去重缓存实现字典/映射关系存储统计频率7. 实现要点# 简单哈希表示例classSimpleHashTable:def__init__(self,size10):self.sizesize self.table[[]for_inrange(size)]# 使用链地址法解决冲突defhash_function(self,key):简单的散列函数returnhash(key)%self.sizedefinsert(self,key,value):插入键值对indexself.hash_function(key)self.table[index].append((key,value))defsearch(self,key):查找键对应的值indexself.hash_function(key)fork,vinself.table[index]:ifkkey:returnvreturnNone8. 注意事项散列函数设计好的散列函数应该均匀分布减少冲突负载因子存储元素数量与哈希表大小的比值影响性能冲突处理选择合适的冲突解决方法动态扩容当负载因子过高时需要考虑扩容总结哈希表通过建立 key 到存储位置的直接映射关系实现了快速的数据访问和查找是计算机科学中非常重要的数据结构之一。9. 实践示例统计字符串中出现次数最多的字母下面是一个统计字符串中出现次数最多的字母的Python示例以及常见的错误分析# 读取一个整数 n表示接下来有 n 行字符串要处理nint(input())# 循环 n 次每次处理一行字符串foriinrange(n):# 读取当前行的字符串题目保证只含小写字母但为了安全我们后面过滤sinput()# 创建一个长度为 26 的列表用来记录 a~z 每个字母出现的次数# 26 * [0] 和 [0] * 26 效果相同都是生成包含 26 个 0 的列表count26*[0]# 遍历字符串中的每一个字符forcharins:# 只处理小写字母避免空格、数字、大写字母等干扰ifacharz:# 计算当前字母在 count 列表中的索引a-0, b-1, ..., z-25idxord(char)-ord(a)# 该字母出现次数加 1count[idx]1# 开始查找出现次数最多的字母max_freq0# 当前最大出现次数初始为 0max_idx-1# 当前最大次数对应的字母索引-1 表示尚未找到# 遍历 26 个字母的计数forminrange(26):ifcount[m]max_freq:# 发现更大的出现次数更新最大值和对应索引max_freqcount[m]max_idxm# 注意这里用的是 而不是 所以当次数相同时不会更新# 这样就会保留索引较小的字母也就是字母顺序更小的那个符合题目默认要求# 将索引转换回对应的字母# ord(a) max_idx 得到该字母的 Unicode 编码chr() 将其转成字符resultchr(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)):再通过索引取字符。错误②把变量名写成字符串字面量错误代码chord(char)-ord(a)报错TypeError: ord() expected a character, but string of length 4 found原因char是一个长度为 4 的字符串由 c、h、a、r 四个字符组成而ord()函数要求传入单个字符。你本意是用循环变量char却误加了引号变成了固定字符串。正确做法变量名不能加引号应写成ord(char)。哈希思想在本例中的应用这个例子实际上使用了哈希思想哈希函数ord(char) - ord(a)将字母映射到 0-25 的索引直接访问通过索引直接访问count数组中的对应位置快速统计时间复杂度为 O(n)其中 n 是字符串长度这种方法比使用字典Python 内置的哈希表实现更高效因为数组的访问速度更快且空间固定为 26。