BF(bloom filter)学习心得
一个经典的问题：
有1000瓶药物，但是其中有一瓶是有毒的，小白鼠吃了一个星期以后就会死掉，请问，在一个星期内找出有毒的药物，最少需要多少只小白鼠？
如果一个人考虑问题是二进制的考虑方法，那么肯定好不犹豫的会说10只，为什么呢？因为小白鼠能够有两种状态，1代表生，0代表死，那么10只能表示2的10次方种状态，那么也就是说能表示1024种状态，那么答案也就是10只。关于小白鼠如何吃药，读者可以仔细去想想 :)
bloom filter实际上也是一个m位的2进制，通过hash的算法来进行映射，从而判断是否存在的一种方法。
bloom filter能够节省大量的存储空间，这个存储空间是靠牺牲准确性获得的，它有可能将一个不存在其中的值判断为在其中，所以如果工程上需要零错误时并不使用这种方法。
bloom filter缺点也很多，除了因为碰撞导致误差外，bloom filter只能判断1和0的情况，对于比较复杂的value存储，bloom filter根本办不到(Judy array可以搬到)，而且bloom filter在某种情况下，hash函数直接影响到cpu的性能，所以BF一般应用到垃圾邮件和反作弊的领域里。
bloom filter一般不单独应用，一般和某种算法结合起来应用，比如一种高压缩的存储算法《Randomized Language Models via Perfect Hash Functions》，这样降低错误率，所以使用bloom filter并不能消除错误，只能尽可能的降低误差。
发表评论