1. 哈希表是什么
哈希表（Hash table），也称散列表，是根据关键码的值而直接进行访问的数据结构。
C++名字unordered_map或unordered_set，Set与Map一个是只有Value，另一个带Key。(Map,键值对)
哈希表的增删改查的时间复杂度都是常数级，使用时特别高效。时间复杂度为o(1)，空间复杂度为o(n)。
2. 哈希函数
就是根据哈希key按照一定逻辑求出哈希value。
3. 哈希碰撞
多个value绑定到了同一个哈希key下面,当访问的时候，得到的vlaue不唯一。
4. 哈希冲突的解决方法
开放定址法
- 线性探测法
- 二次探测法
- 随机探测法
- 再散列函数法
事先准备多个散列函数 - 公共溢出区法
建立两张表，一张为基本表，另一张为溢出表。 - 链地址法（拉链法）
冲突的数据全部存储在同一个线性链表中。
5.常见的三种哈希结构
1.数组
2.set （集合）
| 集合 | 底层实现 | 是否有序 | 数值能否重复 | 数值能否更改 | 增删改查效率 |
|---|---|---|---|---|---|
| std::set | 红黑树 | 有序 | 否 | 否 | O(logn) |
| std::multiset | 红黑树 | 有序 | 是 | 否 | O(logn) |
| std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) |
3.map（映射）
| 映射 | 底层实现 | 是否有序 | key能否重复 | key能否更改 | 增删改查效率 |
|---|---|---|---|---|---|
| std::map | 红黑树 | 有序 | 否 | 否 | O(logn) |
| std::multimap | 红黑树 | 有序 | 是 | 否 | O(logn) |
| std::unordered_map | 哈希表 | 无序 | 否 | 否 | O(1) |
6.添加数据
std::unordered_map<std::string,std::vector<std::string>> unrdered_strings;
std::string MyStr("123");
std::string TheStr("I LOVE YOU !");
unrdered_strings[MyStr].emplace_back(TheStr);