Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

比如10亿个int类型的数,如果用int数组存储的话,那么需要大约4G内存,浪费内存。如果用bitmap解决,就比较方便。java语言中没有bitmap结构,我们采用byte模拟。一个byte占8个bit,如果每一个bit的值是1或0,代表有或没有。下图所示:

构建特定长度的byte数组(new byte[capacity/8 + 1]),其中capacity为整数数组长度(如:1000个数字,就是1000/8)

byte[] bits = new byte[capacity/8 + 1];

计算数字num在byte[]中的位置索引(num/8和num >> 3一样),也就是说num在byte[k]中的索引,计算索引k

    /**
     * num/8得到byte[]的index
     * @param num
     * @return
     */
    public int getIndex(int num){
        return num >> 3;
    }

计算数字num在byte中的位置,就是在byte的第几位,每个byte有8位(num % 8),采用二进程与计算

   /**
     * num%8得到在byte[index]的位置
     * @param num
     * @return
     */
    public int getPosition(int num){
        return num & 0x07;
    }

找到该数字存储位置后,将bit中的0变成1,即表示该数已存在bitmap中,如图

   /**
     * 标记指定数字(num)在bitmap中的值,标记其已经出现过
     * 将1左移position后,那个位置自然就是1,然后和以前的数据做|(或运算),这样,那个位置就替换成1了
     * @param bits
     * @param num
     */
    public void add(byte[] bits, int num){
        bits[getIndex(num)] |= 1 << getPosition(num);
    }

判断指定数字num是否存在数组中

   /**
     * 判断指定数字num是否存在<br/>
     * 将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可
     * @param bits
     * @param num
     * @return
     */
    public boolean contains(byte[] bits, int num){
        return (bits[getIndex(num)] & 1 << getPosition(num)) != 0;
    }

完整代码:

public class Bitmap {

   private final int capacity;

   private final byte[] bytes;

   /**
    * 初始bit数组的容量
    * capacity/8 等于 capacity>>2
    * @author guobingbing
    * @date 2019/9/15 10:36
    * @param capacity
    * @return
    */
   public Bitmap(int capacity){
      if(capacity<=0){
         capacity = Integer.MAX_VALUE;
      }
      this.capacity = capacity;
      int len = (this.capacity>>3) + 1;
      System.out.println("The bytes length is " + len + ".");
      bytes = new byte[len];
   }

   /**
    * 计算num在bt数组中的索引
    * 因为bit数组的容量为capacity>>3+1,所以元数在数组中的位置也是num>>3
    * @author guobingbing
    * @date 2019/9/15 10:27
    * @param num
    * @return int
    */
   public int getBytesIndex(int num){
      return num>>3;
   }

   /**
    * 计算num在bt[index]中的位置,因为每个bt[index]有8个bit位,所以就是num%8
    * 这里采用与运算,速度快。0x07对应的二进制形式 111
    * @author guobingbing
    * @date 2019/9/15 10:43
    * @param num
    * @return int
    */
   public int getBitsPosition(int num){
      return num & 0x07;
   }

   /**
    * 将数字添加到bits数组中
    * 1、计算num在bytes数组的位置
    * 2、计算num在bit中的位置,1Byte=8bit
    * 3、
    * @author guobingbing
    * @date 2019/9/15 11:22
    * @param num
    * @return int
    */
   public int add(int num){
      int index = this.getBytesIndex(num);
      int position = 1 << this.getBitsPosition(num);
      return bytes[index] |= position;
   }

   /**
    * 判断bytes数组中是否存在num
    * @author guobingbing
    * @date 2019/9/15 13:04
    * @param num
    * @return boolean
    */
   public boolean contains(int num){
      int index = this.getBytesIndex(num);
      int position = 1 << this.getBitsPosition(num);
      return (this.bytes[index] & position) != 0;
   }

   /**
    * 获取数组的长度
    * @author guobingbing
    * @date 2019/9/15 13:10
    * @param
    * @return int
    */
   public int size(){
      return bytes.length;
   }

   /**
    * 清除bytes中的数据
    * @author guobingbing
    * @date 2019/9/15 13:07
    * @param num
    * @return void
    */
   public void clear(int num){
      int index = this.getBytesIndex(num);
      int position = ~(1 << this.getBitsPosition(num));
      bytes[index] &= position;
   }

   public static void main(String[] args) {
      //System.out.println(1<<2);
      //System.out.println(24>>3);

      int addCount = 0;
      Bitmap bitmap = new Bitmap(10000);
      for(int i=1; i<=10000; i++){
         if(i%2==0) {
            bitmap.add(i);
            addCount++;
         }
      }
      System.out.println("addCount is " + addCount);

      int containsCount = 0;
      for(int i=1; i<=10000; i++){
         if(bitmap.contains(i)){
            containsCount++;
         }
      }
      System.out.println("containsCount is " + containsCount);
      //System.out.println(bitmap.contains(89));
      //System.out.println(bitmap.contains(10002));
   }
}

发表评论