`
woshizn
  • 浏览: 209748 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

布隆过滤器 布隆算法 BloomFilter

阅读更多
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实现的布隆过滤器算法

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否在一个集合中。它可能会误判,但不会漏判,即如果它说一个元素在集合中,那可能是错误的,但如果它说一个元素不在集合中,那么...

    bloom filter布隆过滤器学习资料大全

    布隆过滤器(Bloom Filter)是一种空间效率极高...通过这个“bloom filter布隆过滤器学习资料大全”,你可以深入研究布隆过滤器的理论、算法实现以及在不同场景下的应用实例,提升对这一重要数据结构的理解和应用能力。

    PDD–基于高级布隆过滤器算法用于高效得删除数据流中的近似重复数据

    首先,我们要理解什么是布隆过滤器(Bloom Filter)。布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它可能会误判,即可能将不存在的元素判断为存在,但不会漏掉真正存在的...

    9 Redis布隆过滤器插件安装.zip

    Redis布隆过滤器插件是Redis数据库中一个非常实用的扩展功能,主要用于高效地判断一个元素是否可能存在于集合中。由于其独特的数据结构和算法,它在存储空间和查询效率之间取得了良好的平衡,尤其适用于大数据场景下...

    布隆过滤器

    布隆过滤器是一种概率型数据结构,用于判断一个元素是否可能在一个集合中存在。它由布伦南·布隆在1970年提出,主要应用于大数据存储和检索,尤其是在空间效率和查询效率方面有着显著优势。由于布隆过滤器会存在一定...

    大文件去重 布隆算法

    最后,"BloomFilter"可能是一个源代码文件夹,包含了布隆过滤器的实现代码。 综合这些文件,我们可以推测这是一个使用C#或.NET开发的布隆过滤器实现,包含了源码、测试和构建配置。通过阅读源代码和执行测试,我们...

    Python+Redis实现布隆过滤器

     布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多...

    python实现布隆过滤器及原理解析

    本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。 相比于传统的 Set、...

    分布式爬虫应用中布隆过滤器的研究.docx

    为了解决URL去重问题,提高爬虫的检索效率,布隆过滤器(Bloom Filter)成为了一种理想的解决方案。布隆过滤器是一种概率型数据结构,它能够在有限的空间内高效地判断一个元素是否可能存在于某个集合中,虽然存在...

    algorithm_coding:推荐算法、相似度算法、布隆过滤器、均值算法、一致性Hash、数据结构、leetcode练习

    bloom_filter_code [布隆过滤器] 1: bloom 布隆过滤器 consistent_hash_code [一致性Hash算法] 1: consistent 一致性Hash算法 leet_code [leet_code刷题] 1: leet_code刷题 heap [堆] 1: max_heap_test 大顶推 ...

    网络安全事件关联分析系统设计——基于布隆过滤器的.pdf

    为了解决这些问题,论文引入了布隆过滤器(Bloom Filter),这是一种高效的、空间效率高的数据结构,用于判断一个元素是否可能存在于一个大规模集合中,而不会产生假阴性(false negative)结果,允许一定程度的假...

    Python-cljcbloom一个用Clojure脚本实现的跨平台布隆过滤器

    在这个项目中,Clojure被用来编写布隆过滤器的底层算法,提供高效的性能。 3. **跨平台性**: Python-cljcbloom使用Clojure的Java绑定特性,使得这个库能够在任何支持JVM的平台上运行,包括Windows、Linux、macOS...

    C++ 数据结构之布隆过滤器

    布隆过滤器(Bloom Filter)是一种空间效率很高的随机数据结构,可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,但缺点是有一定的误识别率和删除错误。 一、历史背景...

    Compressed Bloom filters

    布隆过滤器(Bloom Filter)作为一种高效的空间优化随机数据结构,在支持成员查询方面表现卓越,尤其在数据集庞大时能显著节省存储空间。然而,布隆过滤器存在假阳性的可能性,即可能错误地报告某个元素属于一个集合...

    Redis实现布隆过滤器的方法及原理

    布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,...

    bloom filter 相关论文资料

    综上所述,这份“bloom filter”的论文资料集是深入理解、研究和应用布隆过滤器的重要资源,涵盖了从基本概念到实际应用的多个方面,对于IT从业者尤其是数据结构和算法领域的专业人士来说,是非常宝贵的参考资料。

    bfilter:用于 JavaScript 的布隆过滤器

    用于 JavaScript 的布隆过滤器。 用法 const bfilter = require ( 'bfilter' ) ; 贡献和许可协议 如果你向这个项目贡献代码,你就隐含地允许你的代码在 MIT 许可下分发。 您还隐式验证所有代码都是您的原创作品。 ...

    InverseBloomFilter:并发逆布隆过滤器

    逆布隆过滤器逆布隆过滤器,或“布隆过滤器的反面”,是一种并发的概率数据结构,用于测试一个项目是否被观察到。 这是一个 Go 实现,,它用非加密 FNV-1a 函数代替了 MD5 散列的使用。 反向过滤器可能会报告误报,...

Global site tag (gtag.js) - Google Analytics