哈希表理论知识
C++常见的三种哈希结构
- 数组
- set（集合）
- map（映射）
在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：
| 集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
| std::multiset | 红黑树 | 有序 | 是 | 否 | O(logn) | O(logn) |
| std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
| 映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(logn) | O(logn) |
| std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。
当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。
虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。
LC242. 有效的字母异位词
128个ASCII字符，一般定义数组的大小都会大出一点点
bool isAnagram(string s, string t)
{
int i = 0;
int s_size = s.size();
int map[130] = {0,};
if (s_size != t.size())
{
return false;
}
for (; i < s_size; i++)
{
map[s[i]]++;
}
for (i = 0; i < s_size; i++)
{
map[t[i]]--;
}
for (; i< 130; i++)
{
if (map[i] != 0)
{
return false;
}
}
return true;
}
LC349. 两个数组的交集
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
unordered_set<int> set(nums1.begin(), nums1.end());
unordered_set<int> result;
for (auto i : nums2)
{
// if (set.count(i) != 0)
if (count(nums1.begin(), nums1.end(), i) != 0)
{
result.insert(i);
}
}
return vector<int>(result.begin(), result.end());
}
LC202. 快乐数
对于一个数，他的“快乐”运算，只会有两种结果：
- 最终会得到 1
- 最终会进入循环（回到原来输入的数 ）
int happy(int n)
{
int result = 0;
while (n)
{
result += (n % 10) * (n % 10);
n /= 10;
}
return result;
}
bool isHappy(int n)
{
unordered_set<int> set;
int temp = n;
while (1)
{
temp = happy(temp);
if (1 == temp)
{
return true;
}
else
{
if (set.find(temp) != set.end())
{
return false;
}
set.insert(temp);
}
}
return false;
}
LC1. 两数之和
本题有四个重点：
- 为什么会想到用哈希表
- 哈希表为什么用map
- 本题map是用来存什么的
- map中的key和value用来存什么的
自己写的版本，想法是通过map的key记录出现过的nums[i]值，而value用来记录某个key出现的次数。本题其实没有用到value记录的key出现次数，所以最好是用value某个key在nums的索引下标，这样若找到匹配后，无需再从头遍历一次nums重新找索引下标。
////自己写的版本
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> map;
vector<int> vec;
for (int index = 0; index < nums.size(); index++)
{
if (map.find(target - nums[index]) != map.end())
{
////从头遍历nums找到匹配的索引下标
for (int j = 0; j < index; j++)
{
if (target - nums[index] == nums[j])
{
vec.push_back(j);
vec.push_back(index);
goto OUT;
}
}
}
////记录每个数字出现的次数
if (map.find(nums[index]) == map.end())
{
map[nums[index]] = 1;
}
else
{
map[nums[index]]++;
}
}
OUT:
return vec;
}
官方写法：
vector<int> twoSum(vector<int>& nums, int target)
{
int i;
unordered_map<int, int> umap;
for(i = 0; i < nums.size(); i++)
{
auto it = umap.find(target - nums[i]);
if(it != umap.end())
{
return {it->second, i};
}
umap[ nums[i] ] = i; //通过目标键值对的键获取到该键对应的值
}
return {}; //未有匹配，返回空vector
}