【pta】7-43 字符串关键字的散列映射 <字符串类型散列表、平方探测法>

2024-01-07 16:10:58

一、题目信息

题目链接：https://pintia.cn/problem-sets/15/problems/890

给定一系列由大写英文字母组成的字符串关键字和素数P，用移位法定义的散列函数H(Key)将关键字Key中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为P的散列表中。例如将字符串AZDEG插入长度为1009的散列表中，我们首先将26个大写英文字母顺序映射到整数0~25；再通过移位将其映射为3×322+4×32+6=3206；然后根据表长得到3206，即是该字符串的散列映射位置。

发生冲突时请用平方探测法解决。

输入格式:

输入第一行首先给出两个正整数N（≤500）和P（≥2N的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个字符串关键字，每个长度不超过8位，其间以空格分隔。

输出格式:

在一行内输出每个字符串关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

输入样例1:

4 11
HELLO ANNK ZOE LOLI

结尾无空行

输出样例1:

3 10 4 0

结尾无空行

输入样例2:

6 11
LLO ANNA NNK ZOJ INNK AAA

输出样例2:

3 0 10 9 6 1

二、第一版代码

#include<bits/stdc++.h>
using namespace std;

int a[10005];
map<string,int>mp;

int main(void)
{
    int n,p;
    scanf("%d %d",&n,&p);
    for (int i=0;i<n;i++)
    {
        string s;
        int h=0,cnt=0,flag1=0,flag2=0;
        cin>>s;
        //cout<<s.length()<<endl;
        if(s.length()>=3) for (int j=s.length()-3;j<s.length();j++) h=(h<<5)+s[j]-'A';
        else for (int j=0;j<s.length();j++) h=(h<<5)+s[j]-'A';
        //cout<<h<<endl;
        if (mp.count(s)==1){
            if (i>0) printf(" ");
            printf("%d",mp[s]);
            continue;
        }
        if (a[h%p]==0)
        {
            mp[s]=h%p;
            a[h%p]=h;
            if(i>0) printf(" ");
            printf("%d",h%p);
        }
        else
        {
             for (cnt=1;;)
             {
                 if (a[(h+(int)pow(cnt,2))%p]&&a[(h+(int)pow(cnt,2))%p]!=h)
                 {
                     if(a[(h-(int)pow(cnt,2))%p]&&a[(h-(int)pow(cnt,2))%p]!=h) cnt++;
                     else {
                            mp[s]=(h-(int)pow(cnt,2))%p;
                            a[(h-(int)pow(cnt,2))%p]=h;
                            flag2=1;
                            break;
                     }
                 }
                 else{
                        mp[s]=(h+(int)pow(cnt,2))%p;
                        a[(h+(int)pow(cnt,2))%p]=h;
                        flag1=1;
                        break;
                 }
                 if (flag1||flag2) break;
             }
            if (i>0) printf(" ");
            if (flag1) printf("%d",(h+(int)pow(cnt,2))%p);
            else if(flag2) printf("%d",(h-(int)pow(cnt,2))%p);
        }
    }
    return 0;
}

当时一直百思不得其解，后来找到了一组数据

虽然这些字符串的哈希值是相同的都是0，但是明显它们字符串不同所以发生了冲突，应该采取平方探测法。

我从网上找来了几段ac代码，将数据代入发现和我预想的不太一样，于是我又重拾思路解决这个问题

三、ac代码

#include<bits/stdc++.h>
using namespace std;

map<string,int>mp;
set<int>st;
int n,p;
int main(void)
{
    scanf("%d %d",&n,&p);
    for (int i=0;i<n;i++)
    {
        string s;
        int h=0,cnt=1,flag1=0,flag2=0;
        cin>>s;
        if(s.length()>=3) for (int j=s.length()-3;j<s.length();j++) h=(h<<5)+s[j]-'A';
        else for (int j=0;j<s.length();j++) h=(h<<5)+s[j]-'A';
        if (mp.count(s)==1){ //重复元素，可进行直接输出
            if (i>0) printf(" ");
            printf("%d",mp[s]);
            continue;
        }
        if (st.find(h%p)==st.end()){ //哈希值没有被使用过，可以进行插入
            st.insert(h%p);
            mp[s]=h%p;
            if(i>0) printf(" ");
            printf("%d",h%p);
        }
        else{
            while(true){
                if (st.find((h+cnt*cnt)%p)!=st.end()){
                    if ((h-cnt*cnt)%p<0){
                        cnt++;
                        continue;
                    }
                    if(st.find((h-cnt*cnt)%p)!=st.end()) cnt++;
                    else {
                            st.insert((h-cnt*cnt)%p);
                            mp[s]=(h-cnt*cnt)%p;
                            flag2=1;
                            break;
                    }
                }
                else{
                        st.insert((h+cnt*cnt)%p);
                        mp[s]=(h+cnt*cnt)%p;
                        flag1=1;
                        break;
                }
                if (flag1||flag2) break;
            }
            if (i>0) printf(" ");
            if (flag1) printf("%d",(h+cnt*cnt)%p);
            else if(flag2) printf("%d",(h-cnt*cnt)%p);
        }
    }
    return 0;
}

这与我预期相同，也终于ac过了

当时因为不知道如何对map的value进行查找，故采用set来判断哈希值是不是被使用过了，需不需要使用平方探测法

后来想到可以使用迭代器进行遍历对比，虽然复杂度略高于set的查找效率

bool func(map<string,int>mp,int n)
{
    for (auto it:mp) if (it.second==n) return false;
    return true;
}

或者可以开一个vis数组，采用空间换时间的方法

以及，到最后我把之前的a数组内容删了，居然一点影响都没有，可见本题中map还是可以替代数组的（doge）

四、亿些知识点

字符串散列表哈希值函数

位运算

在上图中，h<<5 == h*32 ==h*2^5

左移的运算会比直接相乘速度更快

平方探测法

当你要插入的哈希值对应的格子被占时，key向右加一的平方看是不是空着的，如果也被占就key向左减一的平方，如果还被占就向右加二的平方……

如此反复直到找到一个空的格子插入

这里可以从上到下看每一行来理解这个方法

set

set就相当于一个集合，里面的值是唯一的

set的底层逻辑和map一样，是基于红黑树排列的，所以里面的值是默认排过序的

因此，set与map对于key的查找效率都为O(logn)~

最后感谢所有大佬的代码

尤其是mooc的陈越姥姥和何钦铭老师yyds！

peace

码农公寓