- 浏览: 569198 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (253)
- java (84)
- python (22)
- 设计模式 (12)
- 数据结构和算法 (7)
- ibatis (1)
- 数据挖掘 (2)
- 集体智慧读书笔记 (1)
- ubuntu (4)
- lucene (11)
- 算法 第4版 (11)
- apache mina (16)
- memcached (1)
- android (9)
- netty (6)
- mongodb (2)
- maven (2)
- openfire (2)
- 服务端 (21)
- 产品 (0)
- apache (1)
- 选择 (2)
- 构架WEB高性能站点 (7)
- redis (8)
- 诗词歌赋 (3)
- 源代码阅读 (5)
- 前端 (1)
- javascript (3)
- guice (1)
- 分布式 (5)
- 总结-2014 (4)
- jvm (1)
最新评论
-
liu_jiaqiang:
写的挺好
maven多项目管理 -
H972900846:
我想知道哪里整的,如果是自己写的,那有点牛呀如果是抄的请说明出 ...
SSL身份认证原理 -
春天好:
博主写的很好,赞一个,多谢分享 *(^-^*)分享一个免费好用 ...
定向网站爬虫---初级例子 -
fenglingabc:
经过测试,parameterType="java.u ...
mybatis获取主键和存储过程返回值 -
jyghqpkl:
[u][/u] ...
Cookie的secure 属性
日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中,遇到一个新元素时,将它和集合中的元素直接比较即可。 |
今天,我们介绍一种称作布隆过滤器的数学工具,它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。
布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。
假定我们存储一亿个电子邮件地址,我们先建立一个十六亿二进制(比特),即两亿字节的向量,然后将这十六亿个二进制位全部设置为零。对于每一个电子邮件地址 X,我们用八个不同的随机数产生器(F1,F2, ...,F8) 产生八个信息指纹(f1, f2, ..., f8)。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制位全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。(见下图)
现在,让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器(F1, F2, ..., F8)对这个地址产生八个信息指纹 s1,s2,...,s8,然后将这八个指纹对应到布隆过滤器的八个二进制位,分别是 t1,t2,...,t8。如果 Y 在黑名单中,显然,t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址,我们都能准确地发现。
布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是,它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中,因为有可能某个好的邮件地址正巧对应八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中,误识概率在万分之一以下。
布隆过滤器的好处在于快速,省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单,存储那些可能别误判的邮件地址。
import java.util.BitSet; public class SimpleBloomFilter { private static final int DEFAULT_SIZE =2 << 24 ; 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 static void main(String[] args) { String value = "stone2083@yahoo.cn" ; SimpleBloomFilter filter=new SimpleBloomFilter(); System.out.println(filter.contains(value)); filter.add(value); System.out.println(filter.contains(value)); } public SimpleBloomFilter() { for( int i= 0 ; i< seeds.length; i ++ ) { func[i]=new SimpleHash(DEFAULT_SIZE, seeds[i]); } } public void add(String value) { for(SimpleHash f : func) { bits.set(f.hash(value), true ); } } 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; } 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; } } } 运行
发表评论
-
protobuf-dt插件
2015-03-24 13:16 1357protobuf-dt: 安装前先安装xtext 可 ... -
java循环标签
2015-03-20 16:13 551今天看 源码的时候 看到 一个小语法 参考: ... -
java程序性能优化 --阅读
2014-10-14 17:56 659闲着,真实无聊; 发现一本好书《java程序性能优 ... -
jetty invalid entry CRC问题
2014-08-04 11:42 15061: http://stackoverflow.com/qu ... -
guice注入
2014-05-24 12:13 9386Google Guice3.0: http://code. ... -
eclipse快捷键
2014-05-21 16:01 5241: clrl+alt+r : 最常用,快速定位到文件 2 ... -
java clone
2014-05-16 17:04 480转:http://www.blogjava.net/ora ... -
ThreadLocal
2014-05-13 18:39 721简单介绍一下ThreadLocal的原理:1.Thread ... -
hession
2014-04-30 12:33 648一、首先先说Hessian是什么? Hessian:he ... -
冒泡和快速排序java
2014-04-19 18:01 7021: 冒泡最简单一种: /** * 算法效率o ... -
java生产者和消费者模型三种实现
2014-04-19 17:51 13301: 生产者和消费者的问题,生产者生产产品到缓冲区,消费者 ... -
单例模式
2014-03-14 16:06 702今天看到群里,关于单例模式的多线程下的安全问题: 1:最 ... -
freemarker的使用
2014-02-28 16:42 7841:freemarker eclipse插件安装方法:ht ... -
java 引用类型和内存泄露
2013-11-21 17:48 547http://blog.csdn.net/luoshenfu ... -
java泛型
2013-11-07 13:52 393Class<T>在实例化的时候,T要替换成具体 ... -
filter执行顺序
2013-10-12 11:16 1086多个筛选器的运行顺序取决于下列规则: 将 filt ... -
spring rmi远程调用
2013-09-09 11:48 11351:以前用jmi发布服务,实现分布式的一种方式,远程调用, ... -
spring mvc返回204状态码
2013-07-24 09:27 38701:204是没内容 不跳转的 代表请求成功的意思 ... -
editplus去掉多余空行
2013-07-19 21:05 6841: ^[ \t]*\n 用正则表达式替换 -
spring3 aop 使用详细
2013-06-06 11:10 01:目标:拦截所有的@Controller中的方法 ...
相关推荐
相似项发现主题中的shingling、simhash、bloom filter算法java实现,测试通过,附带测试数据。
自己写的Java抓图程序 原理见 http://blog.csdn.net/binyao02123202/archive/2010/07/12/5728840.aspx 用了序列化 线程 和BloomFilter算法
Go中的Cuckoo Filter 实现,比 Bloom Filter 更好
使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,
数据结构与算法分析JAVA_LAB06,BLOOM FILTER 实现
Bloom Filter SHA-1 Message Digest Algorithm MD5 Base64 Graph data structure Strongly Connected Components(SCC) Prim's minimum spanning tree Kruskal MST Directed/Undirected graph ops Breadth First ...
hutool-bloomFilter 布隆过滤,提供一些Hash算法的布隆过滤 hutool-cache 简单缓存实现 hutool-core 核心,包括Bean操作、日期、各种Util等 hutool-cron 定时任务模块,提供类Crontab表达式的定时任务 hutool-crypto...
BloomFilter 布隆过滤器 线性表 栈 先进后出(LIFO, Last In First Out) 实现 用两个指针域分别指向栈顶和栈底 常见操作 进栈 栈顶本来指向的节点交由新节点来指向 栈顶指针指向新...
Hutool 是什么 Hutool 是一个 Java 工具包类库,它可以对文件、流、加密解密、转码...hutool-bloomFilter 布隆过滤,提供一些Hash算法的布隆过滤 hutool-cache 缓存 hutool-core 核心,包括Bean操作、日期、各种Util等
lyq-algorithms-liblyq算法库,涉及到相关数据挖掘,解压缩,模式匹配,图算法等多领域算法BloomFilter布隆过滤器算法。可以用来判读一个集合是否存在的问题原理是运用哈希算法将值进行映射,不需要暴力的遍历数据...
java lru leetcode 算法练习刷题的仓库 理论基础:熟悉常见的数据结构、起码看过一本...BloomFilter LRU Cache Algorithm General Coding InOrder/PreOrder/PostOrder Traversal Greedy Recursion/Backtrace Breadth-fi
Java中的快速近似成员资格过滤器 当前实现了以下过滤器类型: 布隆过滤器:“标准”算法 阻止的Bloom过滤器:比常规的Bloom过滤器快,但需要更多的空间 计数布隆过滤器:允许删除条目,但需要4倍以上的空间 简洁的...
BloomFilter LRU Cache Algorithm Greedy Recursion/Backtrace Traversal Breadth-first/Depth-first search Divide and Conquer Dynamic ProgrammingBinary Search Graph System Design System architecture ...
缓存空值、BloomFilter 缓存雪崩: 缓存层不能提供服务,所有的请求都会达到存储层,存储层的调用量会暴增,造成存储层挂掉。解决方案: 缓存集群、本地缓存、限流、降级 算法和协议 数据一致性 容器与devops goLang ...
#zongtui-filter 众推,开源版的今日头条! 包括url去重、bloom过滤器、文章去重等多种去重算法! bloom过滤器已经实现。
5.2.1 Reduce侧的联结 5.2.2 基于DistributedCache的复制联结 5.2.3 半联结:map侧过滤后在reduce侧联结 5.3 创建一个Bloom filter 5.3.1 Bloom filter做了什么 5.3.2 实现一个Bloom filter 5.3.3 Hadoop 0.20...
java lru leetcode 开始 DaLiu Start... 数据结构 (data structure) 是相互之间存在一种或多种特定关系的数据元素的集合 研究的是数据的逻辑结构或物理结构 ...布隆过滤器BloomFilter LRU Cache 算法 If-else, switch -
主要用Java编写。 包括C版本(当前仅对MPHF进行评估)。 可以在线性时间内生成每个密钥需要少于1.58位的MPHF。 可以以小于100 ns / key的速度生成MPHF,以小于100 ns / key的速度评估,每个密钥少于3位。 并发。 ...
技术点56 通过MapReduce 对Bloom filter 进行semi-join 7.3 本章小结 8 结合R 和Hadoop 进行数据统计 8.1 比较R 和MapReduce 集成的几种方法 8.2 R 基础知识 8.3 R 和Streaming 8.3.1 Streaming 和...
数据科学.7 数据结构和算法的运用7.1 使用图进行数据建模和解决问题7.1.1 模拟图7.1.2 最短路径算法技术点52 找出两个用户间的最短距离7.1.3 friends-of-friends(FoF) 技术点53 计算FoF 7.1.4 ...