UVa 188 Perfect Hash

题目分析

本题要求为给定的单词列表构造一个完美哈希函数，函数形式为：

⌊Cw⌋ mod n \left\lfloor \frac{C}{w} \right\rfloor \bmod n⌊wC​⌋modn

其中：

• www是单词转换后的整数值（转换规则：每个字母用555位表示，即乘以323232，a=111，bz=2×32+26=902 \times 32 + 26 = 902×32+26=90）
• nnn是单词列表的长度
• CCC是一个待寻找的正整数，需要尽可能小
• 哈希值必须两两不同，即构成完美哈希

题目还给出一个重要约束：CCC必须是至少一个wiw_iwi​的倍数。

解题思路

单词转换

将每个单词转换为整数：从左到右处理字母，每次将当前值乘以323232，再加上字母对应的数值（a=111，b=222，…，z=262626）。

寻找最小CCC

采用逐步迭代的方法：

1. 从C=1C = 1C=1开始

2. 检查当前CCC是否使所有哈希值互异

3. 若存在冲突（即⌊C/wi⌋ mod n=⌊C/wj⌋ mod n\lfloor C / w_i \rfloor \bmod n = \lfloor C / w_j \rfloor \bmod n⌊C/wi​⌋modn=⌊C/wj​⌋modn），则需要增大CCC

4. 冲突时的最小可尝试CCC为：

   min⁡((⌊Cwi⌋+1)⋅wi,(⌊Cwj⌋+1)⋅wj) \min\left( \left( \left\lfloor \frac{C}{w_i} \right\rfloor + 1 \right) \cdot w_i, \left( \left\lfloor \frac{C}{w_j} \right\rfloor + 1 \right) \cdot w_j \right)min((⌊wi​C​⌋+1)⋅wi​,(⌊wj​C​⌋+1)⋅wj​)

5. 取所有冲突中计算值的最大值作为下一个CCC（因为必须同时解决所有冲突）

6. 重复直到找到可行的CCC

关键优化：由于CCC必须至少是某个wiw_iwi​的倍数，上述更新方法保证新CCC满足该约束。

验证函数test\texttt{test}test

对候选CCC，计算每个单词的哈希值C / w % n，用布尔数组标记是否出现过，若重复则返回false\texttt{false}false，否则true\texttt{true}true。

代码实现

// Perfect Hash// UVa ID: 188// Verdict: Accepted// Submission Date: 2016-03-14// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<int>words;// 存储单词转换后的整数值// 验证函数：检查 C 是否能产生完美的哈希函数// 返回 true 表示所有哈希值互异，false 表示存在冲突booltest(longlongC){vector<int>used;// 标记哈希值是否已被使用for(inti=0;i<words.size();i++)used.push_back(false);for(inti=0;i<words.size();i++){intremainder=C/words[i]%words.size();// 计算哈希值if(used[remainder]==true)// 冲突发生returnfalse;elseused[remainder]=true;}returntrue;}// 寻找最小可行 Clonglongfind(){longlongC=1;// 从 1 开始尝试intn=words.size();do{longlongoldC=C;// 记录本轮初始值// 遍历所有单词对 (i, j)for(inti=0;i<words.size()-1;i++)for(intj=i+1;j<words.size();j++){// 如果存在冲突，则更新 C 为当前冲突中计算的最大值if((oldC/words[i]%n)==(oldC/words[j]%n))C=max(C,min((oldC/words[i]+1)*words[i],(oldC/words[j]+1)*words[j]));}}while(test(C)==false);// 重复直到 C 可行returnC;}intmain(){string line,block;while(getline(cin,line)){istringstreamiss(line);while(iss>>block){intnumber=0;// 将单词转换为整数：每个字母用 5 位表示for(inti=0;i<block.length();i++)number=number*32+block[i]-'a'+1;words.push_back(number);}sort(words.begin(),words.end());// 按升序排序cout<<line<<"\n";// 输出原始输入行cout<<find()<<"\n\n";// 输出 C 并跟一个空行words.clear();// 清空，准备处理下一行}return0;}

复杂度分析

设单词数量为nnn（2≤n≤132 \le n \le 132≤n≤13），则：

• 每次验证test\texttt{test}test的复杂度为O(n)O(n)O(n)
• 每次迭代更新冲突的复杂度为O(n2)O(n^2)O(n2)
• 由于nnn很小，且CCC增长较快，迭代次数有限，算法在实际测试中非常高效

总结

本题的核心在于理解了冲突处理时的CCC更新策略：当⌊C/wi⌋ mod n=⌊C/wj⌋ mod n\lfloor C/w_i \rfloor \bmod n = \lfloor C/w_j \rfloor \bmod n⌊C/wi​⌋modn=⌊C/wj​⌋modn时，两个哈希值相等，要使它们不同，必须增大CCC使得其中一个的商至少增加111，因此下一个候选CCC为min⁡((⌊C/wi⌋+1)⋅wi,(⌊C/wj⌋+1)⋅wj)\min((\lfloor C/w_i \rfloor + 1) \cdot w_i, (\lfloor C/w_j \rfloor + 1) \cdot w_j)min((⌊C/wi​⌋+1)⋅wi​,(⌊C/wj​⌋+1)⋅wj​)。取所有冲突中的最大值，即可保证同时解决所有冲突。这种方法避免了盲目递增，大大提高了搜索效率。