位图与Bloom过滤器

本文主要是介绍位图与Bloom过滤器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

位图

  位图常用在给定一个很大范围的数，判断某个数是否在其中。BitSet是位操作的对象，值只有0或1（即true 和 false），内部维护一个long数组，初始化只有一个long segement，所以BitSet最小的size是64；随着存储的元素越来越多，BitSet内部会自动扩充，一次扩充64位，最终内部是由N个long segement 来存储。默认情况下，BitSet所有位都是0即false；基本原理是，用1位来表示一个数据是否出现过，0为没有出现过，1表示出现过。使用用的时候既可根据某一个是否为0表示此数是否出现过。
  例如有四十亿个数，一个int型的数字是4个字节，32个比特位，如果把每一个比特位标志一个数字，那一个字节就可以标记32个数字(注意：位图不存放这些数据，只是标记是否存在，位图中的数组存放的是二进制数字0或者1)。40亿个数字大概就是16G，而现在使用位图16G/32大约就是500M左右，不光节省内存，也同时提高了效率。

void SetBit(size_t x){size_t index = x >> 5;size_t num = x % 32;_bitTable[index] |= (1 << num);}

  JDK选择long数组作为BitSet的内部存储结构而不用不用int是出于性能的考虑，因为BitSet提供and和or这种操作，需要对两个BitSet中的所有bit位做and或者or，实现的时候需要遍历所有的数组元素。使用long能够使得循环的次数降到最低，所以Java选择使用long数组作为BitSet的内部存储结构。

Bloom过滤器

  Bloom过滤器主要用于快速从海量数据中找出某个成员是否属于这个集合。因为Bloom Filter使用位数组和哈希函数来表征集合，并不需要存储集合数据本身内容，所以其空间利用率非常高。

基本思想：
  布隆过滤器是一个bit 数组，如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1。对于集合S中的某个成员a，分别使用k个哈希函数对其进行计算，如果 H i（a）=x(1<=i<=k,1<=x<=m),则将位数组的第x 位置为1，

查询：
  当查询某个成员a是否在集合S中出现时，使用相同的k个哈希函数计算，如果其对应位置全部为1，则a属于集合S，只要有一个位置为0，则a 不属于集合S。

误判率及相关计算：
  为什么会发生误判： 假如此时查询X3这个元素是否属于集合，通过3个哈希函数计算后的位置数为 2,7,11，而这时这3个位置都为1，BF会认为X3属于集合，但可能此时这3个位置的1是其他元素对应的，就发生误判了。

影响误判率的因素：

1. 集合大小n
   因为集合n越大，其它条件固定的情况下，位数组中就会有更多比例的位置被设成1，误判率就会增大。
2. 哈希函数的个数k
   个数越多，位数组中更多比例的位置被设置为1，即增大了误判率。但在查询时，显然个数越多的时候误判率会越低。
3. 位数组的大小m
   位数组大小m越大，那么n和k固定的情况下，位数组中剩余0的比特位就越高，误判率就会减小。

这篇关于位图与Bloom过滤器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---