布隆过滤器逆？有可能吗？

Question

来自一个面试问题：

确定单词是否在存储的列表中。该列表不适合内存。不允许磁盘访问，仅用于查找，仅允许内存访问。不允许误报，误报正常。

Bloom过滤器做的恰恰相反:允许误报，不允许漏报。

我的想法是:我们不能使用哈希函数，因为我们可能会有违反“无误报”要求的冲突。即使使用计数布隆过滤器，冲突仍然会导致误报。也就是说，两个字符串产生相同的散列，所以当第一个字符串被“插入”时，我们查找第二个字符串，它将显示它在那里，尽管它不是。

我认为答案是位数组，因为我们不能有假阳性。这听起来对吗？

Answer 1

我想LRU缓存就行了。因为当我们询问一个单词是否在列表中时，我们要么想要“绝对是”或者“可能不在”，或者说不允许假阳性，但是假阴性是可以的；那么即使它在列表中也可以说“很可能不在列表中”(很可能不在列表中)，如果这个单词恰好在LRU缓存中，那么它总是会回答“肯定是”。