哈希表通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做哈希函数? ?存放记录的? 数组? 叫做? 哈希表。
那么哈希表能解决什么问题呢？
一般哈希表都是用来快速判断一个元素是否出现集合里。
例如要查询一个学生是否在这所学校里。
要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。
例：通过哈希函数把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
哈希冲突
?处理哈希冲突：
1、开放寻址法? ?：一旦产生冲突，就去寻找下一个空的散列地址，只要散列地址足够大，总能找到。
（1）线性探测法：发生冲突，当前位置被占用，向后测一步，看下一步有没有关键字， 沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个空的地址为止。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。
（2）二次探测法：发生冲突时，在表的双向进行跳跃式探测，比较灵活。（增加平方运算的目的是不让关键字聚集在一起）
（3）?随机探测法：冲突时，对于位移量d采用随机函数计算得到。
2、再散列法? ?：事先准备多个散列函数（多种计算方法），产生冲突的时候就换一个计算方式，直到解决冲突。? 这种方法能使关键字不聚集，但是增加了计算时间。
3、拉链法? ?：将所有产生冲突的哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
4、建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
例：
?拉链法：发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了
线性探测法（属于开放地址法）：保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。
常见的哈希结构：
数组、set（集合）、map（映射）。
?题
定义一个数组叫做用来上记录字符串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。
时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
vector<int> table(26, 0);
for (auto& ch: s) {
table[ch - 'a']++;
}
for (auto& ch: t) {
table[ch - 'a']--;
if (table[ch - 'a'] < 0) {
return false;
}
}
return true;
}
};
///
class Solution
{
public:
bool isAnagram(string s, string t) {
vector<int> vs(26,0);
vector<int> vt(vs);
for(auto a:s)
{
vs[a-'a']++;
}
for(auto a:t)
{
vt[a-'a']++;
}
if(vs==vt)
{
return true;
}
return false;
}
};class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1, set2;
for (auto& num : nums1) {
set1.insert(num);
}
for (auto& num : nums2) {
set2.insert(num);
}
return getIntersection(set1, set2);
}
vector<int> getIntersection(unordered_set<int>& set1, unordered_set<int>& set2) {
if (set1.size() > set2.size()) {
return getIntersection(set2, set1);
}
vector<int> intersection;
for (auto& num : set1) {
if (set2.count(num)) {
intersection.push_back(num);
}
}
return intersection;
}
};
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
int length1=nums1.size(),length2=nums2.size();
int index1=0,index2=0;
vector<int> tmp;
while(index1 < length1 && index2 < length2)
{
int num1 = nums1[index1],num2 = nums2[index2];
if(num1==num2)
{
if(!tmp.size() || num1 != tmp.back())
{
tmp.push_back(num1);
}
index2++;
index1++;
}
else if(num1<num2)
{
index1++;
}
else{index2++;}
}
return tmp;
}
};
?