哈希表就是在关键字和存储位置之间建立对应关系。也就是：

  在 C++ 中可以使用无序容器来实现：

// 头文件
#include<unordered_map>
// 定义，这里表示key和value都是int型
unordered_map<int, int> map = {{1, 1}, {2, 2}, {3, 4}};
// 也可以指定key的类型
unordered_map<char, int> map;
// 如果没有指定元素，则map初始化的value为0
unordered_map<int, int> map;
// 迭代器
map.begin();
map.end();
// 添加 key 并统计重复的key个数
map[key]++;
// 添加 key 并去重
map[key];
// 添加指定的key和value
map[key] = value;
// 查找key（迭代器方式查找）
map.find(target);
// 返回指定key下的value
int value = map[key];

  可以看到 map [key] 既可以左赋值也可以右赋值，很灵活。

力扣 1

  两数之和
  在这里，对于一个固定值 target，我要找到数组中的对应元素以及他们的下标，那就先建立起数组元素 key 和他们下标 value 的映射，这样就构建出了一个哈希表 map，map 用来存放遍历过的元素，比如示例 1，当开始遍历元素 2 时，我想找到 7 是否遍历过，因为 9-2 = 7，但是发现没有，因此更新哈希表，将 key = 2 和 value = 0 放进 map 表中，然后开始遍历 7，在 map 中找有没有元素 2，如果找到了，返回 map 中 {2， 0} 集合，取 value = 0 和 value = 1，即构成了示例 1 的答案。

vector<int> twoSum(vector<int>& nums, int target)
{
    unordered_map<int, int> idx;//构建<key, value>容器集合
    for(int i = 0; i < num.size(); i++)
    {
        auto it = idx.find(target - nums[i]);//查找有没有target - nums[i]
        if(it != idx.end())//如果找到了
        {
            return {it->second, i};//it->second是在取value
        }
        idx[nums[i]] = i;//更新哈希表
    }
    return {};
}

  使用哈希表的时间复杂度为 $\small {O (N)}$，空间复杂度为 $\small {O (N)}$。比暴力解法 $\small {O (N^2)}$ 要快。

力扣 242

  有效的字母异位词
  这个题使用数组作为哈希表。由于 s 和 t 仅包含小写字母，可以统计两个字符串中 26 个小写字母出现的次数。如果 s 和 t 中 26 个字母出现的次数相等，说明 t 是 s 的字母异位词，如果不相等则不是。

bool isAnagram(string s, string t)
{
    // 判断长度是否相等，不相等一定不是字母异位词。
    if(s.length() != t.length())
        return false;
    // 定义一个全零的一维数组，大小为26。
    int table[26] = {0};
    // 统计s中26个字母出现的次数
    for(auto& it: s)
        table[it - 'a']++;
    for(auto& it: t)
    // 统计t中26个字母出现的次数（做差）
        table[it - 'a']--;
    // 此时table中保存的是t和s的次数差值，如果table中元素全为0，说明t和s是字母异位词，每个字母使用次数相等。如果出现任何非零值，则不是。
    for(int i = 0; i < 26; i++)
        if(table[i] != 0) return false;
    return true;
}

力扣 349

  两个数组的交集
  这个题不适用数组作为哈希表进行解决，因为可能输入的数据量非常大，数组会增加存储开销。因此用 set 数据类型进行解决，set 和 map 一样，也是一类哈希表，不过只有一列数据。C++ 中可由下面定义：

//定义
unordered_set<int> set(vector<int>.begin(), vector<int>.end());
unordered_set<int> set();
//迭代器
set.begin();
set.end();
//插入数据并自动去重
set.insert(target);
//寻找目标数据（迭代器）
set.find(target);

  这里先将 nums1 转换为 set 数据，然后查找 nums2 中的元素在 set 表中是否存在，如果存在就将结果保存下来，最后输出。这里用 set 还有一个好处就是会自动去重，所以无需处理结果中可能存在的重复元素。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
    unordered_set<int> res;
    // 使用迭代器初始化set表
    unordered_set<int> table(nums1.begin(), nums1.end());
    // 遍历 nums2 中的元素
    for(int num : nums2)
    {
        // 迭代寻找 num 是否存在于表中
        if(table.find(num) != table.end())
            // 存在则保存结果（这里会实现去重）
            res.insert(num);
    }
    // 使用迭代器的方式将 set 类型转换为 vector<int> 类型
    return vector<int>(res.begin(), res.end());
}

  时间复杂度是 $\small {O (M + N)}$，$\small {N}$ 是遍历 nums2，$\small {M}$ 是最后 res 转换为 vector。空间复杂度是 $\small {O (N)}$。

力扣 454

  四数相加 Ⅱ
  这个题目如果使用暴力解法，复杂度是 $\small {O (N^4)}$。注意到题目要求 nums1 [i] + nums2 [j] + nums3 [k] + nums4 [l] == 0，也就是 nums1 [i] + nums2 [j] == - nums3 [k] - nums4 [l]。那么可以两两一组，先遍历计算 nums1 和 nums2 元素的和，并建立 map 表（这里用 map 表是因为可以利用 value 统计相同元素出现的个数），然后再遍历寻找 nums3 和 nums4 元素的和（取相反数）是否出现在 map 表中，如果出现将对应 value 值相加，最终就能够返回元组个数。

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
{
    // 初始化table后table里面的value默认为0
    unordered_map<int, int> table;
    for(int& a : nums1)
    {
        for(int& b : nums2)
        {
            // 这里有两层含义，如果a + b在table中有相同的元素，value++，如果没有，那么table 自动添加a + b的值，并value++
            table[a + b]++;
        }
    }
    int count = 0;
    for(int& c : nums3)
    {
        for(int& d : nums4)
        {
            int target = -(c + d);
            if(table.find(target) != table.end())
                // 这里意思是返回指定key下的value
                count += table[target];
        }
    }
    return count;
}

  时间复杂度是 $\small {O\left (N^2 \right)}$，空间复杂度是 $\small {O\left (N^2 \right)}$。