布隆算法的原理及JAVA实现
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));
}
}
