UVa 188 Perfect Hash

题目分析本题要求为给定的单词列表构造一个完美哈希函数函数形式为⌊Cw⌋ mod n \left\lfloor \frac{C}{w} \right\rfloor \bmod n⌊wC​⌋modn其中www是单词转换后的整数值转换规则每个字母用555位表示即乘以323232a111bz2×3226902 \times 32 26 902×322690nnn是单词列表的长度CCC是一个待寻找的正整数需要尽可能小哈希值必须两两不同即构成完美哈希题目还给出一个重要约束CCC必须是至少一个wiw_iwi​的倍数。解题思路单词转换将每个单词转换为整数从左到右处理字母每次将当前值乘以323232再加上字母对应的数值a111b222…z262626。寻找最小CCC采用逐步迭代的方法从C1C 1C1开始检查当前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冲突时的最小可尝试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​)取所有冲突中计算值的最大值作为下一个CCC因为必须同时解决所有冲突重复直到找到可行的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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorintwords;// 存储单词转换后的整数值// 验证函数检查 C 是否能产生完美的哈希函数// 返回 true 表示所有哈希值互异false 表示存在冲突booltest(longlongC){vectorintused;// 标记哈希值是否已被使用for(inti0;iwords.size();i)used.push_back(false);for(inti0;iwords.size();i){intremainderC/words[i]%words.size();// 计算哈希值if(used[remainder]true)// 冲突发生returnfalse;elseused[remainder]true;}returntrue;}// 寻找最小可行 Clonglongfind(){longlongC1;// 从 1 开始尝试intnwords.size();do{longlongoldCC;// 记录本轮初始值// 遍历所有单词对 (i, j)for(inti0;iwords.size()-1;i)for(intji1;jwords.size();j){// 如果存在冲突则更新 C 为当前冲突中计算的最大值if((oldC/words[i]%n)(oldC/words[j]%n))Cmax(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(issblock){intnumber0;// 将单词转换为整数每个字母用 5 位表示for(inti0;iblock.length();i)numbernumber*32block[i]-a1;words.push_back(number);}sort(words.begin(),words.end());// 按升序排序coutline\n;// 输出原始输入行coutfind()\n\n;// 输出 C 并跟一个空行words.clear();// 清空准备处理下一行}return0;}复杂度分析设单词数量为nnn2≤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​)。取所有冲突中的最大值即可保证同时解决所有冲突。这种方法避免了盲目递增大大提高了搜索效率。