哈希表及模板

1. 哈希表的主要内容

2. 哈希表的定义

    哈希表是一种数据结构。主要作用就是将一个范围很大的数据，映射到较小的范围(0-N)(一般来讲N为10的5次方~10的6次方之间)。映射之后，可以进行高效的存储和查找。在哈希表中，我们通常用哈希函数h(x)来完成映射的功能。

    因此，如何设计哈希函数就成了哈希表中至关重要的功能之一。一般来讲，比较常用的哈希函数主要是模除法。例如，我们需要将一堆数映射到0-9之间，那么哈希函数直接设置为：
    h(x) = x mod 10
    这样的哈希函数就可以满足我们的要求。模除法是哈希函数最常用的形式。
    需要注意的是，模除的数最好取成一个质数。因为这样可以使得冲突最少。
    注意：在进行模除的时候，结果可能为负数，这样的情况下我们为了保持结果为正数，可以进行如下处理：
    int k = (x % N + N) % N;
    这样的话，就可以保证哈希值k始终为正数。

    当我们使用哈希函数将一堆数映射到指定范围时，可能会出现冲突的情况。例如，我们将若干个数映射到0-9之间的数，就会产生冲突。
    h(10) = 10 mod 10 = 0
    h(20) = 20 mod 10 = 0
    根据上述的例子，我们可以发现：将10和20分别使用h(x)进行映射，发现映射的是同一个位置。这就产生了上述所说的冲突。
    我们需要处理这样的冲突，以便于哈希表可以存储类似10和20这样的可能会产生冲突的数。
    根据处理冲突方式的不同，导致了哈希表存储结构的不同。接下来分别介绍一下哈希表的两大存储结构：开放寻址法和拉链法。

    这里需要补充一下：离散化是及其特殊的哈希方式。因为，离散化通常需要保序。而本博客所讲述的哈希表是一般意义上的哈希方式，不要求保序。

3. 哈希表的操作

    在算法题中，哈希表一般会有两大基本操作：
    1.  添加
        先通过h(x)来进行映射，根据映射的位置进行存储即可。
    2.  查找
        先通过h(x)来进行映射，根据映射的位置进行查找即可。
    对于删除操作，一般算法题是没有的。如果非要将哈希表的元素进行删除的话，我们可以将对应的元素设置一个删除标记(bool类型变量)。当查找到这个元素时，如果该标记为true代表该元素已被删除，否则就未被删除。
    需要注意的是，无论哈希表采用何种存储结构，哈希表的操作一般都是O(1)。

3. 哈希表的存储结构

    拉链法原理：
        1.  首先使用一个数组来存储h(x)所映射的哈希值。
        2.  当产生冲突时，在数组对应的元素下拉一个单链表，将冲突的值存在链表中。

    开放寻址法原理：
        1.  首先使用一个数组来存储h(x)所映射的哈希值。这个数组的长度原则上说是题目数据规模个数的2~3倍。这样的话，发生冲突的概率较低。
        2.  当在k（k为哈希值）这个位置产生冲突时，就去看下一个位置是否空闲，如果空闲就存储，否则就继续往下一个位置寻找，直到找到空闲的位置为止。

4. 哈希表存储结构模板

//(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

//(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

5. 例题

https://www.acwing.com/problem/content/842/

// 拉链法解法
#include <iostream>
#include <cstdio>
#include <cstring>


using namespace std;

const int N = 100003;

int e[N],ne[N],h[N],idx = 0;

void insert(int x){
    //获取哈希值
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool query(int x){
    //获取哈希值
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1 ; i = ne[i]){
        if(e[i] == x){
            return true;
        }
    }
    return false;
}

int main(){
    int n;
    scanf("%d",&n);
    char op[2];
    memset(h,-1,sizeof(h));
    while(n--){
        int number;
        scanf("%s%d",op,&number);
        if(op[0] == 'I'){
            insert(number);
        }else{
            if(query(number)){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }
    }
    return 0;
}

// 开放寻址法解法
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 200003;
const int null = 0x3f3f3f3f;     //代表INT类型最大值，在某些情况下可以替代为无穷大

int h[N];


int find(int x){
    int k = (x % N + N) % N;
    while(h[k] != null && h[k] != x){
        k++;
        //循环查找
        if(k == N){
            k = 0;
        }
    }
    return k;
}

int main(){
    memset(h,0x3f,sizeof(h));
    int n,number;
    char op[2];
    scanf("%d",&n);
    while(n--){
        scanf("%s",op);
        scanf("%d",&number);
        int k = find(number);
        if(op[0] == 'I'){
            h[k] = number;
        }else{
            if(h[k] != null){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }
        
    }
    
    return 0;
}

    在实际的题目中，这两种方法任选其一即可。

6. 字符串哈希方式

    这里所阐述的字符串哈希方式是非常特殊的哈希方式，叫做：字符串前缀哈希法。
    这种方式在算法题中经常出现，因此有必要在这里阐述一下。
    注意：字符串前缀哈希法一般不需要考虑和处理冲突。(在后面会讲到)

    字符串前缀哈希法原理：
        假设给定一个字符串str。str = "ABCABCDEYXCACWING"
        1.  预处理所有前缀的字符串哈希值。
            例如：h[0] = 0
                  h[1] = "A"的哈希值;
                  h[2] = "AB"的哈希值;
                  h[3] = "ABC"的哈希值;
                  h[4] = "ABCA"的哈希值;
                  .....
            其中，h[0]为特殊处理，代表前0个字符串前缀的哈希值。
            所有前缀的子串哈希值我们也可以通过公式求得：
            h(i) = h(i-1) * p + str[i];
            根据上述的内容，我们可以引出两个问题。
                1.1 字符串前缀的哈希值怎么定义？
                    我们可以将整个字符串看作是一个p进制数，而字符串当中的每一个字符看作是这个p进制数的每一位数字。我们来举一个案例：
                    
                    假设字符串str="ABCD",那么怎么求其前缀的哈希值？
                    
                    我们可以将str看作是一个P进制数，而A、B、C、D则看作是这个P进制数的每一个位数。这个位数我们可以从A-Z=>1-26(这里每个字母不能映射为0)。因此ABCD=>(1234)p。那么这个p进制数(1234)p转换为10进制数就是1*p的3次方+2*p的2次方+3*p的1次方+4*p的0次方。因此，我们可以通过这个方式来将一个字符串映射为一个数字。这个数字可能会很大，因此我们还需要将这个数字mod上一个很小的数Q。即：
            ABCD的哈希值 = (1234)p = (1*p的3次方+2*p的2次方+3*p的1次方+4*p的0次方) mod Q;
                1.2 p和Q怎么取？
                    这里有一个经验值：p一般取131或13331;Q一般取2的64次方。
                    如果这么取值的话，我们就不需要考虑冲突问题。
        2.  我们可以利用前面求得的所有字符串前缀哈希值来求得任何一个子串的哈希值。主要是通过如下公式来实现：
            假设，给定一个字符串str，我们已经求得这个str的所有字符串前缀的哈希值。那么，我们现在想要求得str中[L,R]这个区间的子串哈希值。
            我们已知：h[R]代表1到R这个字符串前缀的哈希值（1代表字符串所对应数字的高位，R代表低位）
                      h[L-1]代表1到L-1这个前缀的哈希值（1代表字符串所对应数字的高位，L-1代表低位）
            因此，h[R]的哈希值：p的R-1次方+...+p的0次方
                  h[L-1]的哈希值：p的L-2次方+...+p的0次方
            求得[L,R]这个区间子串的哈希值公式：
            其中r-l+1代表R和L-1之间所相差的位数
            h[R] - (h[L-1] * p的(R-L+1)次方);
        3.  拥有了以上的公式后，我们就可以在O(1)的时间内求出任何一个子串的哈希值。

    字符串哈希的作用：
        当我们想快速的判断两个字符串是否相等，就可以用字符串哈希这种方式。时间复杂度为O(1)

7. 字符串哈希模板

//核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
//小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果(换句话说：我们不需要直接取模，溢出的结果就是取模的结果)。
//这里的字符串从下标1开始存储。

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

8. 例题

https://www.acwing.com/problem/content/843/

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;
const int P = 131;

//p数组代表位权数组,例如：p[0]代表p的0次方....
unsigned long long h[N],p[N];

//求得[l,r]这个区间的字符串的哈希值
unsigned long long get(int l,int r){
    return h[r] - (h[l-1]*p[r-l+1]);
}

int main(){
    int n,m;
    char str[N];
    scanf("%d%d",&n,&m);
    scanf("%s",str+1);
    p[0] = 1;
    for(int i=1;i<=n;i++){
        //预处理所有的位权和前缀哈希值
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + str[i]; 
    }
    while(m--){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1) == get(l2,r2)){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

    作者：gao79138
    链接：https://www.acwing.com/
    来源：本博客中的截图、代码模板及题目地址均来自于Acwing。其余内容均为作者原创。
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。