布谷鸟过滤器.md

布谷鸟过滤器

不储存元素的原始值，而是存其指纹信息 fingerprint（8 位的 bit）。

将元素转为 hash。每个元素计算 2 个 hash 作为下标。一个主位置，一个备选位置。并且利用异或，主备位置可以互相算出来。

插入元素时，如果主位置已经被占了（发生冲突），则将占用的元素 A 踢到 A 的备选位置上，如果 A 的备选位置上还有元素 B，再把 B 踢到 B 的另一个位置上（备选位置或主位置），依次进行直到成功或到达次数上线。

如果到达次数上限，则说明该扩容了。

Redisbloom 里的布谷鸟过滤器还支持多次重复添加/删除一个元素，做法是，首先，一个桶内有 8个位置可以插入，二是 8个位置都满了后，还可以增加多组桶 filter，相当于将一维数组变为二维。

查找

查找元素时，分别查找主位置和备选位置上是否有相应的指纹。

// https://github.com/RedisBloom/RedisBloom/blob/bdc753e983aa1e23fea733d75b4e4e54848093c1/src/cuckoo.c
static void getLookupParams(CuckooHash hash, LookupParams *params) {
    params->fp = hash % 255 + 1;                     // 指纹
    params->h1 = hash;                               // 主位置
    params->h2 = getAltHash(params->fp, params->h1); // 备选位置
}

static CuckooHash getAltHash(CuckooFingerprint fp, CuckooHash index) {
    return ((CuckooHash)(index ^ ((CuckooHash)fp * 0x5bd1e995)));
}

（这感觉有问题啊？指纹居然是根据 hash 值取余算出的。如果两个不同的 key hash 冲突，那么算出下标和指纹都一样，就没法区分了。算指纹应该用一个单独的 hash 函数吧

插入

static CuckooInsertStatus Filter_KOInsert(CuckooFilter *filter, SubCF *curFilter, const LookupParams *params) {

    while (counter++ < maxIterations) {
        
        uint8_t *bucket = &curFilter->data[ii * bucketSize]; // 计算元素应放入的bucket
        swapFPs(bucket + victimIx, &fp);                     // 将bucket的头元素和当前元素互换
        ii = getAltHash(fp, ii) % numBuckets;                // 为换出来的头元素（这里叫受害者）找下一个位置
        
        // Insert the new item in potentially the same bucket
        uint8_t *empty = Bucket_FindAvailable(&curFilter->data[ii * bucketSize], bucketSize);  // 下一个位置可以在本bucket内
        if (empty) {     // 如果下个位置是空的，则直接插入
            *empty = fp; // 赋值指纹信息
            return CuckooInsert_Inserted;
        }
        
        victimIx = (victimIx + 1) % bucketSize;              // 如果换出来的受害者没有地方去了，换下一个受害者尝试
    }

    // If we weren't able to insert, we roll back and try to insert new element in new filter
    // 超过maxIterations会触发扩容，扩容后这里再试一次
    // 扩容会加个 filter
    // ...

    return CuckooInsert_NoSpace;
}

布谷鸟过滤器相对布隆，有什么缺点？

相同数据量和误差率条件下，布谷鸟的理论空间占用会高点。布隆过滤器理论每个元素只占1个bit，布谷鸟的指纹要占 8 bit。