原译：使用Bloom Filters

仙子注：这篇文章是半年前翻译的，最早贴于公司内部的BBS上，并引起一些争论。Bloom Filters是一种效率较高的内存索引算法，它本身具有矛盾性：一方面能快速测试目标成员是否存在，另一方面又不可避免的具有假命中率。如下文档仅供参考。
由于不知道如何在这里粘贴图片，因此本文中没有包含图片说明，请对照原文档来阅读，原文档在：http://www.perl.com/pub/a/2004/04/08/bloom_filters.html?page=1   或可email给我索取中文PDF文档。


使用Bloom Filters

原作者：Maciej Ceglowski
April 08, 2004 


任何perl使用者都熟悉hash查询，一个存在测试的语句可以这样写：

foreach my $e ( @things ) { $lookup{$e}++ }

sub check {
my ( $key ) = @_;
print "Found $key!" if exists( $lookup{ $key } );
}

虽然hash查询很有用，但对非常大的列表，或keys自身非常大时，这种查询可能变得不实用。当查询hash增长得太大，通常的做法是将它移到数据库或文件中，只在本地缓存里保存最常用的关键字，这样能改善性能。

许多人不知道有一种优雅的算法，用以代替hash查询。它是一种古老的算法，叫做Bloom filter。 Bloom filter允许你在有限的内存里（你想在这块内存里存放关键字的完整列表），执行成员测试，这样就能避开使用磁盘或数据库进行查询的性能瓶颈。也许你会认为，空间的节省是有代价的：存在着可大可小的假命中率风险，并且一旦你增加key到filter后，就不能删除它。然而在许多情形下，这些局限是可接受的，bloom filter能编制有用工具。（仙子注：例如代理服务器软件Squid就使用了bloom filter算法。）

例如，假如你运行了一个高流量的在线音乐存储站点，并且如果你已知歌曲存在，就可以通过仅获取歌曲信息的方法，来最大程度的减少数据库压力。你可以在启动时构建一个bloom filter，在试图执行昂贵的数据库查询前，可以用它执行快速的成员存在测试。

use Bloom::Filter;

my $filter = Bloom::Filter->new( error_rate => 0.01, capacity => $SONG_COUNT );
open my $fh, "enormous_list_of_titles.txt" or die "Failed to open: $!";

while (<$fh>) {
chomp;
$filter->add( $_ );
}

sub lookup_song {
my ( $title ) = @_;
return unless $filter->check( $title );
return expensive_db_query( $title ) or undef;
}

在该示例里，该测试给出假命中的几率是1%，在假命中率情况下程序会执行昂贵的数据库索取操作，并最终返回空结果。尽管如此，你已避开了99%的昂贵查询时间，仅使用了用于hash查询的一小片内存。更进一步，1%假命中率的filter，每个key的存储空间在2字节以下。这比你执行完整的hash查询所需的内存少得多。

bloom filters在Burton Bloom之后命名，Burton Bloom 1970年首先在文档里描述了它们，文档名Space/time trade-offs in hash coding with allowable errors.在那些内存稀少的日子里，bloom filters因其简洁而倍受重视。事实上，最早的应用之一是拼写检查程序。然而，由于有少数非常明显的特性，该算法特别适合社会软件应用。

论坛热门帖子:	[lch203] 写得蛮好的linux学习笔记(10-21) [黑马制造] 学习java的30个目标(10-19) [笑傲股林] 做测试半年了，有点迷茫，应该再学些什么提高自己的测试水平和测试能力呢？(10-19) [udp8589] 大家用google的来吱一声? 用百度的~~也来报道下?(10-18) [沂偌掳兆] 本人总结的一些认为C++比较经典的书籍，希望对大家有用(10-18)
TAG标签:	使用 hash 我们 filter key 函数 my 向量 bloomfilter