# 布谷鸟过滤器

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

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

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

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

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

## 查找

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

```c
// 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 函数吧

## 插入

```c
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。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wtifs.gitbook.io/diva-notes/data-structure/bu-gu-niao-guo-lv-qi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.