抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

57 | 理论讲解:布隆过滤器

布隆过滤器 Bloom Filter

⼀个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否在⼀个集合中。

它的优点是空间效率和查询时间都远超(基于二进制位处理)过⼀般的算法,缺点是有一定的误识别率和删除困难。

重点:当查询不存在时是一定不存在(100%不存在),当查询时存在不一定存在(存在误判),所以根据这点,可以用做第一道墙。

使用二进制位进行标识:

图中的 B 元素是不错在的,但是判断上是存在的(误判例子)。

案例

  1. ⽐特币网络
    Redis VS BloomFilter
  2. 分布式系统(Map-Reduce)

比特币网络示例图:关注 SPV 节点

SPV 节点:可以很快的判断一个交易是否存在,就是使用的 BloomFilter,因为不存在则一定不存在,存在的话再去查(区块查起来是比较慢的,加上这一层可以加速查找)

分布式系统:比如 Map-Reduce


0条评论

发表评论