代码随想录—哈希表 | Aryue的个人博客

type

status

date

slug

summary

🤔 序

自3月27日开始刷题至今，已经完成了三个模块的题目，并且写了三篇文章。我对自己刷题速度还是比较满意的，因为明显这一周的刷题速度和进度都大幅加快了。此外，我当前整理的工作流也非常舒适。当算法出现问题时，我可以让gpt4帮我修改和分析；当我遇到一些不熟悉的C++操作和知识点时，我也可以随时向它提问，就好像一个不厌其烦的个人私教。

例如，今天我还问了一个刷算法时的问题——如何根据题目要求处理溢出情况。它的回答如下：

溢出问题.md

2.0KB

言归正传，这一篇文章来总结哈希表相关知识和常见题型。

📝基础理论

哈希表

数组

要在算法中使用哈希表，就要先弄明白哈希表擅长用来解决哪些问题。一般来说，哈希表都是用来快速判断一个算法是否出现在集合中。

因此，在刷题过程中，当我们遇到需要查询之前的记录时，就要马上第一时间想到能否使用哈希表。

哈希函数

哈希函数就是通过特定的编码方式，将其他数据结构转化为不同的数值，而这个数值就是哈希表上的索引值，从而加快我们在表上查找的效率。

哈希碰撞

所谓的哈希碰撞，是指两个数据都映射到了同一索引位置。

通常可以通过拉链法和线性探测法进行优化。

拉链法比较简单粗暴，就是将索引位置创建一个链表，后进入索引位置的元素插入到链表的尾部。这样做的好处是容易处理，坏处是随着拉链长度的增加，查询的时间复杂度可能会退化。

线性探测法的思路则截然不同，它采取通过再次为元素选取一个位置的方法解决冲突问题。这里不再过多赘述，有关哈希碰撞还有很多细节，可以自行探索。

常见的哈希结构

数组

在C++中，具体如下：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

非必要情况下，使用C++11中新增的unordered_set和unordered_map即可，可以达到查询效率和增删效率的最大程度的优化。

由于笔者以前主要使用C#，顺便查了一下C#中对应的数据结构。最常用的就是Dictionary和HashSet，分别对应上述的unordered_map和unordered_set。

🤗题型

字符串型

这两个题目基本上属于同一类型，因为只包含小写字母，可以通过一个长度为 26 的数组存储第一个单词中各个字母出现的次数。具体方法是通过 ASCII 码进行计算，然后填写到相应的位置上。

两数之和、三数之和、四数之和、四数相加？

力扣题目链接—两数之和

力扣题目链接—三数之和

力扣题目链接—四数之和

力扣题目链接—四数相加

这些题目都是求和等于target的组合。如果使用暴力解法，时间复杂度可能为n的平方、n的三次方或n的四次方。

然而，我们之前提到过，在需要查询元素是否出现过时，应该首先考虑哈希方法。以这里的两数之和为例，我们只需要遍历一次即可。在遍历到某个数n时，先判断target-n是否出现过。如果出现过，就找到了对应的组合；如果没有出现过，将该数加入哈希表中。

这里需要注意一点，之前的字母相关题目可以用数组来存储，因为这里的数字不仅仅有26种了，所以就需要使用unordered_map存储，键值对分别为数字和对应的下标。

以此类推，所有的题目都可以使用哈希方法吗？答案是否定的。对于两数之和和四数相加问题是可以的，因为我们只需要返回对应的结果，不需要考虑去重问题。而哈希方法在解决去重上是很困难的，所以无法解决这里的三数之和和四数之和问题。

这里的三数之和和四数之和问题需要使用双指针法。双指针法同样可以将时间复杂度降低一个数量级，优化虽然有限，但还是不错的。

快乐数

这种问题如果分析得当，可以发现仍然可以用哈希表解决。在“快乐数”问题中，题意中说到可能会陷入“无限循环”而不是“无限不循环”，所以我们可以使用一个哈希表记录已经出现的数。如果在计算过程中再次出现，可以肯定其不是快乐数。

参考文章

代码随想录

代码随想录PDF，代码随想录百度网盘，代码随想录知识星球，代码随想录八股文PDF，代码随想录刷题路线，代码随想录知识星球八股文

https://programmercarl.com/哈希表总结.html#map作为哈希表

💡

Written by Aryue，editted by Notion AI.