- 哈希表是根据关键码的值而直接进行访问的数据结构，又叫做散列表，一般哈希表都是用来快速判断一个元素是否出现集合里
- 解决哈希碰撞有两种方法：拉链法，开放寻址法
- 常见的哈希结构（c++）set 和 map
| 集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|
| std::set | 红黑树 | 有序 | 否 | O(log n) | O(log n) |
| std::multiset | 红黑树 | 有序 | 是 | O(logn) | O(logn) |
| std::unordered_set | 哈希表 | 无序 | 否 | O(1) | O(1) |
std::unordered_set 底层实现为哈希表，std::set 和 std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以 key 值是有序的，但 key 不可以修改，改动 key 值会导致整棵树的错乱，所以只能删除和增加。
| 映射 | 底层实现 | 是否有序 | key是否可以重复 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|
| std::map | 红黑树 | key有序 | 否 | O(log n) | O(log n) |
| std::multimap | 红黑树 | key有序 | 是 | O(logn) | O(logn) |
| std::unordered_map | 哈希表 | key无序 | 否 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的 key 也是有序的
使用集合来解决哈希问题的时候，优先使用 unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用 set，如果要求不仅有序还要有重复数据的话，那么就用 multiset
- 利用哈希表（map，set）的性质解题
- 双指针算法（滑动窗口）（见双指针算法总结）
- 链接https://leetcode.cn/problems/valid-anagram/
- 解题方法：哈希表
将两个字符串存入两个哈希表并记录每个字符出现的次数
每个字符出现的次数相等则返回 true ，否则返回 false - leetcode解题代码
class Solution {
public:
bool isAnagram(string s, string t) {
unordered_map<char, int> a, b;
for (auto c: s) a[c] ++;
for (auto c: t) b[c] ++;
return a == b;
}
};
- 链接https://leetcode.cn/problems/ransom-note/
- 解题方法：哈希表
将字符串 b 存入哈希表，如果字符串 a 中出现了哈希表中没有的字符直接返回 false
如果出现了哈希表中存在的字符则哈希表的 value-1 - leetcode解题代码
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char, int> hash;
for (auto c: magazine) hash[c] ++;
for (auto c: ransomNote){
if (!hash[c]) return false;
hash[c] --;
}
return true;
}
};
- 链接https://leetcode.cn/problems/two-sum/
- 解题方法：哈希表
将数组元素存入哈希表，遍历数组求差，差值如果在哈希表中存在则返回下标 - leetcode解题代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); i ++){
int cur = target - nums[i];
if (hash.count(cur)) return {hash[cur], i};
hash[nums[i]] = i;
}
return {};
}
};
- 链接https://leetcode.cn/problems/4sum-ii/
- 解题方法：哈希表
a+b+c+d = 0 => a+b=-(c+d)
遍历 nums1 nums2 将 a+b 的和 x 存入哈希表，遍历 nums3 nums4 哈希表中有多少个 -x 就说明有多少个符合条件的组合 - leetcode解题代码
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> hash;
int res = 0;
for (auto a: nums1)
for (auto b: nums2)
hash[a + b] ++;
for (auto c: nums3)
for (auto d:nums4)
res += hash[-(c + d)];
return res;
}
};
- 链接https://leetcode.cn/problems/group-anagrams/
- 解题方法：哈希表
哈希表中存{key:["","",""]}
例如{"abc":["abc","acb","cba"]}
将所有的字符串按字典序排序，如果是字母异位词则一定有相同的字典序
如"abc","acb","cba"它们的字典序都是"abc"
key 存字典序，value 存有相同字典序的字符串 - leetcode解题代码
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> hash;// {"abc":["abc",[acb],[cab]]}
for (auto str: strs){
auto c = str;
sort(c.begin(), c.end());// 将所有字符串按字典序排序
hash[c].push_back(str);// 按照字典序把字符串存入哈希表
}
vector<vector<string>> res;
for (auto c: hash) res.push_back(c.second);// 将hash中的value拿出来
return res;
}
};
- 链接https://leetcode.cn/problems/intersection-of-two-arrays/
- 解题方法：哈希集合
unordered_set 不包含重复元素，key=value
将 num1 中的元素加入集合中，遍历 nums2 中的元素，如果集合中有相同的元素说明是交集，加入答案数组，并把当前元素从集合中删除 - leetcode解题代码
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set;
vector<int> res;
for (auto c: nums1) set.insert(c);
for (auto c: nums2){
if (set.count(c)){
res.push_back(c);
set.erase(c);
}
}
return res;
}
};
- 链接https://leetcode.cn/problems/intersection-of-two-arrays-ii/submissions/
- 解题方法：哈希集合
unordered_multiset 可以包含重复元素，key=value
和上一题思路类似 - leetcode解题代码
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_multiset<int> mtset;
vector<int> res;
for (auto c: nums1) mtset.insert(c);
for (auto c: nums2){
if (mtset.count(c)){
res.push_back(c);
mtset.erase(mtset.find(c));// 只删除一个c
}
}
return res;
}
};
- 链接https://leetcode.cn/problems/happy-number/submissions/
- 解题方法：哈希集合
通过集合判断一个数是否重复出现过，如果重复出现说明这个数陷入了循环直接返回 false，否则返回 true，用 res 记录每一次计算的结果并更新 n - leetcode解题代码
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> set;
while (n != 1){
int res = 0;
while (n){
res += (n % 10) * (n % 10);
n /= 10;
}
if (set.count(res)) return false;
set.insert(res);
n = res;
}
return true;
}
};