哈希表里的“垃圾元素”，为什么有时必须删除？
◆ 博主名称： 晓此方-ZEEKLOG博客
大家好，欢迎来到晓此方的博客。
⭐️C++系列个人专栏：
⭐️踏破千山志未空，拨开云雾见晴虹。 人生何必叹萧瑟，心在凌霄第一峰
目录
一、什么是哈希表中的垃圾元素
在做滑动窗口 + 哈希统计时，经常会出现一种现象：哈希表中存在 value = 0 的键值对。这些元素通常被称为 “垃圾元素”。
当我们做频率统计时，经常写这样的代码：
mp[x]--; 如果x原来是1，执行后变成了0但在map / unordered_map中：（xxx，0）仍然是一个真实存在的键值对，并不会自动删除。这种 key 仍存在，但 value 已经没有意义 的元素，就可以称为：哈希表垃圾元素（value = 0 的 key）
二、什么时候必须清理垃圾元素
先说结论，核心原则：
只要你的算法依赖“哈希表结构”进行判断，就必须清理。
2.1情况1：需要比较两个哈希表是否相等
典型例题：
LCR 015. 找到字符串中所有字母异位词 - 力扣（LeetCode）https://leetcode.cn/problems/VabMRr/description/本人有两解：
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> v; map<char, int> sc1; map<char, int> sc2; for (auto e : p) { sc2[e]++; } string::iterator left = s.begin(); string::iterator right = s.begin(); for (int i = 0; i < p.size(); i++) { if (right == s.end()) return v; sc1[*right]++; right++; } while (right != s.end()) { if (sc1 == sc2) { v.push_back(left - s.begin()); } sc1[*right]++; right++; sc1[*left]--; if (sc1[*left] == 0) sc1.erase(*left); left++; } if (sc1 == sc2) { v.push_back(left - s.begin()); } return v; } };class Solution { public: vector<int> findAnagrams(string s, string p) { map<char,int> mp1; map<char,int> mp2; for(auto e:p){mp2[e]++;} int m=p.size(); int n=s.size(); string ::iterator left=s.begin(); string ::iterator right=s.begin(); int count=0; vector<int> v; while(right!=s.end()) { mp1[*right]++; if(mp2.find(*right)!=mp2.end()&&mp1[*right]<=mp2[*right]) count++; while((right-left+1)>m) { if(mp2.find(*left)!=mp2.end()&&mp1[*left]<=mp2[*left]) count--; mp1[*left]--; if(mp1[*left]==0) mp1.erase(*left); left++; } if(count==m) v.push_back(left-s.begin()); right++; } return v; } };我们看第一解中的片段：if (sc1 == sc2) {v.push_back(left - s.begin()); 如果窗口移动时只写：sc1[*left]--;left++;没有删除：if (sc1[*left] == 0) sc1.erase(*left);就可能出现：
mp1： a -> 1 b -> 1 mp2： a -> 1 b -> 1 c -> 0 虽然频率逻辑是正确的，但 map 判断时：mp1 != mp2。因为mp2多了一个 key。结果：算法会 漏掉正确答案。因此：value == 0 必须 erase。
2.2情况2：算法依赖 map.size()
如果代码中出现：mp.size()来判断窗口状态，例如：窗口内不同字符数量那么：value = 0 的 key，会导致：size 统计错误。例如：
a -> 1 b -> 1 c -> 0 此时：size = 3。但实际上窗口里只有：2 个有效字符，因此必须删除。
if (mp[x] == 0) mp.erase(x); 三、什么时候不需要清理
如果你的算法 只关心频率值，例如：
mp[a] <= mp[b] mp[a] >= mp[b] mp[a]++ mp[a]-- 而 不比较 map 结构，通常可以不删除。典型例题：
30. 串联所有单词的子串 - 力扣（LeetCode）https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/本人有一解：（这里故意修改了一些代码方便下面讲解）
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> v; map<string, int> mp1; map<string, int> mp2; for (auto e : words) { mp1[e]++; } int len = words[0].size(); int n = words.size(); int lengthen = len * n; int count = 0; for (int i = 0; i < len; i++) { int right = i, left = i; while (right < s.size()) { mp2[s.substr(right, len)]++; if (mp1.find(s.substr(right, len)) != mp1.end() && mp2[s.substr(right, len)] <= mp1[s.substr(right, len)]) { count++; } if (right - left + len > lengthen) { if (mp1.find(s.substr(left, len)) != mp1.end() && mp2[s.substr(left, len)] <= mp1[s.substr(left, len)]) { count--; } mp2[s.substr(left, len)]--; if (mp2[s.substr(left, len)]==0) { mp2.erase(s.substr(left, len)); } left += len; } if (count == n) v.push_back(left); right += len; } mp2.clear(); count = 0; } return v; } };在这题中常见判断是：即使存在：s.substr(right, len) -> 0也不会影响逻辑正确性。因此 删除只是优化，不是必须。
mp2[s.substr(right, len)] <= mp1[s.substr(right, len)] 实际上这里的判断和删除逻辑并非必须，不需要像我一样这么冗余，但是加上mp1.find(s.substr(left, len)) != mp1.end()的判断效率会高很多。
if (mp1.find(s.substr(left, len)) != mp1.end() && mp2[s.substr(left, len)] <= mp1[s.substr(left, len)]) { count--; } mp2[s.substr(left, len)]--; if (mp2[s.substr(left, len)]==0) { mp2.erase(s.substr(left, len)); }四、从刷题中总结出来的实战经验
写滑动窗口哈希表时，可以记住一个简单规则：如果代码中出现：map1 == map2或者是map.size()。就必须写：
if (mp[key] == 0) mp.erase(key); 否则很容易出现隐藏 bug。如果只是做 频率比较，通常可以不删。
当算法依赖 哈希表结构（keys） 时必须去污；
当算法只依赖 哈希表数值（values） 时通常不必去污。
好了，本期内容到此结束，我是此方，我们下期再见。バイバイ！
