哈希简介

让我们来就哈希表做一个最简单的介绍

哈希表是一个通过key-value对（键-值对）实现快速查找数据的简单数据结构

key是我们将对象插入哈希表时提取的特征，value则是我们需要储存的值。

如果把哈希表理解成一座公寓，那么key在我看来，可以意译为“钥匙”，一把钥匙只能打开一扇门，所以一个key值只能对应一个value。

使用哈希表，就是利用key值实现对数据（value）的快速查询。

接下来，我们来看看哈希表在具体操作中如何使用。

STL实操案例

统计相似字符串对的数目

力扣2506.统计相似字符串对的数目

在此题中，由于数据规模较小，直接暴力枚举也未尝不可。

但是如果用哈希表快速查询有没有相似的字符串，则可将时间复杂度大大较少。

常规思路：

二层循环遍历字符串数组，一个一个找相似字符串对
时间复杂度$O(mn^2)$

大致思路：

对每个字符串提取不同字母的集合，这个集合就可以理解为对象的key，而我们要储存的value就是同一个集合出现的次数。

这样，只需要对每个字符串提取key值，就可以通过哈希表实现$O(1)$的访问效率。
时间复杂度$O(mn)$

粗略来看，哈希表的本质是一种空间换时间的策略，通过提前申请的哈希桶空间，只需要看key值有没有对应的value就知道有没有出现过该key值。

核心思路与桶排序很像，但哈希函数又保证了无论key值是什么类型，哈希桶空间总能维持在合适的大小。

另外，我们可以对提取出来的字母集合做一个初步哈希处理，可把这些字母进行状态压缩，通过它们的有无产生一个最大大小为26位的状态数作为key值。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int similarPairs(vector<string>& words) {
        int len=words.size();
        int sum=0;
        unordered_map<int,int> hash;
        for(int i=0;i<len;i++){
            int sta=0;
            for(char c: words[i]){
                sta=sta|(1<<(c-'a'));
            }
            sum+=hash[sta];//每新增一个，都会和前面所有组队
            hash[sta]++;
            
        }
        return sum;
    }
};

STL标准模板库的哈希表操作

在此仅介绍两种较为常用的哈希类，读者如有兴趣，可自行查阅

std::unordered_map

无序映射哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> myMap;
    //插入方法1，插入新键或覆盖原有value
    myMap["apple"]=188;//可以把key值姑且认为是哈希桶的下标
    //实际操作中，key值会被内部哈希函数转成int值，但是使用时，只需把哈希表理解成一个下标可以是任意类型的“桶”即可
    //插入方法2，只插入新键，无法覆盖原有value
    myMap.insert({"banana",288});
    myMap["orange"] = 300;

    std::cout << "apple: " << myMap["apple"] << std::endl;

    // 查找方法1,会返回一个指向对应元素的迭代器，如果没找到，就返回指向末端的迭代器，用于需要修改哈希表的value时
    if (myMap.find("banana") != myMap.end()) {
        std::cout << "banana exists with value " << myMap["banana"] << std::endl;
    }
    //查找方法2，会返回一个整数，找到元素返回1，没找到返回0
    if(myMap.count("strawberry")){
        std::cout<<"strawberry exists with value "<<myMap["orange"]<<std::endl;
    }else{
        std::cout<<"strawberry has been eaten!!!!"<<std::endl;
    }
    // 遍历
    for (const auto &pair : myMap) {//标准库中，哈希表以<键-值对>的形式储存
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

运行结果：

1
2
3
4
5
6
apple: 188
banana exists with value 288
strawberry has been eaten!!!!
orange: 300
banana: 288
apple: 188

大致方法已在注释中标明，不再赘述。
仅提醒一点 : unordered_map储存键值对，通过pair类型储存，调用first得到key值，调用second得到value值

需要注意的时，若插入时不表明value值，则默认是0

1
2
3
4
5
6
7
//查找方法2，会返回一个整数，找到元素返回1，没找到返回0
    myMap["strawberry"]++;
    if(myMap.count("strawberry")){
        std::cout<<"strawberry exists with value "<<myMap["strawberry"]<<std::endl;
    }else{
        std::cout<<"strawberry has been eaten!!!!"<<std::endl;
    }
1
strawberry exists with value 1

std::unordered_set

大致操作与上述例子相同，区别在于set不储存键key，只储存值value，用于快速去重。

插入原理

对于每一个key-value对，都应该保证key值如果相同，必然指向同一个value。
上面我们提到，key值的类型可以多样化，并不局限于int类型。实际上，哈希表是利用哈希函数把key值转换成哈希表内部储存对象的哈希桶下标（哈希值）。

为了更好地利用空间，这种转化必然是会发生哈希碰撞的，也就是不同的key，产生同一个哈希值的情况。压缩内存的本质就是把一一映射改成多对一映射。

那么我们如何处理上面的现象，也就是哈希碰撞呢？

答案是，把每个哈希值冲突的key以链式结构存入哈希桶中，也就是以链表或者vector\储存

这样的话，只需要在每次哈希值冲突的时候，遍历链式结构，判断有无key值重复即可。

现在我们来看看如何自制简易哈希表以便理解个中缘由

数字哈希

题目

假设现在要输入n个数字，需要判断有几个重复的数字，但是受内存所限，数组空间无法开太大，如何用少于$O(n^2)$的时间复杂度统计？

思路

这时我们就可以简易模拟一个哈希表。
key值就是num本身，因为要保证单映射。
value值在此并没有什么作用，所以可以理解为该哈希表是unordered_set
此时，哈希函数就是对数组空间取余，同时用vector\类型数组防止哈希碰撞。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// #include<bits/stdc++.h>
#include<vector>
#include<iostream>
using namespace std;
const int mod=1e10;
//此处假设数组空间最多开到1e10
vector<int> Myhash[mod];
int main(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=0;i<n;i++){
        int num;
        cin>>num;
        vector<int>& v=Myhash[num%mod];
        int flag=0;
        for(auto& a:v)
            if(a==num){
                flag=1;
                break;
            }
        if(flag==0){//此处flag判断可改成函数判断，提前return
            ans++;
            v.push_back(num);
        }
    }
    cout<<ans<<endl;
    return 0;
}

字符串哈希

P3370 【模板】字符串哈希

题目描述

如题，给定 $N$ 个字符串（第 $i$ 个字符串长度为 $M_i$，字符串内包含数字、大小写字母，大小写敏感），请求出 $N$ 个字符串中共有多少个不同的字符串。

输入格式

第一行包含一个整数 $N$，为字符串的个数。

接下来 $N$ 行每行包含一个字符串，为所提供的字符串。

输出格式

输出包含一行，包含一个整数，为不同的字符串个数。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
5
abc
aaaa
abc
abcc
12345

输出 #1

1
4

说明/提示

对于 $30\%$ 的数据：$N\leq 10$，$M_i≈6$，$Mmax\leq 15$。

对于 $70\%$ 的数据：$N\leq 1000$，$M_i≈100$，$Mmax\leq 150$。

对于 $100\%$ 的数据：$N\leq 10000$，$M_i≈1000$，$Mmax\leq 1500$。

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

题解：

思路与数字哈希类似，都是unordered_set类型的哈希表，不需要储存value。
但是需要注意的是，对于有序字符串，应该如何哈希处理。
此处提供一种思路：将字符串视作’z’+1进制数或者128进制数，随后将字符串整理为整数并对数组空间取余即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// #include<bits/stdc++.h>
#include<vector>
#include<iostream>
#include<string>
using namespace std;
const int mod=10000;
const int maxK='z'+1;
vector<string> Myhash[mod];
int hashCount(string str){
    int len=str.size();
    int value=0;
    for(const char a:str){
        value=(value*maxK+a)%mod;
    }
    return value;
}
int main(){
    int n;
    cin>>n;
    int ans;
    for(int i=0;i<n;i++){
        string str;
        cin>>str;
        int value=hashCount(str);
        vector<string>& vv=Myhash[value];
        if(vv.size()==0)//哈希不冲突，必定是新的
            vv.push_back(str),ans++;
        else{//哈希冲突，看看是不是新的
            int flag=0;
            for(string a:vv){
                if(a==str){
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                ans++;
                vv.push_back(str);
            }
        }
    }
    cout<<ans;
    return 0;
}