基于原论文，我实现了一个更全面的布谷鸟过滤器(2)-木庄网络博客

当前第2页返回上一页

首先哈希函数我们使用两个就足够了，这可以达到足够的空间利用率。根据我们需要的假阳性率，我们可以确定使用多大的桶大小，当然 b 的选择并不绝对，即使 r>0.002，你也可以使用 b=4 来启用半排序桶。之后我们可以根据 b 来计算为了达到目标假阳性率，我们需要的 f 的大小，这样所有的过滤器参数就确定了。

将上面的结论与布隆过滤器的每项 $1.44log_2(1/r)$ 对比，可以发现启用半排序时，当 r<0.03 左右，布谷鸟过滤器空间更小，若不启用半排序，则退化到 r<0.003 左右。

一些进阶解释

哈希算法的优化

虽然我们指定了需要两个哈希算法，但实际实现上我们使用一个哈希算法就足够了，因为在论文中提到了一种备选桶计算方法，第二个哈希值可以由第一个哈希值与该位置存储的指纹异或计算得来。如果你在担心我们还需要分别计算指纹的哈希和位置的哈希，我们可以只用一种算法制作 64 位的哈希，高 32 位用于计算位置，低 32 位用于计算指纹。

为什么半排序桶只能用于 b=4 的情况？

半排序的本质是对每个指纹取其四位，该四位可以表示为一个十六进制，对于 b 个指纹的四位存储就可以表示为 b 个 16 进制数，将其所有可能按顺序排列后，可以通过索引其位置来找到对应的排列，从而获取实际的存储值。

我们可以通过以下函数计算所有的情况种类数

func getNum(base, k, b, f int, cnt *int) {
    for i := base; i < 1<<f; i++ {
        if k+1 < b {
            getNum(i, k+1, b, f, cnt)
        } else {
            *cnt++
        }
    }
}

func getNextPow2(n uint64) uint {
    n--
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    n |= n >> 32
    n++
    return uint(n)
}

func getNumOfKindAndBit(b, f int) {
    cnt := 0
    getNum(0, 0, b, f, &cnt)
    fmt.Printf("Num of kinds: %v, Num of needed bits: %v\n", cnt, math.Log2(float64(getNextPow2(uint64(cnt)))))
}

在 b=4 时，总共有 3786 种排列，小于 4096，即用 12 位即可存储所有的排列索引，而如果直接存储所有指纹，则需要 4X4=16 位，这样节省了 4 位，即对每一个指纹节省了一位。

可以发现，在 b 为 2 时是否启用半排序需要存储的位数相同，没有意义。如果 b 太大则需要存储的索引也会急剧扩张，会在查询性能上有很大的损耗，因此 b=4 是一个性价比最高的选择。

此外编码存储四位指纹的选择是因为其刚好可以用一个十六进制表示，利于存储

使用半排序时的参数选择

使用半排序时，应保证 $ceil(b*(f-1)/8)<ceil(b*f/8)$，否则是否使用半排序占用的空间是一样大的

过滤器大小选择

过滤器的桶总大小一定是 2 的指数倍，因此在设定过滤器大小时，尽量满足 $size/α ~=(<) 2^n$，size 即为想要一个过滤器存储的数据量，必要时应选择小一点的过滤器，使用多个过滤器达到目标效果