正好在“问答”和“论坛”中看到关于Bloom Filter的帖子,学习研究了一把,自娱自乐就写了一种实现。不多说,直接上代码,代码尽量写得具备可读性,不多解释了。关于Bloom Filter可以参考
http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.BitSet;
import java.util.zip.GZIPInputStream;
import java.util.zip.GZIPOutputStream;
public class BloomFilter<T extends Serializable> implements Serializable {
/**
*
*/
private static final long serialVersionUID = -4322599722288348992L;
private static final int DEFAULT_CAPACITY = 1 << 16;
private transient BitSet filter;
private HashGenerator<T> hashGenerator;
private int hashSize;
private int nbits;
public BloomFilter(HashGenerator<T> hashGenerator) {
this(hashGenerator, hashGenerator.size(), DEFAULT_CAPACITY);
}
public BloomFilter(HashGenerator<T> hashGenerator, int capacity) {
this(hashGenerator, hashGenerator.size(), capacity);
}
public BloomFilter(HashGenerator<T> hashGenerator, int hashSize, int capacity) {
super();
this.hashGenerator = hashGenerator;
this.hashSize = hashSize;
this.nbits = capacity * hashSize * 2;
filter = new BitSet(nbits);
}
private void writeObject(ObjectOutputStream out) throws IOException {
// 压缩
ByteArrayOutputStream buf = new ByteArrayOutputStream();
ObjectOutputStream objOut = new ObjectOutputStream(new GZIPOutputStream(buf));
objOut.writeObject(filter);
objOut.close();
out.writeObject(buf.toByteArray());
out.defaultWriteObject();
}
private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
byte[] buf = (byte[]) in.readObject();
ObjectInputStream objIn = new ObjectInputStream(new GZIPInputStream(
new ByteArrayInputStream(buf)));
filter = (BitSet) objIn.readObject();
objIn.close();
in.defaultReadObject();
}
public void add(T key) {
for (int i = 0; i < hashSize; i++) {
long hashCode = hashGenerator.getHashCode(key, i);
int index = hashGenerator.getBitIndex(hashCode, nbits);
filter.set(index);
}
}
public boolean contains(T key) {
for (int i = 0; i < hashSize; i++) {
long hashCode = hashGenerator.getHashCode(key, i);
int index = hashGenerator.getBitIndex(hashCode, nbits);
if (!filter.get(index))
return false;
}
return true;
}
}
import java.io.Serializable;
public interface HashGenerator<T> extends Serializable {
public int getBitIndex(long hashCode,int maxIndex);
public long getHashCode(T key, int index);
public int size();
}
import java.util.Random;
public abstract class AbstractHashGenerator<T> implements HashGenerator<T> {
/**
*
*/
private static final long serialVersionUID = 1918866698987940799L;
private static final Random rand = new Random();
private int size;
public AbstractHashGenerator(int size) {
super();
this.size = size;
}
public int getBitIndex(long hashCode, int maxIndex) {
rand.setSeed(hashCode);
return rand.nextInt(maxIndex);
}
public int size() {
return size;
}
}
public class SimpleHashGenerator<T> extends AbstractHashGenerator<T> {
/**
*
*/
private static final long serialVersionUID = -6971076063651082178L;
public SimpleHashGenerator(int size) {
super(size);
}
public SimpleHashGenerator() {
this(8);
}
private long getHashCode2(T key, int index) {
int h = index * key.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
private long getHashCode1(T key, int index) {
int h = index * 31 + key.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
public long getHashCode(T key, int index) {
return getHashCode1(key, index);
// return getHashCode2(key, index);
// if ((index & 1) == 0) {
// return getHashCode1(key, index);
// } else {
// return getHashCode2(key, index);
// }
}
}
小小测试:
import java.io.File;
import java.io.Serializable;
import bluechip.io.SerializeUtils;
public class BloomFilterTest {
static class Key implements Serializable {
/**
*
*/
private static final long serialVersionUID = 7503732767154152820L;
String name;
String id;
public Key(String name, String id) {
super();
this.name = name;
this.id = id;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#hashCode()
*/
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((id == null) ? 0 : id.hashCode());
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#equals(java.lang.Object)
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Key other = (Key) obj;
if (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "Key [id=" + id + ", name=" + name + "]";
}
}
/**
* @param args
*/
public static void main(String[] args) throws Exception {
File file = new File("d:/filter.dat");
int n = 1000000;
BloomFilter<Key> bf = null;
try {
bf = SerializeUtils.readObject(file);
} catch (Exception ex) {
bf = new BloomFilter<Key>(new SimpleHashGenerator<Key>(), n);
for (int i = 0; i < n; i++) {
bf.add(new Key("Jim", String.valueOf(i)));
}
SerializeUtils.writeObject(bf, new File("d:/filter.dat"));
}
System.out.println("==================");
for (int i = 0; i < n; i++) {
Key k = new Key("aaa", String.valueOf(i));
if (bf.contains(k)) {
System.out.println(k);
}
}
System.out.println("==================");
for (int i = 0; i < n; i++) {
Key k = new Key("Jim", String.valueOf(i));
if (!bf.contains(k)) {
System.out.println(k);
}
}
}
}
分享到:
相关推荐
Java-BloomFilter, 在Java中,一个独立的Bloom过滤器 java-bloomfilterJava bloomfilter是一个独立于Java的Bloom过滤器实现。 它旨在在不需要额外库开销的情况下包含在现有项目中。 第一个版本是由 Ian的博客条目...
这是一个java版的bloomFilter Hash函数集,并带有测试程序。在我的资源里还有一个c版的,函数功能相同,在我的应用中具有良好表现。
布隆过滤器,是一个有效利用空间的概率数据结构,用来测试一个元素是否是一个集合的成员。元素可以被添加,但不能被删除(可以用计数过滤处理)。
布隆过滤器 Java中Bloom Filter数据结构的实现。
具有JSON(反)序列化和(zlib)压缩的Java Bloomfilter实现 您可以在此处找到兼容的PYTHON实现: : 例子: BloomFilter bf1 = new BloomFilter(1000000, 0.001); bf1.add("Alabama"); bf1.add("Illinois"); bf1...
分布式环境下改进的BloomFilter过滤技术
Go中的Cuckoo Filter 实现,比 Bloom Filter 更好
NULL 博文链接:https://ansjsun.iteye.com/blog/1168722
相似项发现主题中的shingling、simhash、bloom filter算法java实现,测试通过,附带测试数据。
布隆过滤器实现 为 Java SE 8 计算 BloomFilter。用法 // capacity: 1000, error_rate: 0.001(= 0.1%)final BloomFilter<String> bf1 = new BloomFilter<>(1000, 0.01);bf.add("test");bf.contains("test"); // =...
This is the bloom filter of 2.5 Million ... BloomFilter bf=new BloomFilter(); BitSet bitSet=bf.readBit(fileName); bf.setBits(bitSet); System.out.println(bf.exist("password")); } it will says true.
redis-bloomFilter是基于redis的bitset实现的bloomfilter.具体原理和实现思路可以参考 使用 redis-bloomFilter发布在JitPack,可以选择下载源码编译,或者通过jitpack源添加依赖。 使用Maven添加依赖 添加jitpack源 ...
如何使用bloomfilter构建大型Java缓存系统Java开发Java经验技巧共5页.pdf.zip
布隆过滤器Java中布隆过滤器(概率数据结构)的实现。
提出的解决方案是用Java实现的。 Python实现可。 它包含几种用于生成独立哈希函数的方法: 双重散列 三重哈希 增强型双散列 Peter C. Dillinger和Panagiotis Manolios的“概率验证中的布鲁姆过滤器”中介绍了所有...
自己写的Java抓图程序 原理见 http://blog.csdn.net/binyao02123202/archive/2010/07/12/5728840.aspx 用了序列化 线程 和BloomFilter算法
布隆过滤器Bloom Filters的一个简单Java库
var BloomFilter = require('bloom-filter'); var bf = new BloomFilter({ elements: [1, 2, 3], p: 0.001 // default value of false positive rate }); bf.has(1) // true 原料药 建设者 BloomFilter(opts) ...
Magnus Skjegstad从Java实现中移植的内容:https://github.com/MagnusS/Java-BloomFilter Bloom过滤器是一种数据结构,旨在快速且高效地告知您元素是否存在于集合中。 它是一个概率数据结构:虽然可以肯定地告诉您...
下面小编就为大家带来一篇布隆过滤器(Bloom Filter)的Java实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧