布隆过滤器

如果一个接口被大量查询不存在的数据，比如用户不断请求不存在的商品 ID、缓存里没有的用户 ID，系统很容易被拖进一个尴尬局面：缓存没命中，请求继续打到数据库；数据库查不到，下一次同样的请求又会重复发生。 这类问题的关键不是“如何更快地查到数据”，而是先回答一个更便宜的问题：这个东西是不是一定不存在？ 布隆过滤器解决的正是这个问题。它不能像哈希集合那样给出完全精确的答案，但它能用很少的内存，在极快的时间内告诉你： 如果结果是“不存在”，那它一定不存在。 如果结果是“存在”，那它只是可能存在。 这个“可能”就是布隆过滤器最重要的取舍。它用少量误判，换来了很高的空间效率。 先从一个普通集合说起 假设我们要记录 1 亿个已经注册过的用户 ID，最直接的做法是把这些 ID 放进一个集合： registered_users = set() registered_users.add("user:10086") if "user:10086" in registered_users: print("exists") 这个方案很好理解，也很精确。但问题是：集合为了支持快速查询，通常不只存储原始元素，还要维护哈希表、桶、指针、扩容状态等额外结构。数据量一大，内存会明显上去。 如果我们的目标只是提前过滤掉明显不存在的请求，真的需要保存完整的字符串吗？ 布隆过滤器的答案是：不需要。它只保存一些 bit。 布隆过滤器的直觉 可以把布隆过滤器想成一个很大的位图，也就是一串只包含 0 和 1 的数组： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 普通位图通常要求元素能直接映射成整数位置，比如数字 13 就对应第 13 个 bit。但现实里的元素可能是字符串、URL、邮箱、订单号，不一定能直接当数组下标。 布隆过滤器在中间加了一层哈希函数。 对于一个元素，它不用一个位置表示，而是用多个哈希函数算出多个位置： element = "user:10086" hash1(element) -> 3 hash2(element) -> 9 hash3(element) -> 14 插入这个元素时，就把这些位置都置为 1： ...