哈希表
哈希表运用
- 字符串处理
数组交集
- 349. 两个数组的交集">349. 两个数组的交集
- 350. 两个数组的交集 II">350. 两个数组的交集 II
快乐数
- 202. 快乐数">202. 快乐数
两数之和
- 1. 两数之和">1. 两数之和
四数相加
- 454. 四数相加 II">454. 四数相加 II
赎金信
- 383. 赎金信">383. 赎金信
三数之和
- 15. 三数之和">15. 三数之和

哈希表

哈希表是根据关键码的值而直接进行访问的数据结构

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

哈希函数

如果hashCode得到的数值大于哈希表的大小了，也就是大于tableSize了，怎么办呢？
此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。

哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞

两种解法

拉链法

（数据规模是dataSize，哈希表的大小为tableSize）
其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放冲突的数据了。如图所示：

三种哈希结构

数组
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值会导致整棵树的错乱，所以只能删除和增加。

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

哈希表运用

数组就是简单的哈希表，但是数组的大小可不是无限开辟的

字符串处理

题目：

242. 有效的字母异位词

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。
我的解法（空间爆炸）：

    bool isAnagram(string s, string t) {
        int m = s.length();
        int n = t.length();
        multiset<char> a, b;
        int i ;
        for (i = 0; i < m; i++)
            a.insert(s[i]);
        for (i = 0; i < n; i++)
            b.insert(t[i]);
        if (a.size() != b.size())
            return false;
        else 
              return a==b;
        return true;
    }

空间爆炸2：

    bool isAnagram(string s, string t) {
        vector<char> vec1,vec2;
        vec1.assign(s.begin(), s.end());
        vec2.assign(t.begin(), t.end());
        sort(vec1.begin(), vec1.end());
        sort(vec2.begin(), vec2.end());
        return vec1 == vec2;
    }