【重要】这个布谷鸟的库有一个坑，请尽快更新！

有没有，存不存在？这是一个很经典的场景，几乎每一位互联网开发者都遇到过。其对应的解决方案也比较多。布谷鸟过滤器就是其中一种十分流行的方案。

当然，本篇并不是来介绍布谷鸟过滤器的原理，而是记录一个老许在使用一个布谷鸟过滤器开源库时遇到的坑。如果有读者和老许使用了相同的开源库，请及时更新最新的代码以避免线上panic。当然，如果是自实现的布谷鸟过滤器，老许愿称你为：

其他废话不多说，我们来看一下这个开源库和坑分别是什么。

开源库：

https://github.com/seiflotfy/cuckoofilter

坑：

func TestService_getInstalledApps(t *testing.T) {
    // 从缓存或者其他地方取出布谷鸟过滤器的数据，解析得到布谷鸟过滤器实例
 c, err := cuckoo.Decode([]byte(""))
 assert.Nil(t, err)
 // 查询 test 是否存在
 assert.False(t, c.Lookup([]byte("test")))
}

上面这个单元测试是无法正常运行的，其结果如下：

--- FAIL: TestService_getInstalledApps (0.00s)
panic: runtime error: index out of range [3532051776] with length 0 [recovered]
 panic: runtime error: index out of range [3532051776] with length 0

goroutine 19 [running]:
testing.tRunner.func1.2({0x102e36060, 0x140000e4240})
 /usr/local/go/src/testing/testing.go:1209 +0x258
testing.tRunner.func1(0x140000fe680)
 /usr/local/go/src/testing/testing.go:1212 +0x284
panic({0x102e36060, 0x140000e4240})
 /usr/local/go/src/runtime/panic.go:1038 +0x21c

根据上面的单元测试，我们下面分别看一看Decode和Lookup函数。

Decode函数

// Decode returns a Cuckoofilter from a byte slice
func Decode(bytes []byte) (*Filter, error) {
 var count uint
 if len(bytes)%bucketSize != 0 {
  return nil, fmt.Errorf("expected bytes to be multiple of %d, got %d", bucketSize, len(bytes))
 }
 buckets := make([]bucket, len(bytes)/4)
 for i, b := range buckets {
  for j := range b {
   index := (i * len(b)) + j
   if bytes[index] != 0 {
    buckets[i][j] = fingerprint(bytes[index])
    count++
   }
  }
 }
 return &Filter{
  buckets:   buckets,
  count:     count,
  bucketPow: uint(bits.TrailingZeros(uint(len(buckets)))),
 }, nil
}

首先，检查输入是否为bucketSize的倍数，如果不是则输入不合法，如果是则构建布谷鸟实例。然而，这里有一个隐含条件是空字符串的长度一定是bucketSize的倍数，这也就导致构建的布谷鸟实例中buckets的长度为0，同时也为后续的panic埋下了伏笔。

“

这里额外提一句，bits.TrailingZeros函数在惊！Go里面居然有这样精妙的小函数！中提到过，其作用是返回输入值最低位为0的个数。所以，输入值为0时，则返回值为32或者64。

”

Lookup函数

// Lookup returns true if data is in the counter
func (cf *Filter) Lookup(data []byte) bool {
 i1, fp := getIndexAndFingerprint(data, cf.bucketPow)
 if cf.buckets[i1].getFingerprintIndex(fp) > -1 {
  return true
 }
 i2 := getAltIndex(fp, i1, cf.bucketPow)
 return cf.buckets[i2].getFingerprintIndex(fp) > -1
}