哈希算法--7-14 字符串关键字的散列映射 （25 分）

本文主要是介绍哈希算法--7-14 字符串关键字的散列映射 （25 分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

除留余数法设计哈希表 ：

由该式子得到value在哈希表中的存储位置：index = value % p；这里为了尽量的减少冲突，而且让value在哈希表中尽可能的均匀分布，p的选择就至关重要了。而合理选择p的经验是：若散列表表长为m，通常p为小于或等于表长（最好接近m)的最小质数或不包含小于20质因子的合数。

平方探测法：

冲突是不可避免的，本题中提到的解决冲突的平方探测法：

1. 当index的位置已经没有被占用，则index就是hash值。如果已经别占用，则进行步骤2.
2. 看ans = index+k*k（k从1开始）是不是被占用，如果没有被占用，则ans为hash值，否则就进行步骤3.
3. 看ans = index-k*k（k从1开始）是不是别占用，如果没有被占用，则ans为hash值，否则就k++，进行步骤2.

代码：

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define INF 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin)using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn = 50010;
map<string,int> mp;
string str;
int vis[maxn];int Judge(int sum, int p){sum %= p;if(mp.count(str)){//重复出现return sum;}if(vis[sum] && mp[str] == 0){//发生冲突int k = 1,tmp = sum;while(vis[sum]){sum = (tmp+k*k)%p;if(!vis[sum])break;sum = (tmp-k*k+p)%p;k++;}vis[sum] = 1;mp[str] = sum;return sum;}else if(!vis[sum] && mp[str] == 0){vis[sum] = 1;mp[str] = sum;return sum;}
}int main() {//FRE();int n,p;cin>>n>>p;memset(vis,0,sizeof(vis));for(int i = 0; i<n; i++) {cin>>str;int len = str.size(),sum = 0;if(len>3) {for(int j = len-3; str[j]; j++) {int temp = str[j]-'A';sum = sum*32 + temp;}} else {for(int j = 0; str[j]; j++) {int temp = str[j] - 'A';sum = sum*32 + temp;}}int tt = Judge(sum, p);if(i == 0)cout<<tt;elsecout<<" "<<tt;}cout<<endl;return 0;
}
/*
输入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
*/

 

 

这篇关于哈希算法--7-14 字符串关键字的散列映射 （25 分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---