package com.spider;
import java.util.BitSet;
public class BloomFilter {
private int defaultSize = 2 << 24;
private int basic = defaultSize - 1;
private BitSet bits;
public BloomFilter() {
bits = new BitSet(defaultSize);
}
public boolean contains(String url) {
if (url == null) {
return true;
}
int pos1 = hash1(url);
int pos2 = hash2(url);
int pos3 = hash3(url);
if (bits.get(pos1) && bits.get(pos2) && bits.get(pos3)) {
return true;
}
return false;
}
public void add(String url) {
if (url == null) {
return;
}
int pos1 = hash1(url);
int pos2 = hash2(url);
int pos3 = hash3(url);
bits.set(pos1);
bits.set(pos2);
bits.set(pos3);
}
private int hash3(String line) {
int h = 0;
int len = line.length();
for (int i = 0; i < len; i++) {
h = 37 * h + line.charAt(i);
}
return check(h);
}
private int hash2(String line) {
int h = 0;
int len = line.length();
for (int i = 0; i < len; i++) {
h = 33 * h + line.charAt(i);
}
return check(h);
}
private int hash1(String line) {
int h = 0;
int len = line.length();
for (int i = 0; i < len; i++) {
h = 31 * h + line.charAt(i);
}
return check(h);
}
private int check(int h) {
return basic & h;
}
public void test() {
String url = "http://www.pp.tv";
System.out.println(contains(url));
add(url);
System.out.println(contains(url));
}
public static void main(String arg[]) {
BloomFilter bf = new BloomFilter();
bf.test();
}
}
分享到:
相关推荐
使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,
基于布隆过滤器和聚簇技术的大规模WSN服务发现算法,薛寒寒,王柏,针对大规模WSN节点资源受限,难以快速、准确、节能的进行服务发现问题,提出一种基于布隆过滤器BF(bloom filter)和聚簇技术的大规模W
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多...
本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。 相比于传统的 Set、...
bloom_filter_code [布隆过滤器] 1: bloom 布隆过滤器 consistent_hash_code [一致性Hash算法] 1: consistent 一致性Hash算法 leet_code [leet_code刷题] 1: leet_code刷题 heap [堆] 1: max_heap_test 大顶推 ...
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,...
用于 JavaScript 的布隆过滤器。 用法 const bfilter = require ( 'bfilter' ) ; 贡献和许可协议 如果你向这个项目贡献代码,你就隐含地允许你的代码在 MIT 许可下分发。 您还隐式验证所有代码都是您的原创作品。 ...
布隆过滤器可以说是在大数据的处理算法方面经常使用的基础算法。 在这方面我看了很多的博客,确实看到了很多很详细的解释和总结,但是都是零散的,没有很全面的在原理和实现,以及实现代码的解析等方面做的很全面的...
经研究,提出采用改进的布隆过滤器(Bloom filter)对RFID采集数据进行去重过滤,并运用到中间件系统中。改进的Bloom filter主要将两个标准的Bloom filter组成二维并行Bloom filter,对RFID采集数据所包含的两个属性...
逆布隆过滤器逆布隆过滤器,或“布隆过滤器的反面”,是一种并发的概率数据结构,用于测试一个项目是否被观察到。 这是一个 Go 实现,,它用非加密 FNV-1a 函数代替了 MD5 散列的使用。 反向过滤器可能会报告误报,...
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远超过一般的算法,...
bloom filter(布隆过滤器)应用很广泛的高效算法,研究研究
针对该问题,提出了采用Bloom Filter(布隆过滤器)进行字符串模糊匹配方式,利用Bloom Filter将信息流中大部分正常流量过滤掉,从而减轻了后端的字符串精确匹配的压力,降低了系统功耗,大大提高了处理速度。
随着互联网的发展,网络信息呈爆炸...布隆过滤器(Bloom Filter)是 1970年提出的一种去重算法,它实际上是由一个很长的二进制向量和一系列随机映射函数组成的,拥有查询速度快和占用空间低的优点,然而其存在一定的误识别率
针对确定有限自动机(DFA)的正则表达式匹配技术存在状态膨胀和一次状态转移只能处理单个字符的问题,提出了一种基于布鲁姆过滤器的正则表达式匹配算法。该算法将正则表达式中的每个确定字符串组成DFA的一个状态,...
布隆过滤器是大数据领域的一个常见算法,它的目的是过滤掉那些不是目标的元素。也就是说如果一个要搜索的词并不存在于我的数据中,那么它可以以很快的速度返回目标不存在。 让我们看看以下布隆过滤器的代码: 1...
针对现有云存储系统中数据去重采用的收敛加密算法容易遭到暴力破解以及猜测攻击等不足,提出一种基于布隆过滤器的混合云存储安全去重方案BFHDedup,改进现有混合云存储系统模型,私有云部署密钥服务器Key Server支持...
隆过滤器是Burton Howard Bloom在1970年提出来的,一种空间效率极高的概率型算法和数据结构,主要用来 判断一个元素是否在集合中存在。因为他是一个概率型的算法,所以会存在一定的误差,如果传入一个值去布隆过 ...