首先定义unordered_map<int, int> pairs，默认哈希表数组大小为n;

哈希表底层就是个多条链表数组，哈希表本质是降低算法的时间复杂度(从O(n)到O(1))。而插入和搜索是哈希表中的两个基本操作。

哈希表各函数的定义

• 使用count，返回的是被查找元素的个数。如果有，返回1；否则，返回0。注意，map中不存在相同元素，所以返回值只能是0或1。
• 使用find，返回的是被查找元素的位置，没有则返回pairs.end()。
• 在for()循环中，pairs[nums[i]]++用于统计各元素出现的频次，而pairs[nums[i]] = i则用于把各个元素放入哈希表！
• 在统计频次时，直接用pairs[nums[i]]即可。如果用pairs.count(nums[i])可能会有问题。
• 打印哈希表： for(auto it = pairs.begin(); it != pairs.end(); it++) { cout « it->first « it->second « endl;} 其中it->first打印的是key值，it->second打印的是second值
• 设有哈希函数(散列函数)y = x ％ 5 ，其中 x 是键值value，y 是分配的桶的索引key。散列函数将取决于value的范围和key的数量。散列函数示意如下图：

• 哈希函数的设计是一个开放的问题。其思想是尽可能将value(键)分配到key(桶)中，理想情况下，完美的哈希函数将是value和key之间的一对一映射。然而，在大多数情况下，哈希函数并不完美，它需要在桶的数量和桶的容量之间进行权衡。

哈希冲突与处理方法

哈希冲突(散列冲突)

理想情况下，如果我们的哈希函数是完美的一对一映射，我们将不需要处理冲突。不幸的是，在大多数情况下，冲突几乎是不可避免的。例如，在哈希函数（y = x ％ 5）中，1987和2都分配给了key2，这就是一个冲突。

冲突解决算法应该解决以下几个问题：

1. 如何组织在同一个key中的值？
2. 如果为同一个key分配了太多的值，该怎么办？
3. 如何在特定的key中搜索目标值？
   根据我们的哈希函数，这些问题与key的容量和可能映射到同一个key的value数目有关。

让我们假设存储最大键数的key有 N 个value。通常，如果 N 是常数且很小，我们可以简单地使用一个数组将value存储在同一个key中。如果 N 是可变的或很大，我们可能需要使用高度平衡的二叉树来代替.。

解决冲突的方法

1. 开放寻址法

如果一个数x是哈希表中的value值，那么它的键key = (x % n + n) % n.

1. 拉链法(和图论知识相关)

LC20: 匹配的括号

解题思路

代码如下

bool isValid(string s)
{
    int n= s.size();
    if(n % 2 == 1)
    {
        return false;
    }
    
    unordered_map<char, char> pairs = {
                                        {')', '('}, 
                                        {']', '['}, 
                                        {'}', '{'}}; //注意闭合括号在前
    stack<char> stk;   //新建一个栈，用于存储当前需要比对的括号
    for(char ch:s) //遍历字符串，变量为ch
    {
        if(pairs.count(ch))//count找到的是value值，也即开始括号。
        {
            if(stk.empty() || stk.top() != pairs[ch])
            {
                return false;
            }
            stk.pop();
        }
        else
        {
            stk.push(ch);
        }
    }
    return stk.empty();
}

LC387: 字符串中的第一个唯一字符

解题思路

自从掌握了哈希表的用法后，这类问题统一使用哈希表解决，速度飞快！

代码如下

int firstUniqChar(string s) {
    unordered_map<char, int> pairs;
    //我的想法：先用哈希表存储元素
    for(int i = 0; i < s.size(); i++) {
        pairs[s[i]]++;
    }
    //然后直接找出现频率=1的字符。
    for(int i = 0; i < s.size(); i++) {
        if(pairs[s[i]] == 1) {
            return i;
        }
    }        
    return -1;

}

LC128: 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

解题思路

• 看到此类问题联想到哈希表unordered_set。先把所有元素存入不重复元素哈希表中，然后进行连续子序列查找。
• 首先确定查找元素前一个元素是否存在。不存在才可进行下一步查找。定义一个变量x，每次遍历后把这个x+1，用于统计连续序列的长度(x - num),然后将其和结果值res取最大值即可。

代码如下

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> pair(nums.begin(), nums.end());//C++11新特性可以这么写
    int res = 0;
    //遍历哈希表中元素。如果没有前一个元素，就从当前元素开始计数
    for(auto &num : pair) {
        if(!pair.count(num - 1)) {
        //定义变量x，用于定位当前遍历位置，从而获得遍历长度
            int x = num + 1;
            while(pair.count(x)) {
                x++;
            }
            res = max(res, x - num);
        }
    }
    return res;
}

LC49: 字母异位词分组

• 给你一个字符串数组，请将字母异位词组合在一起。可以按任意顺序返回结果列表。本题中只涉及小写字母，因此可使用排序方法。

解题思路

1. 先用哈希表存储这个vector 的全部元素。其中key值为异位词的根，value值为满足当前异位词标准的全部string。
2. 之后将这个哈希表的it->second(也即哈希表的value值)打印出来即可。

• 数组的长度为n, 字符串最大长度为k，则遍历一次数组的时间复杂度为O(n)，而每次遍历还需要对字符串进行排序，排序时间复杂度为O(klogk)；
• 哈希表需要存储所有的字符串，所以算法的空间复杂度为O(n * k);
• 综上所述，算法的时间复杂度为O(n^2logn), 空间复杂度为O(n^2)

代码如下

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> pairs;
    for(int i = 0; i < strs.size(); i++) {
        string a = strs[i];
        sort(a.begin(), a.end());//排序是为了定下"异位词"基准，将其作为哈希表的key值。
        pairs[a].push_back(strs[i]);//将每一个strs[i]作为value值插入哈希表。
    }
    //定义结果数组，push_back哈希表的value值即可。
    vector<vector<string>> res;
    for(auto it = pairs.begin(); it != pairs.end(); it++) {
        res.push_back(it->second);
    }
    return res;
}

LC202：快乐数

「快乐数」 定义为：

1. 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
2. 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
3. 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

解题思路：

• 使用哈希表存储每次得到的数。如果这个数已经出现在哈希表中，说明出现了死循环，直接返回false；如果一直没有重复元素，那么返回n == 1即可。

代码如下：

//优雅的哈希表！
/* 分离数字计算各个数字的平方和 */
int getSum(int n){
    int sum = 0;
    while(n){
        sum += (n%10)*(n%10);
        n /= 10;
    }
    return sum;
}
/* 判断一个数是不是快乐数 */
bool isHappy(int n) {
    int sum = 0;
    unordered_set<int> set;
    while(1){
        sum = getSum(n);
        /* 判断和是不是1 */
        if(sum == 1)  return true;
        /* 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false */
        if(set.find(sum) != set.end()) return false;
        else set.insert(sum);
        /* 更新n */
        n = sum;
    }
}

• Previous
  各类基本排序算法汇总
• Next
  如何从无到有构建一棵二叉树