算法思想总结：哈希表

一、哈希表剖析

1、哈希表底层：通过对C++的学习，我们知道STL中哈希表底层是用的链地址法封装的开散列。

2、哈希表作用：存储数据的容器，插入、删除、搜索的时间复杂度都是O（1），无序。

3、什么时候使用哈希表：需要频繁查找数据的场景。

4、OJ中如何使用哈希表？？？

（1）STL中的容器（适用所有场景，比如字符串相关、数据映射下标）

（2）数组模拟简易哈希表（减小时间损耗，容器的封装有一定代价）—>大多以下两种情况适用

情况1：（char）涉及到字符串中的“字符” ，hash[26]可以映射所有的字母。

情况2：（int）数据范围较小的时候

二、两数之和

. - 力扣（LeetCode）

解法2代码：

三、判定是否互为字符重排

. - 力扣（LeetCode）

解法2代码：

四、存在重复元素I

. - 力扣（LeetCode）

解法2代码：

五、存在重复元素II

. - 力扣（LeetCode）

解法1代码：

解法2代码：

六、存在重复元素III(经典)

. - 力扣（LeetCode）

解法1代码：

思路2：分桶（非常精巧的思路）

思路来源：. - 力扣（LeetCode）分桶思路详细讲解

因为这个思路来源写得非常的详细，所以直接看就行，以往我们的分桶，更多的是针对整数的分桶，但是在该题中，扩展了存在负数的时候如何分桶，保证每个桶内的元素个数是一样的。这是一种非常巧妙的方法！！！要结合具体的实例去看！！

核心思路：保证每个桶内的绝对值相差小于t，k个桶。当我们遍历到这个数的时候，如果对应的桶的存在，就是true，如果相邻桶存在，看看差值是否符合要求。每个桶中只会有一个元素，因为有多的我们就会直接返回结果。

七、字母异位词分组(经典)

. - 力扣（LeetCode）

八、前K个高频单词（经典）

. - 力扣（LeetCode）

解法1：map+vector+稳定排序+lambda优化 map的底层是红黑树，插入的时候map<string,int> 会按照字典序排好，而我们现在要按照出现次序去排序，同时对于出现次数相同的保证字典序在前面，所以我们其中之一的策略就是vector+sort ,但是sort底层是快排，并不具备稳定性，但是库里面有一个stable_sort是稳定的排序

解法2：unordered_map+vector+sort+调整比较逻辑+lambda优化

上面两种解法都是借助vector容器+sort去解决的。

解法3：unordered_map+priority_queue+compare类

解法4：unordered_map+multiset+compare类

解法5：map+multimap+compare类（能过 但这是巧合）

这题能过的原因是map实现了字典序的排序。而底层的multimap封装中对于相同的键值是优先插入到其右侧。