Pin*_*ead 8 algorithm bloom-filter
从面试问题:
"确定一个单词是否在存储列表中.该列表不适合内存.不允许磁盘访问,仅用于查找,仅允许内存访问.不允许误报,假阴性可以."
Bloom过滤器完全相反:允许误报,不允许误报.
我的想法:我们不能使用哈希函数,因为我们可能会发生违反"无误报"要求的冲突.即使使用计数布隆过滤器,碰撞仍会导致误报.IE两个字符串会产生相同的哈希值,所以当第一个字符串被"插入"时,我们对第二个字符串进行查找,它会显示它在那里,尽管它没有.
我认为答案有点阵,因为我们不能有误报.听起来不错吗？
小智 3
我认为 LRU 缓存就可以了。因为当我们询问一个单词是否在列表中时，我们要么想要“肯定是”或“可能不是”，要么说相反，不允许误报，但误报也可以；那么就可以说“可能不在列表中”，即使它在那里（可能不在），如果这个词恰好在 LRU 缓存中，那么它总是会回答“肯定是”