Java实现的Bloom Filter
Java实现简单的Bloom Filter
布隆过滤器在信息去重，比如网页的去重、邮件去重以及URL去重上很常用，其原理也相对简单，主要是通过多个哈希函数来设置bit位作为某条记录的指纹，查询和空间效率都非常不错。
一、基本原理
这篇博客讲的非常好，我就不再狗尾续貂了：
http://www.cnblogs.com/haippy/archive/2012/07/13/2590351.html
简单来说，就是对数据库中的记录$X，Y，Z$分别使用多个（图中为3个）哈希函数，映射到对应的比特位，将比特位置1，如果下一个数据使用相同三个哈希后对应的比特位全为1，则该数据已存在数据库中。
推导结论为(m为bit位个数，n为待添加的记录数，p为冲突概率)
如果已经限定了bitset容量和待添加的记录数，则最优的哈希函数的个数k为
此时冲突率为：
如果已经限定了冲突概率，则bit数组的大小最优为：
二、构造函数
public class Bloomfilter { private BitSet bitSet; private int bitSetSize; private int addedElements; private int hashFunctionNumber; /** * 构造一个布隆过滤器，过滤器的容量为c * n 个bit. * @param c 当前过滤器预先开辟的最大包含记录,通常要比预计存入的记录多一倍. * @param n 当前过滤器预计所要包含的记录. * @param k 哈希函数的个数，等同每条记录要占用的bit数. */ public Bloomfilter(int c, int n, int k) { this.hashFunctionNumber = k; this.bitSetSize = (int) Math.ceil(c * k); this.addedElements = n; this.bitSet = new BitSet(this.bitSetSize); }通常我们要预设一个相对大一点的bit空间，这样冲突才会比较小，哈希函数的数量K也是越多越好，但是通常8个以上就行了，要看能接受的冲突阈值。
代码中也提供了获得当前冲突率的函数。
三、完整代码
完整代码包括两个类，一个哈希函数库（从网上搜的8个hash函数），和过滤器类：
package crawler.analysis; import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.BitSet; import java.util.List; public class Bloomfilter { private BitSet bitSet; private int bitSetSize; private int addedElements; private int hashFunctionNumber; /** * 构造一个布隆过滤器，过滤器的容量为c * n 个bit. * @param c 当前过滤器预先开辟的最大包含记录,通常要比预计存入的记录多一倍. * @param n 当前过滤器预计所要包含的记录. * @param k 哈希函数的个数，等同每条记录要占用的bit数. */ public Bloomfilter(int c, int n, int k) { this.hashFunctionNumber = k; this.bitSetSize = (int) Math.ceil(c * k); this.addedElements = n; this.bitSet = new BitSet(this.bitSetSize); } /** * 通过文件初始化过滤器. * @param file */ public void init(String file) { BufferedReader reader = null; try { reader = new BufferedReader(new FileReader(file)); String line = reader.readLine(); while (line != null && line.length() > 0) { this.put(line); line = reader.readLine(); } } catch (Exception e) { e.printStackTrace(); } finally { try { if (reader != null) reader.close(); } catch (IOException e) { e.printStackTrace(); } } } public void put(String str) { int[] positions = createHashes(str.getBytes(), hashFunctionNumber); for (int i = 0; i < positions.length; i++) { int position = Math.abs(positions[i] % bitSetSize); bitSet.set(position, true); } } public boolean contains(String str) { byte[] bytes = str.getBytes(); int[] positions = createHashes(bytes, hashFunctionNumber); for (int i : positions) { int position = Math.abs(i % bitSetSize); if (!bitSet.get(position)) { return false; } } return true; } /** * 得到当前过滤器的错误率. * @return */ public double getFalsePositiveProbability() { // (1 - e^(-k * n / m)) ^ k return Math.pow((1 - Math.exp(-hashFunctionNumber * (double) addedElements / bitSetSize)), hashFunctionNumber); } /** * 将字符串的字节表示进行多哈希编码. * @param bytes 待添加进过滤器的字符串字节表示. * @param hashNumber 要经过的哈希个数. * @return 各个哈希的结果数组. */ public static int[] createHashes(byte[] bytes, int hashNumber) { int[] result = new int[hashNumber]; int k = 0; while (k < hashNumber) { result[k] = HashFunctions.hash(bytes, k); k++; } return result; } public static void main(String[] args) throws Exception { Bloomfilter bloomfilter = new Bloomfilter(30000000, 10000000, 8); System.out.println("Bloom Filter Initialize ... "); bloomfilter.init("data/base.txt"); System.out.println("Bloom Filter Ready"); System.out.println("False Positive Probability : " + bloomfilter.getFalsePositiveProbability()); // 查找新数据 List<String> result = new ArrayList<String>(); long t1 = System.currentTimeMillis(); BufferedReader reader = new BufferedReader(new FileReader("data/input.txt")); String line = reader.readLine(); while (line != null && line.length() > 0) { if (!bloomfilter.contains(line)) { result.add(line); } line = reader.readLine(); } reader.close(); long t2 = System.currentTimeMillis(); System.out.println("Parse 9900000 items, Time : " + (t2 - t1) + "ms , find " + result.size() + " new items."); System.out.println("Average : " + 9900000 / ((t2 - t1) / 1000) + " items/second"); } } class HashFunctions { public static int hash(byte[] bytes, int k) { switch (k) { 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); } return 0; } public static int RSHash(byte[] bytes) { int hash = 0; int magic = 63689; int len = bytes.length; for (int i = 0; i < len; i++) { hash = hash * magic + bytes[i]; magic = magic * 378551; } return hash; } public static int JSHash(byte[] bytes) { int hash = 1315423911; for (int i = 0; i < bytes.length; i++) { hash ^= ((hash << 5) + bytes[i] + (hash >> 2)); } return hash; } public static int ELFHash(byte[] bytes) { int hash = 0; int x = 0; int len = bytes.length; for (int i = 0; i < len; i++) { hash = (hash << 4) + bytes[i]; if ((x = hash & 0xF0000000) != 0) { hash ^= (x >> 24); hash &= ~x; } } return hash; } public static int BKDRHash(byte[] bytes) { int seed = 131; int hash = 0; int len = bytes.length; for (int i = 0; i < len; i++) { hash = (hash * seed) + bytes[i]; } return hash; } public 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; } public static int DJBHash(byte[] bytes) { int hash = 5381; int len = bytes.length; for (int i = 0; i < len; i++) { hash = ((hash << 5) + hash) + bytes[i]; } return hash; } public static int SDBMHash(byte[] bytes) { int hash = 0; int len = bytes.length; for (int i = 0; i < len; i++) { hash = bytes[i] + (hash << 6) + (hash << 16) - hash; } return hash; } public static int PJWHash(byte[] bytes) { long BitsInUnsignedInt = (4 * 8); long ThreeQuarters = ((BitsInUnsignedInt * 3) / 4); long OneEighth = (BitsInUnsignedInt / 8); long HighBits = (long) (0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); int hash = 0; long test = 0; for (int i = 0; i < bytes.length; i++) { hash = (hash << OneEighth) + bytes[i]; if ((test = hash & HighBits) != 0) { hash = (int) ((hash ^ (test >> ThreeQuarters)) & (~HighBits)); } } return hash; } }直接运行代码，可以得到：
Bloom Filter Initialize ... Bloom Filter Ready False Positive Probability : 4.169085162009671E-5 Parse 9900000 items, Time : 17288ms , find 100 new items. Average : 582352 items/second正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
