搜索引擎的设计(1)：词典的设计 中篇

此文已由作者刘超授权网易云社区发布。

欢迎访问网易云社区，了解更多网易技术产品运营经验

在有环图中，我们开始假设g(i1)=0

，最后绕了一圈回来，计算出g(i1)=1

，两者矛盾，算法失败。

那么怎样才能避免图有环呢？这就不是g函数的事情了，轮到该好好的设计f1和f2函数了。从前面的描述中，我们知道，图中的节点是由f1和f2计算出来的，取值范围[0, n-1]，共n个，而边的个数是由最后的哈希值决定的，共m个，如果节点多边少，则出现环的概率就小，按照论文中的说法，n>2m是最好的。

另外对于函数f1和f2，我们采取这样的设计，对于每一个字符串w，都是由一系列字符组成的，对于每一个字符w[i]，生成一个取值[0, n-1]的随机数，从而形成一个表格T1，然后同样产生另一组随机数，形成另一个表格T2，然后形成下面的公式：

比如对于字符串“abc”，对于a出现在第一个位置，我们产生两个随机数

，

，同样对于b出现在第二个位置，也产生两个随机数

，

，对于c出现在第三个位置也产生两个随机数

，

，则

,

，则第一层完毕，下面就可以开始构建图了。

f1和f2如此设计怎么就可以保证图是无环的呢？当然不能保证随机生成的两个函数映射表最终形成的图就一定是无环的。好在咱们是基于随机数的，一组随机数最后发现有环，再来一组不就行了，直到形成的图无环为止，反正产生随机数又不要钱。

下面咱们就举一个完整的例子，将这个过程演示一遍。

一年有12个月，采用缩写就是：Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec。咱们就针对这些字符串生成一个最小完美哈希。一共12个字符串，m=12，要求n>2m，咱们就姑且取n=25。

首先第一步，构造随机数表T1和T2，每个字符串有三个字符，我们通过观察可以发现，第二个和第三个字符的组合也是唯一的，为简单起见，咱们仅仅考虑第二个和第三个字符，如图所示。

第二步，由随机数表，我们就可以计算出f1:

同理我们可以计算出f2:

第三步，由此我们可以得到图了，如图，我们从Jan开始构造图，Jan的顶点为5和12，边就是我们希望得到的最后哈希值0，Feb的顶点为5和22，边为1，Mar的顶点为22和12，边为2，不好！竟然出现环了。

 

我们只好重新生成随机数表，如图所示：

 

然后重新计算出f1:

重新计算出f2:

重新绘制图，如图：

最后一步，得到g 函数的映射表。我们假设每个不连通的图中值最小的节点的g 函数的映射为0，也即假设g（0）=0，g（11）= 0,g

(14)=0,g(8)=0.

，然后进行推导，推导过程如图:

 

最后得出g 函数的映射表如图：

 

自此最小完美哈希大功告成。

在用户查询字符串Aug的时候，我们就使用哈希函数：

正好找到哈希表中Aug所在的位置。

当然最小完美哈希唯一不够完美的地方就是，它是针对静态集合的，也即在构造最小完美哈希之前，所有的字符串都必须知道，因而对字符串的增删改不能很好的支持。

搜索引擎的设计(1)：词典的设计 下篇

11.1—11.15云计算基础服务全场5折起

免费体验云安全(易盾)内容安全、验证码等服务

更多网易技术、产品、运营经验分享请点击。