哈希表unordered_map
- 前言
- 哈希表
- unordered_map
-
- 基础unordered_map
- 为什么叫 unordered
- 遍历
- 查找与删除
- 问题呈现
-
- 1.如果有好几个元素都在6桶，那他又是如何找到我需要的那个元素的
- 2.为什么无序的底层逻辑
前言
在学习unordered_map之前，我们最好将哈希表回顾一遍，对哈希表的底层运行深入了解，有利于我们接触unordered_map。 对于哈希表和unordered_map，经过学习后也提出了一些问题，放在结尾，各位也可以看看自己是否有同样的问题。
哈希表
如果现在有100万个对象，而你需要从中找到一个叫王五的人，难道需要从头到尾遍历吗。 由此引申出了哈希表。 哈希函数 他会给每一个成员赋予一个数字，而数字有大有小。 存入：王五 -> 100 哈希函数算出：王五 -> 123456 然后 123456 % 10 于是存到桶6 而桶6就是寻找王五的靶子。
0
1
2
3
4
5
6 -> 王五
7
8
9
这种查找方式会直接将目标瞄准桶6，因而省去遍历。 所以查找速度接近O(1)
unordered_map
基础unordered_map
unordered_map是以键值对（Key-Value）的形式进行存储的，如果与上面的哈希表相连，我们就可以清楚地发现王五便是其中的key可以通过key去找寻相应的value。 可以这样理解。
王五
↓
哈希函数
↓
桶6
↓
找到(王五,95)
↓
返回95
这也就引出了最简单的使用代码
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<string, int> age;
age["张三"] = 18;
age["李四"] = 20;
cout << age["张三"] << endl;
return 0;
}
为什么叫 unordered
如下代码
unordered_map<string, int> age;
age["A"] = 1;
age["B"] = 2;
age["C"] = 3;
for(auto p : age)
{
cout << p.first << " "
<< p.second << endl;
}
输出顺序如何A B C？ 实际上不一定。 可能：
C 3
A 1
B 2
也可能：
B 2
C 3
A 1
遍历
直接使用lambda形式遍历即可
for(auto p : age)
{
cout << p.first
<< " : "
<< p.second
<< endl;
}
其中p.first是 key p.second是 value
查找与删除
对于查找 一定要先用find确认是否存在 如果直接cout << age[“赵六”]; 如果赵六不存在，会自动创建：赵六 -> 0
auto it = age.find("张三");
if(it != age.end())
{
cout << it->second;
}
删除直接age.erase(“张三”);即可
问题呈现
1.如果有好几个元素都在6桶，那他又是如何找到我需要的那个元素的
对于这种情况
桶6
↓
王五 -> 100
↓
张三 -> 90
↓
李四 -> 80
计算机会通过哈希函数直接定位到桶6，而不是从桶0开始找，也不是遍历整个哈希表 桶6里面有： 王五 张三 李四 这时才需要比较： 王五 ❌ 张三 ✅
2.为什么无序的底层逻辑
假设有 10 个桶：
0
1
2
3
4
5
6
7
8
9
插入：
age["A"] = 1;
age["B"] = 2;
age["C"] = 3;
它会先计算哈希值。
例如
A -> 哈希值100
B -> 哈希值56
C -> 哈希值123
然后：
100 % 10 = 0
56 % 10 = 6
123 % 10 = 3
整个哈希表就类似于这种情况
0 : A
1 :
2 :
3 : C
4 :
5 :
6 : B
7 :
8 :
9 :
从桶0开始遍历，自然输出ABC 但哈希值是随机的，这就导致了ABC这三个字母，出现了很多排列方法，自然是无序的。
