package sunfa;
import java.util.BitSet;
import java.util.Random;
/**
* BloomFilter(布隆过滤器)
* http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html
*
*/
public class BloomFilter {
private int DEFAULT_SIZE = 1 << 6;
private BitSet bitSet = null;// java.util.BitSet的最小长度是1<<6
public BloomFilter() {
init();
}
public BloomFilter(int cmp) {
this.DEFAULT_SIZE = cmp;
init();
}
private void init() {
bitSet = new BitSet(DEFAULT_SIZE);
}
public int size() {
return bitSet.size();
}
private static int oldHash(int h) {
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
static int indexFor(int h, int length) {
return h & (length - 1);
}
public void add(Object o) {
int i = indexFor(oldHash(o.hashCode()), DEFAULT_SIZE);
bitSet.set(i);
}
public boolean contians(Object o) {
int i = indexFor(oldHash(o.hashCode()), DEFAULT_SIZE);
return bitSet.get(i);
}
public String toString() {
String s = "[";
for (int i = 0; i < bitSet.size(); i++) {
if (bitSet.get(i))
s += i + ",";
}
s += "]";
return s;
}
public static void main(String[] args) {
BloomFilter bloom = new BloomFilter();
System.out.println("bloomFilter.size:" + bloom.size());
Random ran = new Random();
int count = 100;
for (int i = 0; i < count; i++) {
int n = ran.nextInt(100);
System.out.print("before:" + n + "," + bloom.contians(n));
bloom.add(n);
System.out.println("==>after:" + n + "," + bloom.contians(n));
}
System.out.println();
System.out.println(bloom.toString());
}
//幂算法
public static int power(int b, int e) {
if (b == 0 || b == 1 || e == 0) {
return 1;
}
if (1 == e)
return b;
int n = e >> 1;
int tmp = power(b, n);
if (0 == (e & 1))
return tmp * tmp;
else
return tmp * tmp * b;
}
}
分享到:
相关推荐
Bloomfilter布隆过滤器技术分享PPT。 介绍了布隆过滤器的使用方法与适用场景等。 适合用于技术分享。
bloom filter布隆过滤器学习资料大全,收集了很多相关的论文,并总结了各种布隆过滤器的变种
自制布隆过滤器,采用八种不同哈希函数来获取随机数,错误率低
bloom filter 布隆过滤器,这是源码,简单易学易用
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
硬核 - Redis 布隆(Bloom Filter)过滤器原理与实战.doc
布隆过滤器C源码
布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数,查找元素类型,三个...
布隆过滤器Bloom Filters的一个简单Java库
C++实现的布隆过滤器,其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否...
使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,
布隆过滤器的一个Go实现,参考bloomfilter.js
bloomfilter布隆过滤器 海量数据处理
布隆去重工具类,感兴趣的了解一下。
布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用
主要介绍了布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下
NULL 博文链接:https://ansjsun.iteye.com/blog/1168722
用于 JavaScript 的布隆过滤器。 用法 const bfilter = require ( 'bfilter' ) ; 贡献和许可协议 如果你向这个项目贡献代码,你就隐含地允许你的代码在 MIT 许可下分发。 您还隐式验证所有代码都是您的原创作品。 ...
布隆过滤器是一种数据结构,主要用于判断一个元素是否可能在一个集合中存在。它可以在插入和查询数据时快速地判断一个元素是否可能在这个集合中,比如在缓存中查询一个元素是否存在。 它的原理是使用多个哈希函数对...
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多...