布隆过滤器

布隆过滤器（Bloom Filter）在实际生产环境中主要用于“判断一个元素是否存在于大数据量的集合中”。 其底层算法的核心逻辑主要由两大部分组成：第一部分是精心设计并构造 K 个哈希函数即大小为 N 的位数组，并设置数组每个元素的初始值为 0；第二部分是判断一个元素是否存在于大数量的集合时，需要将该元素经过 K 个哈希函数的计算得出 K 个哈希值，并判断位数组对应的下标的元素取值是否为 1，如果都为 1，则元素有很大概率是存在的，而只要有一个对应的数组元素不为 1，则代表该元素一定不存在与集合中。

布隆过滤器还可以充当“Redis 缓存击穿”的解决方案。因为“缓存击穿”的产生是有前端不断地请求一定不存在与缓存中的数据，而导致大量的请求落地到 DB 上，从而造成数据库服务器的压力暴增所引起的。而布隆过滤器正是用于高效地判断一个元素是否存在于集合中，因而可以将布隆过滤器应用于 Redis 的缓存击穿中。