Hash Table基础
哈希表(Hash Table)是常用的数据结构，其运用哈希函数(hash function)实现映射，内部使用开放定址、拉链法等方式解决哈希冲突，使得读写时间复杂度平均为O(1)。
HashMap(std::unordered_map)、HashSet(std::unordered_set)的原理与Hash Table一样，它们的用途广泛、用法灵活，接下来侧重于介绍它们的应用。
相关LeetCode题：
集合
如果仅需要判断元素是否存在于某个集合，我们可以使用结构HashSet(std::unordered_set)。例如 LeetCode题目 349. Intersection of Two Arrays：
// 349. Intersection of Two Arrays
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> s1(nums1.begin(),nums1.end());
unordered_set<int> s2(nums2.begin(),nums2.end());
vector<int> res;
for(auto& a:s1)
if(s2.count(a)) res.push_back(a);
return res;
}
相关LeetCode题：
349. Intersection of Two Arrays 题解
720. Longest Word in Dictionary 题解
计数
如果需要对元素进行计数，我们可以使用结构HashMap(std::unordered_map)，元素如取值范围固定可以用Array(std::vector)，例如LeetCode题目 217. Contains Duplicate：
// 217. Contains Duplicate
bool containsDuplicate(vector<int>& nums) {
unordered_map<int,int> m;
for(int x:nums) if(m[x]++==) return true;
return false;
}
相关LeetCode题：
266. Palindrome Permutation 题解
748. Shortest Completing Word 题解
451. Sort Characters By Frequency 题解
30. Substring with Concatenation of All Words 题解
在滑动窗口算法中常使用HashMap计数，关于滑动窗口算法，详见：算法与数据结构基础 - 滑动窗口(Sliding Window)
Key-Val
进一步地，HashMap表示一种Key-Val (或ID-属性) 关系，这里Val可以是计数、下标(index)等等。
相关LeetCode题：
953. Verifying an Alien Dictionary 题解
981. Time Based Key-Value Store 题解
244. Shortest Word Distance II 题解
映射
更一般地，HashMap表示一种映射关系，意义在于O(1)时间复杂度完成由 A->B 的映射。
相关LeetCode题：
535. Encode and Decode TinyURL 题解
HashMap与Prefix sum
利用HashMap和Prefix sum，我们可以在O(n)时间复杂度求解一类子序列求和问题，其中HashMap用于计数，例如LeetCode题目 560. Subarray Sum Equals K：
// 560. Subarray Sum Equals K
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> m;
m[]=;
int sum=,res=;
for(auto& a:nums){
sum+=a;
res+=m[sum-k];
m[sum]++;
}
return res;
}
相关LeetCode题：
930. Binary Subarrays With Sum 题解
325. Maximum Size Subarray Sum Equals k 题解
HashMap与图形问题
HashMap可以应用于二维图形的一些问题求解，以欧拉距离、斜率、x/y坐标等为key，以计数、x/y坐标为val。图形问题中HashMap的映射关系不是那么直观和明显，需要单独计算key、仔细甄别映射关系。
相关LeetCode题：
939. Minimum Area Rectangle 题解
HashMap与vector/list/stack结合
HashMap与vector、list、stack等数据结构可以结合成为复合数据结构，这样可以既用到HashMap O(1)的优点，也用到vector支持下标操作、list增删节点快、stack先进后出的特点。例如 LeetCode题目 380. Insert Delete GetRandom O(1)：
// 380. Insert Delete GetRandom O(1)
vector<int> v;
unordered_map<int,int> m;
以上用vector存储元素，unordered_map存储元素和对应下标；getRandom函数利用vector下标操作，而删除元素时，使用unordered_map取得被删元素、将vector末尾元素与其对调，利用了HashMap O(1)的优点。
相关LeetCode题：
380. Insert Delete GetRandom O(1) 题解