一：百科：
（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。
如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢。
二：布隆过滤器原理
布隆过滤器需要的是一个位数组（这个和位图有点类似）和k个映射函数（和Hash表类似），在初始状态时，对于长度为m的位数组array，它的所有位都被置为0。对于有n个元素的集合S={s1,s2……sn}，通过k个映射函数{f1,f2,……fk}，将集合S中的每个元素sj(1<=j<=n)映射为k个值{g1,g2……gk}，然后再将位数组array中相对应的array[g1],array[g2]……array[gk]置为1；如果要查找某个元素item是否在S中，则通过映射函数{f1,f2…..fk}得到k个值{g1,g2…..gk}，然后再判断array[g1],array[g2]……array[gk]是否都为1，若全为1，则item在S中，否则item不在S中。这个就是布隆过滤器的实现原理。
三：优点和缺点
它的优点是空间效率和查询时间都远远超过一般的算法，布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。另外, 散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势,缺点是有一定的误识别率。
四：应用
例如一个千万级别的app, 用户当天登录了就算一次pv, 当天后面的点击就不再计算了，显然下次要过滤点，一般的就是通过数据库中是否有记录来判断，我们可以利用布隆过滤器，高效的判断该设备是否记录过。
static BloomFilter bloomFilter = new BloomFilter(5000000, 1000000, 8);
if(bloomFilter.contains(token)){
//exist
}
package util;
import java.util.BitSet;
import java.util.concurrent.atomic.AtomicInteger;
/**
* 布隆过滤器
*
*/
public class BloomFilter {
private BitSet bits;
private int size;
private AtomicInteger realSize = new AtomicInteger(0);
private int addedElements;
private int hashFunctionNumber;
/**
* 构造一个布隆过滤器，过滤器的容量为c * n 个bit.
*
* @param c 当前过滤器预先开辟的最大包含记录,通常要比预计存入的记录多一倍.
* @param n 当前过滤器预计所要包含的记录.
* @param k 哈希函数的个数，等同每条记录要占用的bit数.
*/
public BloomFilter(int c, int n, int k) {
if (k > 10)
throw new IllegalArgumentException("Illegal k(maximum is 8): " + k);
this.hashFunctionNumber = k;
this.size = (int) Math.ceil(c * k);
this.addedElements = n;
this.bits = new BitSet(size);
}
/**
* 写入Bloom过滤器
*
* @param str 缓存字符串
*/
public void put(String str) {
realSize.incrementAndGet();
byte[] bytes = str.getBytes();
int[] positions = createHashes(bytes, hashFunctionNumber);
for (int position1 : positions) {
int position = Math.abs(position1 % size);
bits.set(position, true);
}
}
/**
* Bloom过滤器是否包含对应的字符串
*
* @param str 字符串对象
* @return true表示包含
*/
public boolean contains(String str) {
byte[] bytes = str.getBytes();
int[] positions = createHashes(bytes, hashFunctionNumber);
for (int i : positions) {
int position = Math.abs(i % size);
if (!bits.get(position)) {
return false;
}
}
return true;
}
/**
* 得到当前过滤器的错误率.
*
* @return 错误率
*/
public double getFalsePositiveProbability() {
return Math.pow((1 - Math.exp(-hashFunctionNumber * (double) addedElements / size)),
hashFunctionNumber);
}
public int getSize(){
return size;
}
public int getRealSize(){
return realSize.get();
}
private int[] createHashes(byte[] bytes, int hashFunctionNumber) {
int[] result = new int[hashFunctionNumber];
for (int i = 0; i < hashFunctionNumber; i++) {
result[i] = HashFunctions.hash(bytes, i);
}
return result;
}
static class HashFunctions {
static int hash(byte[] bytes, int index) {
switch (index) {
case 0:
return RSHash(bytes);
case 1:
return JSHash(bytes);
case 2:
return ELFHash(bytes);
case 3:
return BKDRHash(bytes);
case 4:
return APHash(bytes);
case 5:
return DJBHash(bytes);
case 6:
return SDBMHash(bytes);
case 7:
return PJWHash(bytes);
}
throw new IllegalArgumentException("Invalid index: " + index);
}
static int RSHash(byte[] bytes) {
int hash = 0;
int magic = 63689;
for (byte b : bytes) {
hash = hash * magic + b;
magic = magic * 378551;
}
return hash;
}
static int JSHash(byte[] bytes) {
int hash = 1315423911;
for (byte b : bytes) {
hash ^= ((hash << 5) + b + (hash >> 2));
}
return hash;
}
static int ELFHash(byte[] bytes) {
int hash = 0;
int x;
for (byte b : bytes) {
hash = (hash << 4) + b;
if ((x = hash & 0xF0000000) != 0) {
hash ^= (x >> 24);
hash &= ~x;
}
}
return hash;
}
static int BKDRHash(byte[] bytes) {
int seed = 131;
int hash = 0;
for (byte b : bytes) {
hash = (hash * seed) + b;
}
return hash;
}
static int APHash(byte[] bytes) {
int hash = 0;
int len = bytes.length;
for (int i = 0; i < len; i++) {
if ((i & 1) == 0) {
hash ^= ((hash << 7) ^ bytes[i] ^ (hash >> 3));
} else {
hash ^= (~((hash << 11) ^ bytes[i] ^ (hash >> 5)));
}
}
return hash;
}
static int DJBHash(byte[] bytes) {
int hash = 5381;
for (byte b : bytes) {
hash = ((hash << 5) + hash) + b;
}
return hash;
}
static int SDBMHash(byte[] bytes) {
int hash = 0;
for (byte b : bytes) {
hash = b + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
static int PJWHash(byte[] bytes) {
long bitsInUnsignedInt = (4 << 3);
long threeQuarters = ((bitsInUnsignedInt * 3) >> 2);
long oneEighth = (bitsInUnsignedInt >> 3);
long highBits = (long) (0xFFFFFFFF) << (bitsInUnsignedInt - oneEighth);
int hash = 0;
long test;
for (byte b : bytes) {
hash = (hash << oneEighth) + b;
if ((test = hash & highBits) != 0) {
hash = (int) ((hash ^ (test >> threeQuarters)) & (~highBits));
}
}
return hash;
}
}
public static void main(String[] args) {
BloomFilter bloomFilter = new BloomFilter(5000000, 3000000, 8);
System.out.println(bloomFilter.getFalsePositiveProbability());
Runtime rt = Runtime.getRuntime();
//空闲内存：
long free = Runtime.getRuntime().freeMemory();
//总内存：
long total = Runtime.getRuntime().totalMemory();
//已占用的内存：
long userd = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
// System.out.println("最大可用内存：" + rt.maxMemory()/1024/1024 + " M");
// System.out.println("空闲内存：" + free/1024/1024 + " M");
// System.out.println("总内存：：" + total/1024/1024 + " M");
// System.out.println("已占用的内存：：：" + userd/1024/1024 + " M");
}
}
