哈希表（一）

一、基础知识

哈希表的优点：

查找key的时间效率是O（1）

什么时候要用到哈希表：

查询元素的出现问题（是否出现过，是否在集合里，出现次数等）

哈希表的三种数据结构：

数组（数据范围较小时）

set（数据范围很大或者数据很散乱时）

map（需要同时用到key和value时）

二、数组

    bool isAnagram(string s, string t) {//仅26个英文字母，且是连续的，数据范围可为[0,25]，用数组int hash[26]={0}; //初始化，记录字母出现次数的哈希数组if(s.size()!=t.size()){return 0;}for(int i=0;i<s.size();i++){ //遍历字符串，哈希计数hash[s[i]-'a']++; //映射，key值是字母-'a'（作差得起点），value是出现次数hash[t[i]-'a']--;}for(int i=0;i<26;i++){ //遍历哈希数组，看哈希计数是否为0（先+后-，若相等，最后为0）if(hash[i])return 0;}return 1;}

 对于26个连续的小写英文字母，要记录其出现的次数，用哈希数组即可；

遍历字符串，在hash[s[i]-'a']的位置进行++或--的操作；

最后判断哈希数组中是否全为0，若是则证明两个字符串是字母异位词。

三、set

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {//unordered set自动去重，用来定义resultunordered_set<int> result; //注意要写<int>//直接将数组1转变为set，便于判断数组2的元素是否在数组1集合中，减免了对1的for遍历unordered_set<int> nums1_set(nums1.begin(),nums1.end()); //转换是.begin()，.end()for(int i=0;i<nums2.size();i++){if(nums1_set.find(nums2[i])!=nums1_set.end()){//能找到，说明是交集元素result.insert(nums2[i]);}}return vector<int>(result.begin(),result.end()); //最终返回的是数组，转化为vector<int>}

对于装有零散数据（数据范围很大）的集合，用set

 将nums1数组变为集合1，遍历nums2数组，判断元素是否存在集合1中

若是，则加入result（unordered_set自动去重）中

四、map

vector<int> twoSum(vector<int>& nums, int target) {//用哈希map来存放遍历过的元素，数值作为key，索引作为value（哈希表查找key的效率是o(1)，查找很快）//遍历数组元素，首先求该元素的配对元素，然后判断它是否在遍历过的map中，没有则将当前元素加入map，继续遍历下一个unordered_map<int,int> map;for(int i=0;i<nums.size();i++){int s=target-nums[i];auto iter=map.find(s); //查找key，找到时返回位置指针，找不到时返回.end()if(iter!=map.end()){//说明找到了，直接返回答案即可return {iter->second,i};//要写second，不能写value}map[nums[i]]=i;}return {};}

 对于既要用到数组元素值（key），又要用到索引（value）的情况，用map

（key是要查找的东西，所以将元素值作为key）

遍历数组元素，判断和当前元素对应的值（terget-nums[i]）是否存在于遍历过的元素集合map中，

若是，则返回答案；若不是，则将当前元素加入map中，继续遍历下一元素