哈希表和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(); }