布隆过滤器(一)——布隆过滤器的原理和理解_java实现布隆过滤器,并且如何减少哈希碰撞的概率

布隆过滤器系列
（一）布隆过滤器的原理和理解
（二）Java布隆过滤器实现

一、背景

布隆过滤器（BloomFilter）在1970年由布隆提出，用于检测一个元素是否存在于某个特定的集合中，它有一定的误判几率。

实际上，在数据量不大时，我们并没有使用布隆过滤器的必要，只需要创建一个集合，然后扫描集合的内容进行比较即可清楚某数据是否存在。但是在数据量非常大时，每次扫描就会消耗太多的资源，这时，有一种机制能够提前过滤就显得很重要了，即便它有一定的误判概率。

之前文章中有简要说过Redis的缓存穿透、缓存击穿等问题（Redis缓存问题），事实上，布隆过滤器也常常和Redis等工具一起使用，用于避免上述问题的出现。

二、原理

布隆过滤器不是使用链表、树等结构，而是使用散列（哈希表）的数据结构，它的机制是将元素映射成一个位阵列中的点，这样一来，需要判断一个元素是否存在，也就只需要判断某个点是否为1即可。当然，遇到hash碰撞时，就会发生误判。所以为了降低误判的概率，我们采用多个Hash，这样一来哈希碰撞的概率也能够大幅降低。

三、对于“可能存在”和“不可能存在”的理解

我们现在将mysql中的内容放入一个全新的布隆过滤器中，将对应数据的hash点更改成1。这时，当出现一个新的内容需要判断是否存在于mysql中时，我们先进行hash，如果hash后的值对应的点在布隆过滤器中有任何一处不为1，那么该值就一定不可能存在于mysql中；反之，如果查找布隆过滤器中的值全部都为1了，那么它有可能存在于mysql中，也有可能只是偶然情况发生了哈希碰撞。