在网上看到的,思想很好,留下了;貌似在一个很大的集合中查找或者过滤,空间性能上不错:
摘录自网上:
Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。
集合表示和元素查询
下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时,Bloom Filter是一个包含m位的位数组,每一位都置为0。
为了表达S={x1, x2,…,xn}这样一个n个元素的集合,Bloom Filter使用k个相互独立的哈希函数(Hash Function),它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x,第i个哈希函数映射的位置hi(x)就会被置为1(1≤i≤k)。注意,如果一个位置多次被置为1,那么只有第一次会起作用,后面几次将没有任何效果。在下图中,k=3,且有两个哈希函数选中同一个位置(从左边数第五位)。
在判断y是否属于这个集合时,我们对y应用k次哈希函数,如果所有hi(y)的位置都是1(1≤i≤k),那么我们就认为y是集合中的元素,否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合,或者刚好是一个false positive。
原文地址:http://blog.csdn.net/jiaomeng/article/details/1495500
分享到:
相关推荐
### Bloom Filter概念与原理 #### 一、Bloom Filter概述 Bloom Filter是一种高效的数据结构,主要用于快速查询一个元素是否存在于一个集合中。它通过牺牲一定的精确度来换取存储空间的极大节省。Bloom Filter的...
### Leveldb中Bloom Filter的优化:ElasticBF #### 概述 在现代数据库技术中,**Log-Structured Merge-tree (LSM-tree)** 结构因其高效的写入性能而被广泛应用于各种键值(Key-Value, KV)存储系统中,如Google的*...
### Bloom Filter概述与应用 #### 一、Bloom Filter简介 Bloom Filter是一种高效的数据结构,主要用于近似地判断一个元素是否在一个集合中。它的主要特点是空间效率高,但允许存在一定的误报率(即可能会错误地...
- **bloomfilter.h**:这是一个头文件,很可能包含了Bloom Filter的数据结构定义和相关操作函数的声明。在C语言中,头文件通常用于提供接口给其他源文件使用,这里可能是为了在spider.c中方便地调用Bloom Filter的...
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 100000, 0.0001); // 添加元素 bloomFilter.put("element1"); bloomFilter.put("element2"); // 检查元素 ...
**Python-bloomfilter过滤器详解** Bloom Filter是一种空间效率极高的概率型数据结构,用于判断一个元素是否在一个集合中。在Python开发中,尤其是在处理大量数据时,Bloom Filter可以有效地节省内存空间,尤其适用...
在传统的Bloom Filter中,它通常处理单一的关键字,而在“多字段矩阵型Bloom Filter”中,这一概念被扩展到了支持多个字段的情况,这使得它在处理复杂数据集时更具灵活性。 首先,我们要理解Bloom Filter的基本原理...
BloomFilter<String> bloomFilter = BloomFilter.create(funnel, 100000, 0.03); bloomFilter.put("element1"); bloomFilter.put("element2"); System.out.println(bloomFilter.mightContain("element1")); //...
布隆过滤器(Bloom Filter)是一种空间效率极高的概率数据结构,用于判断一个元素是否可能在一个集合中。它由布伦南·布隆在1970年提出,最初是为了解决查找问题中的空间效率问题。这篇论文资料集合涵盖了布隆过滤器...
bloomfilter.js, 使用FNV的JavaScript bloom filter快速散列 Bloom过滤器This过滤器实现使用非加密 Fowler-Noll-Vo散列函数来实现速度。用法var bloom = new BloomFilter( 32 * 256,//number of bits to all
在Go编程语言中,Bloom Filter和Cuckoo Filter是两种流行的数据结构,用于空间效率高的近似存在检查。本篇文章将深入探讨Cuckoo Filter如何在某些情况下优于Bloom Filter,以及Go语言中实现Cuckoo Filter的细节。 ...
布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在大数据处理、缓存系统、分布式存储等领域有着广泛的应用。这个压缩包文件“bloom filter布隆过滤器学习...
Bloom filter是一个简明的空间效率极高的随机的数据结构。用Bloom filter 表示 cache 内容 ,可以高效地实现cache 协作。本文对BloomFilter及其改进型进行了综述性分析,探讨了它的实用性。
2. Bloom Filter技术:Bloom Filter是一种空间效率很高的随机数据结构,它使用位数组来简洁地表示一个集合,并且能够快速判断一个元素是否属于这个集合。Bloom Filter的引入是为了高效利用数据空间,在海量数据匹配...
本文将深入探讨标题提及的"Go-一个CuckooFilter的Go库BloomFilter的替代物",以及其背后的CuckooFilter数据结构和它如何成为BloomFilter的一种优化方案。 首先,Bloom Filter是一种空间效率极高的概率数据结构,...
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算法详解** Bloom Filter是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。由Burton Howard Bloom在1970年提出,它的主要特点是能够在牺牲一定的判断准确性(可能存在...