布隆过滤器

2.布隆过滤器的分析

  布隆过滤器实质上是一种数据结构,是一种巧妙的概率型数据结构。

  作用:高效的插入和查询

  主要特点:它能告诉你这个结果 是否存在可能存在或者不存在。

  相对于list map set 的优点:高效 内存占用小,但是其返回的结果是概率性

  并不是确切的值。

  解析:布隆过滤器是一个bit数组或者说是一个bit向量

  值的映射过程:

              值在映射过程中会根据不同的hash函数生成多个hash值,将 不同的hash值指向布隆的不同bit位,当多不同的值占用相同的bit位时,会在 

             Bit位的计数所以加1,删除某个索引值得时候只需将索引值减一即可,这样

             避免了因删除某个值的bit导致另外存储到同一bit位的值找不到的情况。

  注意:布隆过滤器不易过长,拆分时尽量将一个值的bit位放在同一个bitmap 中。

  详解:https://www.jianshu.com/p/2104d11ee0a2

原文地址:https://www.cnblogs.com/wpf-7/p/12200097.html