常见的三种哈希结构（数组，set，map）
哈希算法的使用场景：
当需要在数组中快速找某元素是否存在时，应当立刻想到哈希，这也是面试中常见的题
三种常见的哈希结构：
1.数组
2.set
3.map
使用环境：
1.当元素个数较少并且能知道大概元素个数时，使用数组
2.当元素数量较大时，使用set
3.当一个数据涉及两种因素时(即key和value)，使用map
到这里你可能还是比较懵，我就用三个题目来让你理解吧
加重理解：
1.数组
1.题目链接：1. 两数之和 - 力扣（LeetCode）
题解:
242. 有效的字母异位词(力扣)（C语言题解）-CSDN博客
该题为什么想到哈希：涉及到快速查找数组中是否出现某元素（在nums2中找是否有nums1中的字母）
为什么用数组： 字母最多只有26个，数量较少，且大小确定
2.set
2.题目链接：349. 两个数组的交集 - 力扣（LeetCode）
C语言题解：[349. 两个数组的交集]（C语言）（两种解法：双指针+排序，哈希）-CSDN博客
C++题解： [349. 两个数组的交集]（C++）（第三种解法：set）-CSDN博客
该题为什么想到哈希：涉及到快速查找数组中是否出现某元素（找nums2中的数字是否在nums1中出现过）
为什么用数组： 现在力扣的数据改了，说明了数组中最大的数也只是1000，因为元素大小确定，且数量较小，所以可以用数组
为什么用set：之前的数据没有改变，所以最大的数并不确定，很可能是一个超级大的数，但是可能元素很少，只有几个，用数组会造成内存的大量浪费，所以最好用set
3.map
3.题目链接：两数之和 - 力扣（LeetCode）
C++题解： 1. 两数之和(C++)(map)(哈希算法）-CSDN博客
该题为什么想到哈希：涉及到快速查找数组中是否出现某元素（找target-numsi是否在nums1中出现过）
为什么用map： 它涉及了找target-numsi的结果是否也在nums中出现过（key),也涉及了返回下标（value）
好的，现在就介绍介绍这三种
讲解：
1.数组：
数组就不用过多讲了
2.set:
集合 | 底层逻辑 | 是否有序 | 是否可更改 | 数值是否可重复 | 查改速率 | 增删速率 |
|---|---|---|---|---|---|---|
std::set | 红黑树 | 是 | 否 | 否 | O(logn) | O(logn) |
std::multiset | 红黑树 | 是 | 否 | 是 | O(logn) | O(logn) |
std::unordered_set | 哈希表 | 否 | 否 | 否 | O(1) | O(1) |
三种的使用场景：
std::set:
要求集合有序
std::multiset:
要求集合有序 且 有重复数据的时候用
std::unordered_set:
优先考虑这个，因为他的增删和查找效率最高
3.map:
集合 | 底层逻辑 | 是否有序 | 是否可更改 | 数值是否可重复 | 查改速率 | 增删速率 |
|---|---|---|---|---|---|---|
std::map | 红黑树 | 是 | 否 | 否 | O(logn) | O(logn) |
std::multimap | 红黑树 | 是 | 否 | 是 | O(logn) | O(logn) |
std::unordered_map | 哈希表 | 否 | 否 | 否 | O(1) | O(1) |
三种的使用场景：
std::map:
key有序
std::multimap:
key有序 且 有重复数据的时候
std::unordered_map:
优先考虑这个，因为他的增删和查找效率最高
完结撒花，恭喜你又进步了呀~