互联网人应该了解的一个数据结构Bloom Filter

先贴上已经写得非常好的一篇文章:http://blog.csdn.net/jiaomeng/article/details/1495500

Bloom Filter是一个用于标记和查找标记的一种数据结构,因为设计精妙,也有人认为它是一种算法。

它设计的大体思路是通过hash值来对一个二进制位的存储“条”上打上标记,同样判断是否已经存在时,只需要通过位运算进行匹配判断便可。

这里存在三种误判:1是因为存储空间的限制(根据使用的具体业务量计算或大致判断得出)导致可能存在多个hash值映射到了同一个(或一批:一批是指采用了拆分的方式将一个hash映射到了多个点)位置,导致误判;2是上一点中的拆分式的映射,导致位置标记覆盖速度加快,就可能存在某个hash映射到的几个点刚好是其他多个不同hash标记的点的组合;3是因为hash碰撞而导致两个字符串在Bloom Filter中存在相互误判。

这三种误判是不能完全避免的,只能是优化它,所以提取这三点中的关键部分-hash值,对其进行优化。于是,我们需要根据多套hash算法,计算出多个hash,将这些hash值都做标记,验证是否存在时,则需要所有的hash值都通过。通过这种方式,我们能很大幅度的减小误判。

因为Bloom Filter是存在误判的,所以我们只能使用于一些性能要求较高,但对准确率要求不高的场景。例如,我们可以做一个随机抽题的功能,就可以用它来标记那些已经抽过的题。