字符串关键字的散列映射
给定一系列由大写英文字母组成的字符串关键字和素数P，用移位法定义的散列函数H(Key)将关键字Key中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为P的散列表中。
例如将字符串AZDEG插入长度为1009的散列表中，我们首先将26个大写英文字母顺序映射到整数0~25；再通过移位将其映射为3×32^2+4×32+6=3206；然后根据表长得到3206%1009=179，即是该字符串的散列映射位置。
发生冲突时请用平方探测法解决。
#include<iostream>
#include<cstdio>
#include<algorithm> // 包含算法库，用于reverse函数
#include<cmath> // 包含数学库，用于pow函数
#include<unordered_map> // 包含无序映射库，用于快速查找字符串
using namespace std;// 定义一个哈希函数，将字符串转换为一个整数哈希值
int strHash(string s) { reverse(s.begin(), s.end()); // 反转字符串int sum = 0, num = 0;for(auto i : s) {sum += (i-'A')*pow(32, num); // 根据字符和位置计算哈希值num++;if(num == 3) break; // 只考虑前3个字符}return sum;
}int main() {int n, p; cin >> n >> p; // n表示字符串数量，p表示哈希表大小unordered_map<string, int>um; // 用于存储字符串及其对应的哈希表中的位置int Hash[p] = {0}; // 创建哈希表，初始化为0fill(Hash, Hash+p, -1); // 将哈希表所有元素初始化为-1，表示空位for(int i = 0; i < n; i++) {if(i != 0) cout << ' '; // 不是第一个字符串时，输出空格string s; cin >> s; // 输入字符串if(um.count(s)) { cout << um[s]; continue; } // 如果字符串已存在于映射中，直接输出其位置int num = strHash(s); // 计算字符串的哈希值int y = num%p; // 计算哈希值在哈希表中的位置int tmp_y = y;int n1 = 1, n2 = 1;// 解决哈希冲突：线性探测法while(Hash[tmp_y] != -1) {tmp_y = y; if(n2 % 2 != 0) {tmp_y = (tmp_y+n1*n1)%p; // 奇数步：正向探测n2++;}else {tmp_y = (tmp_y-n1*n1+p)%p; // 偶数步：反向探测n2++; n1++;}}Hash[tmp_y] = num; // 将哈希值存入哈希表um[s] = tmp_y; // 将字符串及其位置存入映射cout << tmp_y; // 输出字符串在哈希表中的位置}return 0;
}
