行业知识
哈希表C++哈希表详解（知识点+相关LeetCode题目）
���录
（）前言
一、什么是哈希表
（）二、哈希表的操作
2.1 操作时间复杂度
2.2 哈希表通用API
2.3 建立哈希表
2.3 哈希表常见结构介绍
Set（集合）
Map（映射）
unordered_map（哈希表）
三、哈希表的力扣经典题目
有效的字母异位词242
两个数组的交集 349
两数之和1
四数相加II 454
三数之和 15
四数之和 18
前言
本文将从哈希表的概念、复杂度、STL实现函数、哈希表相关经典题目展开叙述。
一、什么是哈希表
哈希表是散列表，就是通过关键码值而直接进行访问的一种数据结构
哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素
其内部由一个个key：value 样式的键值对组成。
哈希表中的key通过哈希函数得到内存地址，然后将key和value放到对应的内存地址，从而实现通过key获取Value的方式
哈希碰撞：2个不同的key通过哈希函数（hash function）得到了相同的内存地址，也就是是内存地址已经被一个占用了，解决方法是将其中之一变为链表结构，使用next指向。这样内存地址就不会重复，但是会影响查询
二、哈希表的操作
2.1 操作时间复杂度
1) 搜索：1.无哈希碰撞，直接用哈希函数通过Key定位到内存地址,复杂度O(1) 2.有哈希碰撞，因为存在内存地址需要通过链表查询,复杂度O(N)
2) 插入：通过key找到内存地址插入即可,复杂度 O(1)--自动插入
unorder_map InquireMap;InquireMap[val] = 1;
3) 删除：通过key找到内存地址删除即可,复杂度 O(1)
2.2 哈希表通用API
- begin()：该函数返回一个指向哈希表开始位置的迭代器
- end()：返回一个指向哈希表结尾位置的下一个元素的迭代器
- empty()：判断哈希表是否为空，空则返回true，非空返回false
- size()：返回哈希表的大小
- erase()： 删除某个位置的元素，或者删除某个位置开始到某个位置结束这一范围内的元素， 或者传入key值删除键值对
- at()：根据key查找哈希表中的元素
- clear()：清空哈希表中的元素
- find()：以key作为参数寻找哈希表中的元素，如果哈希表中存在该key值则返回该位置上的迭代器，否则返回哈希表最后一个元素下一位置上的迭代器
- count()： 统计某个key值对应的元素个数 （注：因为unordered_map不允许重复元素，所以返回值为0或1）
2.3 建立哈希表
unordered_map correspond{ {'I',1}, {'V',5}, {'X',10}, {'L',50}, {'C',100}, {'D',500}, {'M',1000}, };2.3 哈希表常见结构介绍
总体结构上分为数组、set、map
数组也是一种意义上的哈希表
set的结构中每个元素都是一个值（类似于数组）
map的结构是一个 key:value 的数据结构
Set（集合）
1） set、multiset 基于红黑树（一种平衡二叉搜索树），所以（key）值都是有序的，但是不可以修改，一旦修改就会引起整棵树的错乱，所以只能删除和增加，两者唯一的区别是前者不可重复（key）值，后者可以重复
2）unordered_set 底层实现为哈希表，区别就是没有关键码这个说法,哈希表是无序的，所以查询效率要快些O(1)就可以实现。因为无序，所以值也不可以重复
小结：当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
这三种数据结构的具体优劣在这里引用一张表来直观体现
集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率 std::set 红黑树 有序 否 否 O(log n) O(log n) std::multiset 红黑树 有序 是 否 O(logn) O(logn) std::unordered_set 哈希表 无序 否 否 O(1) O(1) Map（映射）
1）map、multimap 基于红黑树（一种平衡二叉搜索树），key是有序的，和上面提到的set、multimap一样，key值可以添加、删除，但是不可以更改（map中，对key是有限制，对value没有限制的。所以说value值可以修改）两者唯一的区别是前者不可重复key值，后者可以重复
2）unordered_map 底层实现为哈希表（无序），因为无序，所以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)
unordered_map（哈希表）
这个数据结构更加常用，所以在这里特别讲一下它的性质
- unordered_map底层存储的是键值对，可以通过key快速的索引到value unordered_map内部因为是数据是通过映射存入哈希桶内的，所以对unordered_map进行遍历得到的是一个无序的序列。
- unordered_map通过key进行访问的速度比map快，但是遍历元素的迭代效率就要低于map了。unordered_map也实现了operator[ ] 可以通过key直接访问到value
三、哈希表的力扣经典题目
有效的字母异位词242
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
class Solution {public: bool isAnagram(string s, string t) { int hash[26] = {0};//26个英文字符 for(int i =0 ;i left && nums[right] == nums[right-1]){ right--; } while(right > left && nums[left] == nums[left+1]){ left++; } //当去完重之后进行原来的操作--收缩指针--原先的都已经用过了，已经为恰好满足 right--; left++; } } } return result; }};题解：
整体上的思路是用双指针替代了哈希表的算法。因为需要返回一个二维数组，并且包括每一种可能，并且还要不重复，所以在这里使用双指针去重的思路。
排序整个数组，从不重复的数字开始，作为i元素，之后在后面的区间里设置j和k两个元素在其各自去重的情况下，计算和是否满足为0，j和k两个元素作为双指针从i+1的位置和size-1的位置向中心移动，移动时检测去重，最终返回结果
四数之和 18
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 =0){ //剪枝处理--便于执行（只大于不等于--因为等于可能也是一种解法 target 0 0 0） //因为只要求k，i，left，right互不相同就可以，去重也是为了防止元素间的对应，就比如当前这个元素使用过了，就不能再使用，两个是分开的意思 break; } if(k>0 && nums[k]==nums[k-1]){ continue;//去重 } for(int i=k+1;i target && nums[i]+nums[k] >= 0){ //剪枝处理的原理是当前的元素大于target，并且两元素大于0，说明后面不可能成立了（都大于0） break; } //去重一定是从k之后元素开始算，因为这也是i的范围 if(i>k+1 && nums[i] == nums[i-1]){ continue; } int left = i+1; int right = nums.size()-1; while(left target){ right--; }else if(targetNum
