最小完美哈希

• 目的

  • 为了快速的定位倒排索引中Term的位置，需要使用哈希表。但是哈希冲突是很伤的事情，所以如果能够有一个哈希函数使得每个Term都落入不同的桶就好了。最小完美哈希闪亮登场了。

• 局限

  • 所有的key都必须都知道。
  • 要有不小于|key|的桶数。

• CHM算法

  • 目的：

  • 实现：

  • 

  • 注意通常ix的空间为key的空间的两倍以上。

  • 设计G：

    • 等价于无环图的遍历

    • 

    • 

    • 

    • 所以如果g(i1) = 0, g(i2) 一定等于0，g(i3)一定等于1…

    • 如果上述的dependency在特定ix中会存在环，最后相当于矩阵不可逆，也就无法求出解了。

    • 如何构造出无环的ix呢？

    • 答案就是：F1(str) == sum str[i] + RndTable1[i] mod n。n就是上面中讲到的ix的space。RndTable1是用随机数打的表。F2的结构也类似，只不过是生成的表不同。

    • 居然用随机的话，很明显了，就是RP好无环就手工，有环就再返工重新生成RndTable，

    • 现在需要的就是分析这个凑的过程的运行效率问题。这个就要涉及到f1,f2这两个函数的值域大小，如果越大，越容易凑出一个g函数，但是g函数的参数域就会比较大，存储这个f函数的数据就需要占用更多的空间。相反如果值域越小，在凑的时候就非常容易出现环，需要更长的时间才能凑出这个g函数。

    • 怎么办呢？

      我们可以使用3个的h函数来降低形成环的可能，就是这样h(x)=g(h1(x))+g(h2(x))+g(h3(x))modn ，这样虽然推理g函数的过程会复杂一些，但是很有效，有实验分析表明，当h函数的值域大约参数域的1.23倍的时候，这个g函数的创建尝试次数是常数。