BloomFilter——大规模数据处理利器
原文链接:http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。 实例 为了说明Bloom Filter存在的重要意义,举一个实例: 方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。 Bloom Filter的算法 废话说到这里,下面引入本篇的主角——Bloom Filter。其实上面方法4的思想已经很接近Bloom Filter了。方法四的致命缺点是冲突概率高,为了降低冲突的概念,Bloom Filter使用了多个哈希函数,而不是一个。
Bloom Filter参数选择
Bloom Filter实现代码下面给出一个简单的Bloom Filter的Java实现代码: package binggou;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class BloomFilter {
/** * BitSet初始分配2^13个bit */
private static final int DEFAULT_SIZE = 1 << 13;
/** * 不同哈希函数的种子,一般应取质数 */
private static final int[] seeds = new int[]{5,7,11,13,31,37,61};
private BitSet bits = new BitSet(DEFAULT_SIZE);
/** * 哈希函数对象 */
private SimpleHash[] func = new SimpleHash[seeds.length];
public BloomFilter() {
for (int i = 0; i < seeds.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE,seeds[i]);
}
}
// 将字符串标记到bits中
public void add(String value) {
for (SimpleHash f : func) {
bits.set(f.hash(value),true);
}
}
// 判断字符串是否已经被bits标记
public boolean contains(String value) {
if (value == null) {
return false;
}
boolean ret = true;
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
/** * 哈希函数类 */
public static class SimpleHash {
private int cap;
private int seed;
public SimpleHash(int cap,int seed) {
this.cap = cap;
this.seed = seed;
}
//hash函数,采用简单的加权和hash
public int hash(String value) {
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}
}
/** * 测试 * @param args */
public static void main(String[] args) {
String string = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
Set<String> set = new HashSet<String>();
BloomFilter bloomFilter = new BloomFilter();
Random random = new Random();
int length = 10;
// 生成随机字符串
for (int i = 0; i < 1024; i++) {
String str = "";
for (int j = 0; j < length; j++) {
str = str + string.charAt(random.nextInt(62));
}
set.add(str);
bloomFilter.add(str);
}
// 测试BloomFilter
for (int i = 0; i < 1024; i++) {
String str = "";
for (int j = 0; j < length; j++) {
str = str + string.charAt(random.nextInt(62));
}
if (set.contains(str) != bloomFilter.contains(str)) {
System.out.println("str = " + str);
}
}
}
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |