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 11
HELLO ANNK ZOE LOLI

输出格式

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

6 11
LLO 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<bool, N> check;
//In order to judge whether the position with index i has a number
int 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 Probing
	int 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 position
	check[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<double> 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 easily
		cout << findex(a) << endl;
	}
	return 0;
}

​