当前位置：首页 > news >正文

哈希表的使用

news 来源：原创 2025/5/20 19:40:32

哈希表的概念：哈希表的核心是哈希函数，它接受一个键作为输入，经过一系列计算后返回一个整数，这个整数就是该键对应的存储位置（索引）。理想情况下，不同的键应该映射到不同的存储位置，但在实际应用中，可能会出现多个键映射到同一个位置的情况，这被称为哈希冲突。

哈希结构(三种常见的)：

1.set（集合） 2.数组 3.map（映射）

哈希函数的设计至关重要，一个好的哈希函数应该满足以下几个特点：
1、确定性：对于相同的键，哈希函数必须始终返回相同的哈希值。
2、高效性：计算哈希值的过程应该尽可能快，以保证哈希表的操作效率。
3、均匀性：哈希函数应该尽可能均匀地将键分布到各个存储位置，减少哈希冲突的发生。

哈希冲突：哈希冲突指的是当使用哈希函数将不同的键（Key）映射到哈希表中相同的存储位置（索引）的情况。由于哈希表的存储位置数量是有限的，而可能的键的数量往往是无限的，所以在实际应用中，很难保证每个键都能被哈希函数映射到不同的位置，从而导致哈希冲突的发生。（可以用开放寻址法和链地址法解决）

哈希表的操作
1、 插入操作：首先通过哈希函数计算键的哈希值，找到对应的存储位置。如果该位置为空，则直接插入键值对；如果发生哈希冲突，根据采用的冲突解决方法进行处理。
2、 查找操作：同样通过哈希函数计算键的哈希值，找到对应的存储位置。如果该位置存储的键与要查找的键相同，则返回对应的值；如果不同或该位置为空，则表示未找到。
3、 删除操作：先找到要删除的键所在的位置，然后将该位置标记为已删除（在开放寻址法中）或从链表中移除（在链地址法中）。

哈希表插入、查找、删除操作都很高效，一般状况下的时间复杂度均为O(1),如果哈希冲突严重时即所有的键值都在同一个地方那么三个操作的时间复杂度就会转化为O(n)。

哈希表在题目里的应用:可以统计某个元素出现的次数...

一、单词字母异位

解题思路(哈希表)：

1.初始化计数数组：首先，创建一个长度为 26 的数组 record，用于记录字符串中每个小写英文字母出现的次数。数组的每个位置对应一个字母（'a' 对应位置 0，'b' 对应位置 1，依此类推）。
2.统计字符串 s 中每个字符的出现次数：遍历字符串 s 中的每个字符 i，通过计算 ord(i) - ord("a") 得到字符相对于 'a' 的偏移量（即字符在字母表中的位置），然后将对应位置的计数器加一。
3.减去字符串 t 中每个字符的出现次数：遍历字符串 t 中的每个字符 i，同样通过计算 ord(i) - ord("a") 得到字符的位置，然后将对应位置的计数器减一。
4.检查计数器数组：最后，遍历计数器数组 record。如果所有元素的值都为 0，说明字符串 s 和 t 包含相同数量和种类的字符，因此它们是字母异位词，函数返回 True。如果数组中有任何非零元素，说明两个字符串的字符种类或数量不同，函数返回 False。
5.输入和输出：代码最后部分从用户那里读取两个字符串 s 和 t，然后调用 isAnagram 函数判断它们是否为字母异位词，并打印结果。

def isAnagram(s,t):record = [0] * 26for i in s:#并不需要记住字符a的ASCII，只要求出一个相对数值就可以了record[ord(i) - ord("a")] += 1for i in t:record[ord(i) - ord("a")] -= 1for i in range(26):if record[i] != 0:#record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。return Falsereturn True
s = input()
t = input()
print(isAnagram(s,t))

二、赎金信

解题思路(哈希表)：

初始化字符计数器：首先，创建一个空字典 counts，用于记录杂志 magazine 中每个字符的出现次数。

统计杂志中的字符：遍历杂志字符串 magazine 中的每个字符 c，如果字符 c 不在字典 counts 中，则将其添加到字典中，并将对应的值设为 1（表示该字符在杂志中出现了一次）。如果字符 c 已经在字典中，则将其对应的值加一（表示该字符在杂志中又出现了一次）。

检查信中的字符：遍历勒索信字符串 ransomNote 中的每个字符 c，执行以下操作：

如果字符 c 不在字典 counts 中，说明杂志中没有这个字符，因此无法构造出勒索信，函数返回 False。
如果字符 c 在字典 counts 中，但对应的值为 0，说明杂志中该字符的数量已经被之前的信字符用完，因此也无法构造出勒索信，函数返回 False。
如果字符 c 在字典 counts 中且对应的值大于 0，则将对应的值减一（表示使用了一个该字符来构造信）。

判断能否构造完成：如果勒索信中的所有字符都成功地在杂志中找到了足够的数量，并且没有触发返回 False 的条件，那么函数在遍历完勒索信后返回 True，表示可以使用杂志中的字符来构造出勒索信。

输入和输出：代码最后部分从用户那里读取两个字符串 r（代表信）和 m（代表杂志），然后调用 canConstruct 函数判断是否能用杂志构造出信，并打印结果。

def canConstruct(ransomNote, magazine):counts = {}for c in magazine:counts[c] = counts.get(c, 0) + 1for c in ransomNote:if c not in counts or counts[c] == 0:return Falsecounts[c] -= 1return True
r = input()
m = input()
print(canConstruct(r,m))

相关文章：