哈希法学习
文章目录
-
一、哈希表（Hash table）
-
二、哈希函数与哈希碰撞
-
- 1、拉链法
- 2、线性探测法
-
三、哈希法编程实现
-
-
1、数组
-
2、std::unordered_set（集合）
-
- （1）增删查
- (2) std::unordered_set和vector的相互初始化
-
3、std::unordered_map（映射）
-
- （1）找出两数之和
- (2)四数之加
-
一、哈希表（Hash table）
哈希表是根据关键码的值 而直接进行访问的数据结构。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：
一般来说哈希表都是用来判断一个元素是否出现在集合里。
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组、set或者是map来存放数据，才能实现快速的查找。
如果遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！
二、哈希函数与哈希碰撞
哈希函数是把传入的key映射到符号表的索引上。
把学生的姓名直接通过哈希函数映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。
哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashCode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
如果几个学生的名字在哈希函数下同时映射到哈希表同一个索引下标的位置，即发生了哈希碰撞，如下图所示。
哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。
1、拉链法
数据规模是dataSize， 哈希表的大小为tableSize，如果dataSize > tableSize，即可使用拉链法。
使用拉链法时要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
2、线性探测法
使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：
三、哈希法编程实现
1、数组
数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
2、std::unordered_set（集合）
不需要对数据进行排序，而且还不要让数据重复，可以选择set
set是一个集合，里面放的元素只能是一个key
（1）增删查
unordered_set可以把它想象成一个集合，它提供了几个函数让我们可以增删查：
unordered_set::insert(x);
unordered_set::find(x);
unordered_set::erase(x);(2) std::unordered_set和vector的相互初始化
vector<int> nums1;
std::unordered_set<int> num2(nums1.begin(),nums1.begin());
vector<int> nums3(num2.begin(),num2.end());可以利用迭代器进行互相转化。
3、std::unordered_map（映射）
- map是一种<key, value>的结构，用key保存数值，用value保存数值所在的下标。
1. 两数之和
（1）找出两数之和
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int,int> map; //初始化一个空map
for(int i = 0; i < nums.size(); i++) {
auto iter = map.find(target - nums[i]); //map.find返回迭代器，使用auto定义数据类型
if(iter != map.end()) {
return {iter->second, i}; //iter->first返回key,iter->second返回value
}
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};(2)四数之加
解法一：编程较简介
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> umap;
for(int a : nums1){
for(int b : nums2){
umap[a+b]++;
}
}
int count = 0;
for(int c : nums3){
for(int d : nums4){
if(umap.find(-c-d) != umap.end()){
count += umap[-c-d];
}
}
}
return count;
}
};解法二：内存和用时较少
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
sort(nums3.begin(), nums3.end());
sort(nums4.begin(), nums4.end());
std::unordered_map<int, int> map;
for(int i = 0; i < nums1.size(); i++){
int a = 1;
while(i+1 < nums1.size() && nums1[i+1] == nums1[i]){
a++;
i++;
}
for(int j = 0; j < nums2.size(); j++){
int b = 1;
while(j+1 < nums2.size() && nums2[j+1] == nums2[j]){
b++;
j++;
}
auto iter = map.find(nums1[i]+nums2[j]);
if(iter == map.end()){
map.insert(pair<int, int>(nums1[i]+nums2[j], a*b));
}
else{
iter->second += a*b;
}
}
}
int count = 0;
for(int k = 0; k < nums3.size(); k++){
for(int l = 0; l < nums4.size(); l++){
auto iter = map.find(0-nums3[k]-nums4[l]);
if(iter != map.end()){
count += iter->second;
while(l+1 < nums4.size() && nums4[l+1] == nums4[l]){
count += iter->second;;
l++;
}
}
}
}
return count;
}
};