哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。

原理

我们先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。因此，查询操作就是找到 key​ 对应的桶，并在桶中获取 value 。

那么，如何基于 key​ 定位对应的桶呢？这是通过哈希函数（hash function）实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key​ ，输出空间是所有桶（数组索引）。换句话说，输入一个 key​ ，我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。

输入一个 key ，哈希函数的计算过程分为以下两步。

1. 通过某种哈希算法 hash() 计算得到哈希值。
2. 将哈希值对桶数量（数组长度）capacity​ 取模，从而获取该 key​ 对应的数组索引 index 。

index = hash(key) % capacity

随后，我们就可以利用 index​ 在哈希表中访问对应的桶，从而获取 value 。

设数组长度 capacity = 100​、哈希算法 hash(key) = key​ ，易得哈希函数为 key % 100​ 。图 6-2 以 key​ 学号和 value 姓名为例，展示了哈希函数的工作原理。

key（学号）        hash(key) = key % 100        value（姓名）
─────────────────────────────────────────────────────────
  1001     ->        1001 % 100 = 1        ->  桶 1  :  { 1001: "张三" }
  1002     ->        1002 % 100 = 2        ->  桶 2  :  { 1002: "李四" }
  1003     ->        1003 % 100 = 3        ->  桶 3  :  { 1003: "王五" }
  1005     ->        1005 % 100 = 5        ->  桶 5  :  { 1005: "赵六" }

  查找 1003：1003 % 100 = 3  ->  直接定位到桶 3  ->  O(1)

取模把无限的 key 空间映射到 0~99 这 100 个桶上，不同的 key 只要余数相同就会落进同一个桶。

Hash冲突

从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。

哈希表的结构改良方法主要包括“链式地址”和“开放寻址”，已经理解了不细写。

具体见：https://www.hello-algo.com/chapter_hashing/hash_collision/

C++的HashMap

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set （集合）
• map(映射)

这里数组就没啥可说的了，我们来看一下set。

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。map同理

常用操作

/* 初始化哈希表 */
unordered_map<int, string> map;

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map[12836] = "小哈";
map[15937] = "小啰";
map[16750] = "小算";
map[13276] = "小法";
map[10583] = "小鸭";

/* 查询操作 */
// 向哈希表中输入键 key ，得到值 value
string name = map[15937];

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.erase(10583);

‍