哈希表和STL —— unorderde_set/unordered_map【复习笔记】

1. 哈希表的相关概念

1.1 哈希表的定义

哈希表，又称为散列表，是根据关键字直接进行访问的数据结构。

它通过一个哈希函数（Hash Function），建立了一种关键字和存储地址间的直接映射关系，将每个关键字映射到一个固定大小的数组中的一个位置，这个位置被称为哈希地址或索引。理想情况下，散列表的查找的时间复杂度为O(1)，和表中元素数量无关

1.2 哈希冲突

1.2.1 哈希冲突的定义

哈希表可能把两个或两个以上的不同关键字映射到同一个地址，这种情况就叫哈希冲突，也加散列冲突，起冲突的不同关键字，称为同义词

1.2.2 处理哈希冲突的方法

1. 线性探测法

从冲突位置开始，依次线性向后探测，直到找到下一个没有存储数据的位置（如果走到哈希表尾，则返回哈希表头）

2. 链地址法

所有元素不直接存储到哈希表中，哈希表存储指针，每数据时指针为空，当有多个关键字映射到同一个位置，将这些数据串成链表，挂在该位置下面

1.3 哈希函数

1.3.1 哈希函数的定义

将关键字映射成对应地址的函数就是哈希函数，也叫散列函数，记为 Hash（key）= Addr 

1.3.2 常见的哈希函数

1. 直接定址法

直接取关键字的某个线性函数值作为散列地址，散列函数是 Hash（key）= a * key + b（a和b为常数）

2. 除留余数法

假设哈希表的大小为 M ，通过 key 除以 M 的余数作为映射位置的下标，散列函数是 Hash（key）= key % M

注意：

1. M 取不太接近 2 的整数次幂的一个质数。（ 一般来讲，将关键字范围扩大 2 倍，取大于这个范围的质数即可）

2. key 有可能为负数，取模之后也会有负数。负数补正加上模数即可，但这样的活正数和负数的操作就不同一，为了方便，同一为 模加模：

无论key是正数还是负数：（ key % N + N ）% N

3. 其他方法

数学分析法、平方取中法、折叠法、随机数法......这些方法相对局限

2. 哈希表的具体实现

案例：维护一个数据结构，初始为空，有以下操作：

           1 x：插入元素 x

           2 x：查询元素是否在数据结构中

输入描述：第一行一个整数 n ，表示操作次数 （假设插入操作次数小于10次）

                  之后 n 行，第 i 行两个整数 op、x，表示第 op 个操作和元素 x

2.1 除留取余法（哈希函数） + 线性探测法（处理哈希冲突）

#include<iostream>
#include<cstring>
using namespace std;
//根据题目的插入操作次数的范围，找到一个合适的模数创建哈希表
//范围扩大两倍，N 是质数
const int N = 23;
int h[N];//将哈希表的所有元素初始化为一个不会取到的值
//如果初始化为0或其他数，那可能无法辨别该数是初始数还是放入的数
//一般这个取不到的值为0x3f3f3f3f
const int INF = 0x3f3f3f3f;
void Init()
{memset(h, 0x3f, sizeof(h));
}//哈希函数返回映射位置
int h_f(int x)
{//模加模int id = (x % N + N) % N;//线性探测法处理哈希冲突while (h[id] != INF && h[id] != x){id++;if (id == N) id = 0;}return id;
}//插入元素
void insert(int x)
{int id = h_f(x);h[id] = x;
}//查找元素
bool find(int x)
{int id = h_f(x);return h[id] == x;
}
int main()
{Init();int n; cin >> n;while (n--){int op, x; cin >> op >> x;if (op == 1){insert(x);}else{if (find(x))cout << "yes" << endl;else cout << "no" << endl;}}return 0;
}

2.2 除留取余法（哈希函数） + 链地址法（处理哈希冲突）

该实现方法和（用数组实现树的遍历存储）中的链式前向星方法一样，本质是数组模拟链表

#include<iostream>
using namespace std;
#include<cstring>
//根据题目的插入操作次数的范围，找到一个合适的模数创建哈希表
//范围扩大两倍，N 是质数
const int N = 23;
int h[N];//数组模拟链表
int e[N], ne[N],id;//除留取余法
int f(int x)
{return (x % N + N) % N;
}//查找元素
bool find(int x)
{//得到 x 对应的哈希值int idx = f(x);//遍历链表for (int i = h[idx]; i; i = ne[i]){if (e[i] == x) return true;}return false;
}//插入元素
void insert(int x)
{//先判断该元素是否存在if (find(x)) return;int idx = f(x);//头插id++;e[id] = x;ne[id] = h[idx];h[idx] = id;
}int main()
{int n; cin >> n;while (n--){int op, x; cin >> op >> x;if (op == 1){insert(x);}else{if (find(x)) cout << "yes" << endl;else cout << "no" << endl;}}return 0;
}

3. unordered_set/unordered_multiset

unordered_set 和 set(红黑树和STL——set/map）的区别是，前者使用哈希表实现，而后者使用红黑树实现。导致的结果就是存储和查找的速率不一样，以及前者无序，后者有序，其他的使用方式完全一样。

而unordered_set 和 unordered_multiset 的区别：unordered_set 不能存相同的元素而unordered_multiset 可以存相同元素

#include<iostream>
#include<unordered_set>
using namespace std;int main()
{int arr[] = { 3,5,6,8,9,2,10,1 };unordered_set<int> mp;//begin/end:迭代器，可以用范围for遍历哈希表//和红黑树实现的 set 不同，遍历出来的结果是无序的for (auto& e : arr){//insert:插入，时间复杂度近似为O(1)mp.insert(e);}//find:查找一个元素，返回迭代器//count:查询一个元素出现的次数，一般用来判断该元素是否在哈希表中//时间复杂度都近似为O(1)if (mp.count(3)) cout << "yes" << endl;else cout << "no" << endl;//erase:删除元素，时间复杂度近似为O(1)mp.erase(3);if (mp.count(3)) cout << "yes" << endl;else cout << "no" << endl;//size:返回哈希表中元素个数，时间复杂度O(1)cout << mp.size() << endl;//empty:判断哈希表是否为空，时间复杂度O(1)if (mp.empty()) cout << "空" << endl;else cout << "非空" << endl;return 0;
}

4. unordered_map/unordered_multimap 

unordered_map 和 map（红黑树和STL——set和map）的区别是，前者使用哈希表实现，而后者使用红黑树实现。导致的结果就是存储和查找的速率不一样，以及前者无序，后者有序，其他的使用方式完全一样。

而unordered_map 和 unordered_multimap 的区别：unordered_map 不能存相同的元素而unordered_multimap 可以存相同元素

还有一点，无论是 map 还是 unordered_map 都可以存图，但 map 的查找速率较低，而 unordered_map 的查找速率较高

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;void test()
{unordered_map<int, vector<int>> mp;mp[1].push_back(2);mp[2] = { 3, 4, 5 };mp[3].push_back(1);mp[3].push_back(2);for (auto& p : mp){cout << p.first << ":";for (auto& b : mp[p.first]) cout << b << " ";cout << endl;}
}int main()
{unordered_map<string, int> mp;//insert:插入元素，时间复杂度近似O(1)//用{}将元素括起来mp.insert({ "lili",1 });mp.insert({ "kiki",2 });mp.insert({ "vivi",3 });//c++17的结构化绑定for (auto& [k,v] : mp){cout << k << "编号：" << v << endl;}//operator[]:重载[],让unordered_map可以像数组一样使用//但operator[]可能会向 map 插入意料外的元素//插入时，第一个关键字为[]里内容，第二个关键字为默认值//会把<"hihi",0>放入if (mp["hihi"] == 4) cout << "hihi=4" << endl;else cout << "no" << endl;//begin/end:迭代器，用范围for遍历for (auto& [k, v] : mp){cout << k << "编号：" << v << endl;}//erase:删除，时间复杂度近似O(1)mp.erase("hihi");//find:查找元素，返回迭代器//count：查询元素出现次数，一般用来判断元素是否在哈希表中//时间复杂度都近似O(1)if(mp.count("lili")) cout << "yes" << endl;else cout << "no" << endl;//size:求哈希表元素个数//empty:判断哈希表是否为空//时间复杂度都近似O(1)cout << mp.size() << endl;if (mp.empty()) cout << "空" << endl;else cout << "非空" << endl;//存图test();
}