哈希表基础知识
哈希表，Hash table，也称为散列表，它是可以根据关键字的值，直接进行查询与访问的数据结构。我们通常通过映射函数将关键字直接对应到表中的某个位置，从而加快查找速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。
一般哈希表可以用来快速判断一个元素是否出现在集合中，一般hashcode就是通过特定的编码方式，将其他数据格式转换为不同的数值。
image.png
hashcode的数值大于哈希表
为了保证通过哈希函数映射出来的索引都落在哈希表上，我们会对数值做一个取模的操作，这样我们就保证了数据一定可以映射到哈希表上了
数据数量大于哈希表
如果数据数量大于哈希表大小，就算哈希函数计算的再均匀也会几个数据映射到哈希表同一个索引的情况下，这种情况就叫做哈希碰撞
image.png
哈希碰撞的两种解决方法
拉链法
image.png
线性探测法
image.png
使用线性探测法，一定要保证tablesized(哈希表大小)大于datasize（数据开发）
常见的三种哈希结构
- 数组
2.映射map
3.集合set
有效的字母异位词
242. 有效的字母异位词 - 力扣（LeetCode）
题目：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
思路：
- 定义一个大小为26的数组，初始化为0，用来记录字符出现的次数,；
- 把26个字母出现的次数映射到数组的下标上；
- 设定的数组中进行字符串遍历， 对前一个数组进行+1操作，对后一个数组进行-1操作，当某一个关键字判断等于0时，就表示有字母相同。
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26]={0};
for(int i=0;i<s.size();i++)
{
record[s[i]-'a']++;
}
for(int i =0;i<t.size();i++)
{
record[t[i]-'a']--;
}
for(int i=0;i<26;i++)
{
if(record[i]!=0)
{
return false;
}
}
return true;
}
};
349.两个数组的交集
解题思路：
使用unordered_set这种哈希数据结构，set可以给结果去重
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> num_set(nums1.begin(),nums1.end());
for(int num:nums2)
{
if(num_set.find(num)!=num_set.end(num))
{
result_set.insert(num);
}
}
return vector<int> (result_set.begin(),result_set.end());
}
};
202.快乐数
202. 快乐数 - 力扣（LeetCode）
思路：
1.获取各个位数的数字
2.设置一个集合
3.判断位数能否等于1，等于1返回true，
4.若是sum出现过，表示陷入了死循环，返回false
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;
}
// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
1.两数之和
1. 两数之和 - 力扣（LeetCode）
思路：
set用在有序且不重合的哈希表中效率更高，map用在无需的哈希表中效率更高。
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++) {
// 遍历当前元素，并在map中寻找是否有匹配的key
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
// 如果没找到匹配对，就把访问过的元素和下标加入到map中
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
