面试真题

结论：布隆过滤器是空间高效的概率集合，用多哈希位表示元素存在。要点：初始化m位数组与k独立哈希；添加：哈希对m取模置1；查询：同哈希，全1则可能存在，有0必不存在；不支持删除（计数布隆可）；误判率p≈(1-e^{-kn/m})^k，n为元素数；相比HashSet省空间但允许误判；适用于海量去重、防穿透、垃圾邮件过滤。