Snapchat BloomFilter Remove

刷snapchat面经的时候遇到了一道题，关于bloom filter，面试官要求能实现remove，但是问题是，remove不就导致bloom filter不准了吗？我最开始考虑的是用一个counter，add就是++， remove就--，但是感觉还是不对，不知道各位大神有什么想法，多谢

http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311

bloomfilter不支持remove~..如果要remove..要rebuild everything～

leixiang5 发表于 2016-9-22 02:07
bloomfilter不支持remove~..如果要remove..要rebuild everything～

对呀……所以我觉得面试官问这个不知道啥意思……

神罗天征 发表于 2016-9-22 02:25
对呀……所以我觉得面试官问这个不知道啥意思……

会不会是要cuckoo filter?

leixiang5 发表于 2016-9-22 04:48
会不会是要cuckoo filter?

这个好高级……不过看了一些博客，好像确实可以用counter

应该是counter bloom filter啊，lintcode上有原题目。

pinkdatura 发表于 2016-11-2 14:15
应该是counter bloom filter啊，lintcode上有原题目。

啊？请问是哪一道题呀

好像是上过设计课的能看到，其实你去他们网站搜一下counter bloom filter的答案就能看懂，其实就是每一位存数字而不是存boolean

https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters