哈希表理论基础。
哈希表
哈希表是根据关键码的值而直接进行访问的数据结构。关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。
一般哈希表都是用来快速判断一个元素是否出现集合里。
哈希函数
将元素映射到哈希表上，并得到哈希表上该元素的索引，然后就可以通过索引下标快速访问到该元素。
对得到的索引进行取模操作，确保所有元素都在映射表中。
哈希碰撞
多个元素映射到同一个索引位置
拉链法 和 线性探测法
常见的哈希结构
- 数组
- set 集合
- map 映射
set
| 集合 | 底层实现 | 是否有序？ | 数值可重复？ | 更改数值？ | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
| std::multiset | 红黑树 | 有序 | 是 | 否 | O(logn) | O(logn) |
| std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
map
| 集合 | 底层实现 | 是否有序？ | 数值可重复？ | 更改数值？ | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| 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) |
