一、题目信息
题目链接：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