哈希表
哈希表是根据关键码的值而直接进行访问的数据结构。
其实呢，数组就是一张哈希表
其中，关键码就是索引下标
然后通过下标访问数组中的元素
什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。 这
要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。
将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。
哈希函数
哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。
哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
如果hashCode得到的数值大于 哈希表的大小了，也就是大于tableSize了，怎么办呢？
此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。
此时问题又来了，哈希表我们刚刚说过，就是一个数组。
如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。
接下来哈希碰撞登场
哈希碰撞
一般哈希碰撞有两种解决方法， 拉链法和线性探测法。
#拉链法
刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了
（数据规模是dataSize， 哈希表的大小为tableSize）
其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
线性探测法
使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：
常见的三种哈希结构
当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：
std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。
当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。
其他语言例如：java里的HashMap ，TreeMap 都是一样的原理。可以灵活贯通。
虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。
总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
算法题
242.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母。
数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。
需要定义一个多大的数组呢，定一个数组叫做record，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。
定义一个数组叫做record用来上记录字符串s里字符出现的次数。
需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。
再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。
那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。
那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。
最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。
class Solution {
public:
bool isAnagram(string s, string t) {
int resort[26] = {0};
for(int i = 0; i< s.size();i++)
{
resort[s[i]-'a'] = resort[s[i]-'a'] +1;
}
for(int i = 0; i< t.size();i++)
{
resort[t[i]-'a'] = resort[t[i]-'a'] -1;
}
for(int i =0 ; i <26; i++)
{
if(resort[i]!=0)
return false;
}
return true;
}
};
349. 两个数组的交集
力扣题目链接(opens new window)
题意：给定两个数组，编写一个函数来计算它们的交集。
说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
这道题目，主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。
注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序
但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。
而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。
而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：
std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。
把nums1进行处理转化为哈希表放进去，然后用nums2遍历访问哈希表判断是否出现过。出现过的放进另一个集合中。
unordered_set
unordered_set与set非常类似，唯一的区别是set会对存进去的数据进行排序，而unordered_set是乱序排列。
unordered_set有如下三个特性：
不再以键值对的形式存储数据，而是直接存储数据的值。而在关联式容器set中，是以键值对的方式存储的。且set与map又有所不同，set只能存储键与值相同的键值对，例如键为'a'，值为'a'。
容器内部存储的元素的值各不相同，即天然去重。且不能被修改。注意：set也是天然去重。
容器内的元素乱序存在。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set(nums1.begin(),nums1.end());//直接把nums1数组转化为set
for(int num : nums2)//nums2查询
{
if(nums_set.find(num) != nums_set.end())
{
result_set.insert(num);
}
}
return vector<int>(result_set.begin(),result_set.end());
}
};
for(int num : nums2)
其实这个是C++11的新特性，在C++primer第五版中有讲解，特此整理学习！
其实这就是简化的循环写法，善于观察的同学结合上下代码语句，应该猜个大概。
等同于
int num;
for(int i=0;i<nums.length;i++)
{
num=nums2[i];
}
文字解释：从nums2的int型数组中依次将值赋值给num，将num带入for语句代码块中执行。
直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。
总结
1.通式
for(要遍历的数据类型 遍历变量 ： 遍历对象)
注：遍历的数据类型要和遍历的对象元素类型一致
2.范围for循环不能用于循环体中有改变容器大小的操作。举例子：循环体内不能向vector容器添加元素。
不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。
if(nums_set.find(num) != nums_set.end())
这是标准库里迭代器部分的内容，简单点说，就是用find这个函数，去找nums_set这个序列中的num元素，如果序列中所找的这个元素不存在，就会返回end()。
如果nums_set.find(num)返回的不是 nums_set.end()),就说明在str序列中找到i元素：
if(nums_set.find(num) != nums_set.end())找到了
同理，如果nums_set.find(num)返回的是 nums_set.end()),就说明在str序列中没找到i元素：
if(nums_set.find(num) != nums_set.end())没找到
数组求解：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
int hash[1005] = {0}; // 默认数值为0
for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
hash[num] = 1;
}
for (int num : nums2) { // nums2中出现话，result记录
if (hash[num] == 1) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
第202题. 快乐数
力扣题目链接(opens new window)
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
这道题目看上去貌似一道数学问题，其实并不是！
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
判断sum是否重复出现就可以使用unordered_set。
还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。
class Solution {
public:
int getsum(int n)
{
int sum = 0;
while(n)
{
sum += (n%10) * (n%10);
n/=10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(1)
{
int sum = getsum(n);
if(sum == 1)
{
return true;
}
if(set.find(sum) != set.end())//如果在，就是重复了返回false
{
return false;
}else
{
set.insert(sum);//如果不在，放在哈希表中，更新n的值
}
n = sum;
}
}
};
例如输入19
第一次调用getsum(19)
int sum = 0
while(n=19)
{
sum = 0 + (19%10)*(19%10); sum = 81
n=n/10=19/10=1;
}
进入第二次循环
while(n=1)
{
sum = 81 + (1%10)*(1%10)=81+1=82
n=1/10=0;退出循环
}
return sum = 82;
两数之和
力扣题目链接(opens new window)
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
首先我在强调一下 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。
因为本地，我们不仅要知道元素有没有遍历过，还有知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。
再来看一下使用数组和set来做哈希法的局限。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。
这道题目中并不需要key有序，选择std::unordered_map 效率更高！ 使用其他语言的录友注意了解一下自己所用语言的数据结构就行。
接下来需要明确两点：
map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下表，这样才能找到与当前元素相匹配的（也就是相加等于target）
接下来是map中key和value分别表示什么。
这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。
那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。
所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下表}。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map<int,int> map;
for(int i = 0; i< nums.size();i++)
{
auto iter = map.find(target-nums[i]);
if(iter != map.end())
{
return {iter->second,i};
}
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
auto的原理就是根据后面的值，来自己推测前面的类型是什么。
auto的作用就是为了简化变量初始化，如果这个变量有一个很长很长的初始化类型，就可以用auto代替。
注意点：
1.用auto声明的变量必须初始化（auto是根据后面的值来推测这个变量的类型，如果后面没有值，自然会报错）
2.函数和模板参数不能被声明为auto（原因同上）
3.因为auto是一个占位符，并不是一个他自己的类型，因此不能用于类型转换或其他一些操作，如sizeof和typeid
4.定义在一个auto序列的变量必须始终推导成同一类型
示例：
std::vector<std::string> ve;
std::vector<std::string>::iterator it = ve.begin();
我们可以用atuo来代替那个初始化类型：
auto it = ve.begin();
我们在遍历一个元素的，需要判断之前的元素是否遍历过。
遍历过的加到集合中，新遍历 一个的时候判断是不是在集中中出现过，出现过就是我们之前遍历过了。
这个集合中map存放已经遍历过的元素。
