哈希表基础
哈希表
哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。
哈希表是根据关键码的值而直接进行访问的数据结构。
一般哈希表都是用来快速判断一个元素是否出现集合里。
哈希函数
例如要查询一个名字是否在这所学校里。
哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。
哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
如果hashCode得到的数值大于 哈希表的大小了，也就是大于tableSize了，此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上了。
如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。
接下来哈希碰撞登场
#哈希碰撞
如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。
一般哈希碰撞有两种解决方法， 拉链法和线性探测法。
拉链法将发生冲突的元素存储在链表中。
线性探测法，一定要保证tableSize大于dataSize。 不断增加索引，向冲突位置后寻找空位。
常见的三种哈希结构
当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
- 数组
set（集合）map(映射)
set
在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：
map
242.有效的字母异位词
题目链接：242.有效的字母异位词
文档讲解：代码随想录
状态：轻松AC
思路
从题目信息提炼要求，字母异位词：字母种类且各个个数均相同
字母种类固定（26个），且每个字母与下表可以产生联系，故选用数组
题解
class Solution {
public:
bool isAnagram(string s, string t) {
int arry1[26] = {0};
int arry2[26] = {0};
for(auto i:s)arry1[i-'a']++;
for(auto i:t)arry2[i-'a']++;
for(int i = 0;i<26;i++)
{
if(arry1[i]!=arry2[i])return false;
}
return true;
}
};
349. 两个数组的交集
题目链接：349. 两个数组的交集
文档讲解：代码随想录
状态：轻松AC
思路
关键点在于去重，用set不解释
本题学到了一种容器转化方式
vector<int>(result.begin(),result.end())；//set->vector
unordered_set<int> uset1(nums1.begin(),nums1.end());//vector->set
题解
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> uset1(nums1.begin(),nums1.end());
unordered_set<int> result;
for(auto i:nums2)
if(uset1.find(i)!=uset1.end())result.insert(i);
return vector<int>(result.begin(),result.end());
}
};
202题.快乐数
思路
理解本题的本质，若进入循环，且不为1，则一定无解死循环
本题最后一定死循环，若为1有解，非1无解
快慢指针思想也可解决，本题一定有环，则快慢指针一定在环中相遇，仅需判断是否为1
题解
class Solution {
public:
int get_sum(int &n){
int sum = 0;
while(n!=0)
{
int temp = n%10;
sum += temp*temp;
n /= 10;
}
n = sum;
return sum;
}
bool isHappy(int n) {
//哈希表思想
// int sum = 0, temp = 0;
// unordered_set<int> uset;
// while(true)
// {
// sum = get_sum(n);
// if(uset.find(1) != uset.end())return true;
// else if(uset.find(sum) != uset.end())return false;
// else uset.insert(sum);
// }
//循环思想
int slow = 0,fast = 0, n2 = n;
while(true)
{
slow = get_sum(n);
int temp = get_sum(n2);
fast = get_sum(n2);
if(slow == fast && slow == 1)return true;
else if(slow == fast)return false;
}
}
};
1.两数之和
思路
思考过程：一层for循环逐个遍历数组（假设为i），若想达到目标，要找到target-i,并且找到target-i的下标.
当然可以暴力，O(n^2)
可以设置一个集合（哈希表是根据关键码的值而直接进行访问的数据结构），若target-i可以被find（且不为自身），则成功
先别着急，题目是让返回下标呀，下标与值要联系起来，妥妥的map没跑了
题解
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> umap;
vector<int> result;
for(int i = 0;i<nums.size();i++)umap[nums[i]] = i;
for(int i = 0;i<nums.size();i++)
{
if(umap.find(target-nums[i])!=umap.end()&& i!=umap[target-nums[i]])
{
result.push_back(i);
result.push_back(umap[target-nums[i]]);
return result;
}
}
return result;
}
};