哈希表Hash table

哈希表是根据关键码的值而直接进行访问的数据结构。

数组就是⼀张哈希表。

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断⼀个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话，只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于哈希表的大小了，也就是大于tableSize了，怎么办呢？

此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了，哈希表我们刚刚说过，就是一个数组。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表同⼀个索引下标的位置。

接下来哈希碰撞登场

哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

一般哈希碰撞有两种解决方法，拉链法和线性探测法。

拉链法

刚刚小李和小王在索引 1 的位置发生了冲突，发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了

（数据规模是dataSize，哈希表的大小为tableSize）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，⼀定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找⼀个空位放置小王的信息。所以要求tableSize⼀定要⼤于dataSize，要不然哈希表上就没有空置的位置来存放冲突的数据了。如图所示：

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

1.数组

2.set（集合）

3.map（映射）

这里数组就没啥可说的了，我们来看⼀下set和map。

std::unordered_set底层实现为哈希表，std::set和std::multiset的底层实现是红黑树，红黑树是⼀种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

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也是⼀样的道理。

有效的字母异位词

就是判断 s 和 t 是否是由相同的字符组成

数组其实就是⼀个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串 s 里字符出现的次数。

定义⼀个数组叫做record用来上记录字符串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。

class solution
{
public:bool cmp(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;}
};

两个数组的交集

题意：给定两个数组，编写一个函数来计算它们的交集。

这道题目，主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的，同时可以不考虑输出结果的顺序

思路如图所示：

代码：

# include <iostream>
# include <vector>
# include <unordered_set>
using namespace std;int main()
{vector<int> nums1;vector<int> nums2;int n;int m;cin >> n >> m;int x;for (int i = 0; i < n; ++i){cin >> x;nums1.push_back(x);}for (int i = 0; i < m; ++i){cin >> x;nums2.push_back(x);}unordered_set<int> result;unordered_set<int> nums(nums1.begin(), nums1.end());for (int num : nums2){if (nums.find(num) != nums.end())result.insert(num);}}

快乐数

# include <iostream>
# include <vector>
# include <unordered_set>
using namespace std;int made(int x)
{int sum = 0;while (x > 0){sum = sum + (x % 10) * (x % 10);x = x / 10;}return sum;
}bool cmp(int x)
{unordered_set<int> last;int s = x;while (1){s = made(s);if (last.find(s) == last.end()){if (s == 1)return true;last.insert(s);}else{return false;}}
}int main()
{int n;cin >> n;cout << bool(n);
}

两数之和

首先我在强调一下什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。

那么我们就应该想到使用哈希法了。

因为本地，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看⼀下使用数组和set来做哈希法的局限。

1.数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

2.set是⼀个集合，里面放的元素只能是⼀个key，而两数之和这道题目，不仅要判断y是否存在，而且还要记录y的下标位置，因为要返回x和y的下标。所以set也不能用

此时就要选择另⼀种数据结构：map，map是⼀种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。

这道题目中并不需要key有序，选择std::unordered_map效率更高！

接下来需要明确两点：

        1.map用来做什么

        2.map中key和value分别表示什么

map用来存放我们访问过的元素

数组中的元素作为key，有key对应的就是value，value用来存下标。

# include <iostream>
# include <vector>
# include <unordered_map>
using namespace std;int main()
{int num[100];int n;int target;cin >> n >> target;unordered_map<int, int> map;for (int i = 0; i < n; ++i){cin >> num[i];}for (int i = 0; i < n; ++i){if (map.find(target - num[i]) != map.end()){auto iter = map.find(target - num[i]);cout << i << iter->second;}map.insert(pair<int, int>{ num[i], i });}
}

四数相加II

例如:

输⼊:

A = [1,  2]

B = [ -2, -1]

C = [-1, 2]

D = [ 0, 2]

输出:

2

本题是使用哈希法的经典题目，这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况。

# include <iostream>
# include <vector>
# include <unordered_map>
using namespace std;int main()
{int n;cin >> n;int a[500];int b[500];int c[500];int d[500];for (int i = 0; i < n; ++i){cin >> a[i];}for (int i = 0; i < n; ++i){cin >> b[i];}for (int i = 0; i < n; ++i){cin >> c[i];}for (int i = 0; i < n; ++i){cin >> d[i];}unordered_map<int, int>map;for (int i : a){for (int j : b){map[i + j]++;}}int count = 0;for (int i : c){for (int j : d){if (map.find(0 - i - j) != map.end())count = count + map[0 - i - j];}}cout << count;
}