返回信息流用bloom filter判断一个元素是不是在一个集合里，如果判断不存在，那肯定不存在，如果判断存在，有可能是false positive。
我现在的需求正好相反，如果判断该元素属于这个集合，那它一定属于这个集合，如果判断不属于这个集合，允许出现false negative。
用map或者bitset都能实现，但是想充分节省内存，有什么好的数据结构或者算法吗？
通过『我邮2.0』发布
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #90219同步于 2016/5/21
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
问个和bloom filter类似的问题
nxlhero
2016/5/21镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。
2 条回复
如果你要求bloom filter的内存占用，即n为元素总数，内存占用为n * K bits，（K ~= 4)。
我觉得这个不太可能实现。至少不太可能用hash来实现。
比如：
a != b
hash(a) == hash(b) // it is possible
a in set and b not in set
check(b) is True // but b not really in set
桶式hash本身会导致不同的key有相同的hash值，这样hash值存在，不能保证key一定存在。如楼上所说。
bloom filter使用hash值的组合，这些组合又会导致bloom filter返回true，但是key不一定存在。
如果要保证有hash值，key一定存在，那么不同key的hash值一定不能重复，这就变成编码问题了：给每个key设计一个唯一的编码。