search

linvon / cuckoo-filter

Cuckoo Filter go implement, better than Bloom Filter, configurable and space optimized 布谷鸟过滤器的Go实现，优于布隆过滤器，可以定制化过滤器参数，并进行了空间优化
MIT License
294 stars 28 forks source link

能否暴露布谷鸟过滤器是否满的方法或者接口 #5

Closed GuoxinL closed 2 years ago

GuoxinL commented 2 years ago

能否暴露布谷鸟过滤器是否满的方法或者接口 f.victim.used 如果只通过Add方法判断是有歧义的

linvon commented 2 years ago

有歧义是指？ victim.used只有在超过kick out次数后置true认为“满”了并无法再写入，add方法本身也是这个逻辑

GuoxinL commented 2 years ago

Add方法的功能没有问题，因为filter满了确实不可以在添加item并且重复也不可以添加item，这都没有问题；但是，我在Add后得到的false结果中区分不出来当前过滤器是否是满了，还是当前过滤器没有满但item已存在； 所以才希望您能暴露这个方法

func (f *Filter) IsFull() bool {
    return f.victim.used
}

这样的话，我就可以在add后明确的通过IsFull来知道是否真的满了 如果您认可这样的方式我可以提一个pr

linvon commented 2 years ago

你可以在阅读一下添加元素过程的代码，它和布隆过滤器添加元素并不一样，f.victim.used只会在item不断被kick out直至无法填入时置true，虽然实际过滤器可能还有空间，但这时我们认为过滤器已经“满了”，因此add方法返回false时就是我们所说的满了

GuoxinL commented 2 years ago

我看过这里的源码add的过程中用“kMaxCuckooCount”来限制踢的次数； 您的意思是我每次需要判断满的时候都可以调用add方法，就可以知道当前filter是否满是吧；感觉哈，这么做不是特别好：） 感觉不是特别的明确

GuoxinL commented 2 years ago

我的需求是想用多个布谷鸟过滤器形成一个链表，比如有10个filter的filterChain，item进入时会插入到最近的一个，会判断当前filter是否满，如果没有满的话就会插入，如果满的话就进入下一个filter，都满了会采用LRU的方式去做淘汰；

linvon commented 2 years ago

其实是一样的，你直接调用add，对于插入失败就表示满了，可以避免先判断full再插入这样的冗余代码

GuoxinL commented 2 years ago

之前的理解错误，将Add方法理解成非线性的了

感谢您耐心的解答!