1. 哈希表是什么

哈希表(Hash table),也称散列表,是根据关键码的值而直接进行访问的数据结构。
C++名字unordered_mapunordered_setSetMap一个是只有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);