海量数据向来都是百度,淘宝,腾讯面试的热点,虽然微软不看重这个,但是了解一下还是很有必要的。
最近在写倒排索引,希望继续关注本博。
===========================================================
【什么是Bloom Filter】
Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,采用Bloom Filter的数据结构,可以通过极少的错误换取了存储空间的极大节省。 这里有一篇关于Bloom Filter的详细介绍,不太懂的博友可以看看。
【适用范围】
可以用来实现数据字典,进行数据的判重,或者集合求交集
【基本原理及要点】
对于原理来说很简单,位数组外加k个独立hash函数。Bloom filter提供两种基本的操作,将元素加入集合和判断某一元素是否属于该集合,一下说明如何操作:
将一个元素加入集合:首先将要加入集合的元素用k个hash函数进行hash,得到k个hash index,然后在集合的位数组中将这k个hash index的位置置1,下面用两幅图来描述这个过程。
bloom filter位数组(集合)的初始状态
插入两个个元素,X1,X2:
bloom-filter-插入元素
查找元素是否属于该集合:首先同样用定义的hash函数对该元素进行hash得到hash index,然后查位数组中对应的hash index是否都是1,如果是,则表明该元素属于该集合,反之不属于【当然不全是了,请继续看后面】,如图,判断元素Y1,Y2是否属于该集合。
bloom-filter-判断元素是否属于集合
如上图,由于y1的三个hash index有一个不为1,因此不属于该集合,而y2所有的hash index的位置上都为1,因此属于该集合。
【Bloom Filter的不足】
分享到:
相关推荐
背景分布式一致性 hash 算法将哈希空间组织成一个虚拟的圆环,圆环的大小是,最终会得到一个 [0,] 之间的一个无符号整型,这个整数代表服务器的编号;多个服务
C# 海量数据处理算法BloomFilter算法的实现和测试例子;C# 海量数据处理算法BloomFilter算法的实现和测试例子
Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不...
大数据量,海量数据 处理方法总结 包括Bloom filter 哈希 bit-map 堆 双层桶划分 数据库索引 倒排索引 外排序 trie树等。细分为适用范围、要点、实例等。
bloomfilter.js, 使用FNV的JavaScript bloom filter快速散列 Bloom过滤器This过滤器实现使用非加密 Fowler-Noll-Vo散列函数来实现速度。用法var bloom = new BloomFilter( 32 * 256,//number of bits to all
#资源达人分享计划#
1. 将访问过的URL保存到数据库 2. 用HashSet将访问过的URL保存起来 3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库
Bloom filter是一个简明的空间效率极高的随机的数据结构。用Bloom filter 表示 cache 内容 ,可以高效地实现cache 协作。本文对BloomFilter及其改进型进行了综述性分析,探讨了它的实用性。
分布式环境下改进的BloomFilter过滤技术
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.
bloom-filter-scala, 用于 Scala的Bloom过滤器,最快的JVM Scala的 Bloom filter 概述Bloom过滤器是一种空间高效的数据结构,用于测试某个元素是否是集合的成员。 false 正匹配是可能的,但 false 负数不是。 ...
leveldb中bloomfilter的优化。
相似项发现主题中的shingling、simhash、bloom filter算法java实现,测试通过,附带测试数据。
Respect! The original paper about bloom filter. Very beginning of hash error tolerate algorithm to get wanted data faster.
改进的Bloom filter主要将两个标准的Bloom filter组成二维并行Bloom filter,对RFID采集数据所包含的两个属性值tagID和readerID进行并行过滤。经实验可见,标准Bloom filter与哈希过滤(hash filter)相比具有明显的...
bloom filter(布隆过滤器)应用很广泛的高效算法,研究研究
提出一种针对动态集合的矩阵型Bloom filter表示与查找法(matrix Bloom filter,MBF),它使用一个s×m位矩阵对数据集合进行哈希表示与查找,较同类算法SBF和DBF,能继承Bloom filter算法常数查找开销的基本精髓。
bloom filter的一些论文 有综述,有应用,较为详细 不过可能需要下载cnki的阅读器,这个比较好下,大家可以自己下个
这是一个java版的bloomFilter Hash函数集,并带有测试程序。在我的资源里还有一个c版的,函数功能相同,在我的应用中具有良好表现。
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下