阅读时间: 8分钟

Bloom filter是一个data structure用来提升速度及记忆体使用的效率。
这个data structure是probabilistic data structure，它可以判断某个元素(element)是否在某个set内。
虽然存在误差率，有可能把不属于这个set的元素误认为属于这个set (False Positive)，
但不会把属于这个set的元素误认为不属于这个set (False Negative)。

Bloom filter的运作原理就是利用hash function对资料进行hash，然后将得的值透过mod再获到最终在资料中的位置(它的bit值会转为1)。当中可变的因素包括hash function的数目、资料的长度及资料的值。

相信大家都可能有些疑问，但不要紧，
大家可以到以下网站(英文版)即时测试一下。
https://llimllib.github.io/bloomfilter-tutorial/
网站有一个例子供大家测试:
1, 预设有一个Bloom filter，有15个index，都是empty的。

2, 可随意输入string，之后会由2个hash function执行hash，由于有2个hash function，所以最后会有2个位置的bit值会被更新为1。同时也可以看到自己的输入纪录。

3, 可以透过输入不同的string来测试一下能否输入的String是否在刚才的Set中。但值得留意的是会有误差率，即是你输入的String显示是存在刚才的Set中也不一定是真的。

既然有误差率，那又有什么作用呢?

1, Tinder内的建议选择(一般交友APP会看到)
会根据你身处的地方及个人要求作出配对，为了避免重複出现同一选择(已和你配对或已被你拒绝的对象)，系统会将已经出现的选择加入Bloom filter。这样用家就不用又再次见到相同的对象。

2, Aadhaar (Unique ID系统)
任何一个Unique ID系统都会为新的注册用户产生独一无二的号码。假如在短时间有大量用家来注册成为用户，就会为数据库带来负担。为了减轻数据库负担，可以利用Bloom filter来检查某个注册号码是否已经存在。

3, Cache优化
大家平时上网都会用到搜寻器，搜寻愈多资料就累积了愈多cache。但很多时候大部门的网页不是我们想用、想看的。进去一次就发现那些网页不合适，再不想再进去。
不过系统不管你喜不喜欢，由于cache的LRU policy的原因都会把你看过的网页资料(就算只进去一次)放进cache。时间久了，就会累积大量cache。
为了解决这个问题，可以利用Bloom filter加以优化，使cache只会储存有多于一次浏览纪录的网页资料。不会把只有一次浏览纪录的网页加入cache。

其实Bloom filter的用途可以委广泛，如果大家想再深入了解及探讨，欢迎留言或私下找我研究。