全球观察：7-2 案例字符串关键字的散列映射

2022-12-15 22:22:59 来源：博客园

(资料图片仅供参考)

7-2 案例字符串关键字的散列映射

题目描述

给定一系列由大写英文字母组成的字符串关键字和素数P，用移位法定义的散列函数H(Key)将关键字Key中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为P的散列表中。

例如将字符串AZDEG插入长度为1009的散列表中，++我们首先将26个大写英文字母顺序映射到整数0~25++；再通过移位将其映射为3×322+4×32+6=3206；然后根据表长得到3206%1009=179，即是该字符串的散列映射位置。

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

输入格式

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

4 11HELLO ANNK ZOE LOLI

输出格式

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

6 11LLO ANNA NNK ZOJ INNK AAA

AC代码

const int IINF = 0x3f3f3f3f;const long LINF = 0x3f3f3f3f3f3f3f3f;const double EPS = 1.0e-9;const long MOD = 1e9 + 7;const int N = 2e5 + 100;int m, n;array check;//In order to judge whether the position with index i has a numberint findex(string& a){//Encode the characters,each characters occupies two binary bits;int sum = 0;ifor(i, 0, 2){sum += (a[i] - "A") * pow(32, i);}int temp = sum;//Record the encoded value//firstly,Take the remainder of sum and find the subscript,sum = sum % n;int sign = 1;//Change Sign in Square Probingint detal = 1;//increase vlaue;            //可能出现死循环，见下一张while (check[sum]){//if index of sum has number there is conflict,//and then the Quadratic probingf will be used to find empty position。 sum = temp + sign * detal * detal;if (sign < 0) detal++;sign = -sign;sum = sum % n;}if (sum >= n) return -1;// no empty positioncheck[sum] = 1;return sum;}int main(int args, char* argv[]){//ios::sync_with_stdio(false);//cin.tie(nullptr);//cin.tie(nullptr);//auto start = std::chrono::steady_clock::now();//auto end = std::chrono::steady_clock::now();//std::chrono::duration diff = end - start;//std::cout << diff.count() << " s\n";/*clock_t start = clock();clock_t end = clock();double time = (end - start) / CLOCKS_PER_SEC;*/cin >> m >> n;string a;ifor(i, 0, m - 1){cin >> a;reverse(a.begin(), a.end());//in order to encode charactor easilycout << findex(a) << endl;}return 0;}

关键词：输入格式输出格式可能出现

全球观察：7-2 案例 字符串关键字的散列映射

7-2 案例 字符串关键字的散列映射

题目描述

输入格式

输出格式

全球观察：7-2 案例字符串关键字的散列映射

7-2 案例字符串关键字的散列映射