哈希表

哈希表（Hash table ，也被称为散列表）是根据关键码而直接进行访问的数据结构

一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称之为 <Key, value> 的键值对

哈希表可以近似理解成数组，哈希表中的关键码就是数组的索引下标，通过下标可以直接访问数组的元素

一般哈希表都是用来快速判断一个元素是否出现集合当中

哈希表 以空间换时间 ，因为需要额外的 数组 、 set 或 map 来存放数据，才能实现快速查找

# 哈希函数

哈希函数（hash function）将关键码映射为哈希表的索引

构造哈希函数的要求：

定义域必须包含全部需要存储的关键码，而值域的范围则依赖于散列表的大小或地址范围。
函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生
函数应尽量简单，能够在较短的时间内计算出任一关键码对应的散列地址

常用的哈希函数

直接地址法
- 直接将关键码值作为地址 H(key) = key 或做一个简单的线性映射 H(key) = a × key + b
除留取余法
- 最常用的一种哈希函数
- 保证函数值是一个合法的下标
- H(key) = key MOD p ，其中 p 是数组的大小， p 最好为质数，这样可以使得函数值分布更均匀
数字分析法
- 适用于关键码值范围比较大的情况（并非每一位都有区分意义）
- 对所有关键码，分析每一位上的数字分布。取数字分布均匀的位作为地址的组成部分
平方取中法
- 适用于关键码中各位的分布都比较均匀，但关键码的值域比数组规模大（每一位都有区分意义）
- 将关键码平方后，取其结果的中间各位作为散列函数值
- 由于中间各位和每一位数字都有关系，因此均匀分布的可能性较大
- 中间部分究竟要选取几位，依赖于哈希表的单元总数
折叠法
- 如果关键字相当长，以至于和哈希表的单元总数相比大得多时，可采用此法
- 选取一个长度后，将关键码按此长度分组相加

# 哈希碰撞

哈希碰撞是指：不同的关键码映射到同一个地址

也称之为冲突

两类解决方案：

闭散列表：利用当前散列表中的空余单元
- 线性探测法：H_i = (H_i-1 + 1) mod size
  - H_i-1 是最近计算到的探测点（ H₀ 是原始的散列位置），H_i 是要计算的新的探测点
- 二次探测法：H_i = (H₀ + i²) mod size
- 再次散列法：H_i = (H₀ + i * hash²(x)) mod size
开散列表：将散列到同一地址的节点组织成一个单链表，存储散列表的数组中保存的是每个单链表的起始地址

CodeSheep：哈希表详解

理想情况下，哈希查找的时间复杂度是 $O(1)$

# 常见的哈希结构

三种哈希结构

数组
set （集合）
map （映射）

set 只存储 key ，而 map 存储了 <key, value> 的键值对

# 集合 set

在 set 中，元素的 key 就是它的 value

键值对 <key, value> ：用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value ， key 代表键值， value 表示与 key 对应的信息

在 set 中，不能修改元素的值，但是可以从容器中插入或删除

C++ 的 set 实现：

std::set ：底层实现为红黑树， key 是有序的
std::multiset ：底层实现是红黑树， key 有序
std::unordered_set ：底层实现是哈希表， key 无序

set	底层实现	`key` 是否有序	`key` 是否可以重复	能否更改 `key`	查询效率	增删效率
`std::set`	红黑树	有序	否	否	$O(\log {n})$	$O(\log {n})$
`std::multiset`	红黑树	有序	是	否	$O(\log{n})$	$O(\log{n})$
`std::unordered_set`	哈希表	无序	否	否	$O(1)$	$O(1)$

红黑树 是一种平衡二叉搜索树，所以 key 是有序的，但 key 不可以修改，改动 key 会导致整棵树的错乱，所以只能删除和增加

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

虽然 std::set 、 std::multiset 的底层实现是红黑树，不是哈希表，但是 std::set 、 std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法（map 也是同样的道理）

代码随想录：哈希表理论基础

# `std::set`

所有的元素都会被自动排序，不允许出现键值 key 重复

总是按照其内部比较对象（类型比较）所指示的特定严格弱排序准则进行排序

set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但 set 容器允许根据顺序对子集进行直接迭代

头文件： #include <set>

cplusplus：std::set

# `std::multiset`

所有的元素都会被自动排序，允许键值重复

multiset 底层存储的是 <value, value> 的键值对

multiset 容器通过 key 访问单个元素的速度通常 unordered_multiset 容器慢，但当使用迭代器遍历时会得到一个有序序列

头文件： #include <set>

multiset 的接口与 set 接口基本一致

cplusplus：std::multiset

# `std::unordered_set`

元素不会被自动排序，不允许出现键值重复

头文件： #include <unordered_set>

cplusplus：std::unordered_set

# 映射 map

map 容器按照特定的次序（按照 key 来比较）存储由键值 key 和值 value 组合而成的元素

在 map 中，键值 key 通常用于排序和标识元素，而值 value 中存储与此键值 key 关联的内容

键值 key 和值 value 的类型可能不同，并且在 map 的内部， key 与 value 通过成员类型 value_type 绑定在一起

在 map 中，不允许修改 key ，但可以修改 key 对应的 value

C++ 的 map 实现：

std::map ：底层实现是红黑树， key 有序
std::multimap ：底层实现是红黑树， key 有序
std::unordered_map ：底层实现为哈希表， key 无序

map	底层实现	`key` 是否有序	`key` 是否可以重复	能否更改 `key`	查询效率	增删效率
`std::map`	红黑树	有序	否	否	$O(\log {n})$	$O(\log {n})$
`std::multimap`	红黑树	有序	是	否	$O(\log {n})$	$O(\log {n})$
`std::unordered_map`	哈希表	无序	否	否	$O(1)$	$O(1)$

另， hash_set 、 hash_map 和 unordered_set 、 unordered_map 功能一致，区别在于是否被引入标准库

unordered_set 和 unordered_map 被引入了 C++ 11 标准库
hash_set 和 hash_map 并未被引入 C++ 11 标准库

代码随想录：哈希表理论基础

# `std::map`

map 中的元素总是按照键值 key 进行自动排序， key 不可重复

map 通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行直接迭代（即对 map 中的元素进行迭代时，可以得到一个有序的序列）

map 支持下标访问符，即， map[key] 可以找到与 key 对应的 value

头文件： #include <map>

cplusplus：std::map

# `std::multimap`

元素会被自动排序，键值 key 可以重复

multimap 不支持下标访问符

multimap 的接口与 map 类似

cplusplus：std::multimap

头文件： #include <map>

# `std::unordered_map`

元素不被自动排序，键值 key 不可以重复

支持下标访问符

头文件： #include <unordered_map>

cplusplus：std::unordered_map

# 总结

数组是简单的哈希表

数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制
如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组会造成空间的极大浪费

当哈希值分布较为集中时，可以直接采用数组实现哈希法，例如：

LeetCode 242. 有效的字母异位词
LeetCode 383. 赎金信

而当哈希值比较少、特别分散、跨度非常大的时候，则考虑用 set 实现哈希法，例如：

LeetCode 349. 两个数组的交集
LeetCode 202. 快乐数

与集合 set 中每个元素只能是一个 key 相比， map 还可以存放与 key 对应的 value ，因此不仅可以用来保存元素值，还可以保存元素值的下标，例如：

LeetCode 1. 两数之和
LeetCode 454. 四数相加 II

虽然 map 可以适用所有哈希法的场景，但 map 要维护红黑树或者符号表，还要做哈希函数的运算，相比之下，在某些场景下采用数组或 set 会效率更高，因此，需要根据实际需要来选择数组或 set 或 map

另外，关于 set 和 map 的具体实现：

std::set 和 std::multiset 的底层实现是红黑树，而 std::unordered_set 的底层实现是哈希表
std::map 和 std::multimap 的底层实现是红黑树，而 std::unordered_map 的底层实现是哈希表
基于红黑树实现的， key 是有序的，而基于哈希表的， key 是无序的
只有 std::multiset 和 std::multimap 允许 key 重复，其余的都不允许
在同样满足需求的情况下， std::unordered_set 是效率最高的 set ；类似的，在同样满足需求的情况下， std::unordered_map 是效率最高的 map

参考：代码随想录：哈希表总结

哈希表

# 哈希函数

# 哈希碰撞

# 常见的哈希结构

# 集合 set

# std::set

# std::multiset

# std::unordered_set

# 映射 map

# std::map

# std::multimap

# std::unordered_map