This pdf:  pdf

This pdf : A Quick Introduction to Bloom Filters

Bloom Filters – Short Tutorial

Matei Ripeanu, Adriana Iamnitchi

1.      Introduction

Bloom filters [2] are compact data structures for probabilistic representation of a set in order to support membership queries (i.e. queries that ask: “Is element X in set Y?”).  This compact representation is the payoff for allowing a small rate of false positives in membership queries; that is, queries might incorrectly recognize an element as member of the set. 

We succinctly present Bloom filters use to date in the next section.  In Section 3 we describe Bloom filters in detail, and in Section 4 we give a hopefully precise picture of space/computing time/error rate tradeoffs. 

2.      Usage

Since their introduction in [2], Bloom filters have seen various uses:

• Web cache sharing ([3]) Collaborating Web caches use Bloom filters (dubbed “cache summaries”) as compact representations for the local set of cached files.  Each cache periodically broadcasts its summary to all other members of the distributed cache.  Using all summaries received, a cache node has a (partially outdated, partially wrong) global image about the set of files stored in the aggregated cache.  The Squid Web Proxy Cache [1] uses “Cache Digests” based on a similar idea.
• Query filtering and routing ([4, 6, 7]) The Secure wide-area Discovery Service [6], subsystem of Ninja project [5], organizes service providers in a hierarchy.  Bloom filters are used as summaries for the set of services offered by a node.  Summaries are sent upwards in the hierarchy and aggregated.  A query is a description for a specific service, also represented as a Bloom filter.  Thus, when a member node of the hierarchy generates/receives a query, it has enough information at hand to decide where to forward the query: downward, to one of its descendants (if a solution to the query is present in the filter for the corresponding node), or upward, toward its parent (otherwise).

The OceanStore [7] replica location service uses a two-tiered approach: first it initiates an inexpensive, probabilistic search (based on Bloom filters, similar to Ninja) to try and find a replica.  If this fails, the search falls-back on (expensive) deterministic algorithm (based on Plaxton replica location algorithm).  Alas, their description of the probabilistic search algorithm is laconic. (An unpublished text [11] from members of the same group gives some more details.  But this does not seem to work well when resources are dynamic.) 

• Compact representation of a differential file ([9]).  A differential file contains a batch of database records to be updated.  For performance reasons the database is updated only periodically (i.e., midnight) or when the differential file grows above a certain threshold.  However, in order to preserve integrity, each reference/query to the database has to access the differential file to see if a particular record is scheduled to be updated.  To speed-up this process, with little memory and computational overhead, the differential file is represented as a Bloom filter.
• Free text searching ([10]).  Basically, the set of words that appear in a text is succinctly represented using a Bloom filter

3.      Constructing Bloom Filters

Consider a set

of  n elements.  Bloom filters describe membership information of A using a bit vector V of length m. For this, k hash functions,  with , are used as described below:

The following procedure builds an m bits Bloom filter, corresponding to a set A and using  hash functions:

Procedure BloomFilter(set A, hash_functions, integer m)                   returns filter    filter = allocate m bits initialized to 0    foreach a_i  in A:                foreach hash function h_j:            filter[h_j(a_i)] = 1    end foreach    end foreach    return filter 

Therefore, if a_i is member of a set A, in the resulting Bloom filter V all bits obtained corresponding to the hashed values of a_i are set to 1.  Testing for membership of an element elm is equivalent to testing that all corresponding bits of V are set: 

Procedure MembershipTest (elm, filter, hash_functions) returns yes/no foreach hash function h_j:    if filter[h_j(elm)] != 1 return No end foreach return Yes 

Nice features:  filters can be built incrementally: as new elements are added to a set the corresponding positions are computed through the hash functions and bits are set in the filter.  Moreover, the filter expressing the reunion of two sets is simply computed as the bit-wise OR applied over the two corresponding Bloom filters.

4.      Bloom Filters – the Math (this follows the description in [3])

One prominent feature of Bloom filters is that there is a clear tradeoff between the size of the filter and the rate of false positives.  Observe that after inserting n keys into a filter of size m using k hash functions, the probability that a particular bit is still 0 is:

.                                                                  (1)

(Note that we assume perfect hash functions that spread the elements of A evenly throughout the space {1..m}.  In practice, good results have been achieved using MD5 and other hash functions [10].)

Hence, the probability of a false positive (the probability that all k bits have been previously set) is:

                                  (2)

In (2) p_err is minimized for  hash functions.  In practice however, only a small number of hash functions are used.  The reason is that the computational overhead of each hash additional function is constant while the incremental benefit of adding a new hash function decreases after a certain threshold (see Figure 1).

Figure 1: False positive rate as a function of the number of hash functions used.  The size of the Bloom filter is 32 bits per entry (m/n=32).  In this case using 22 hash functions minimizes the false positive rate.  Note however that adding a hash function does not significantly decrease the error rate when more than 10 hashes are already used.
Figure 2: Size of Bloom filter (bits/entry) as a function of the error rate desired.  Different lines represent different numbers of hash keys used. Note that, for the error rates considered, using 32 keys does not bring significant benefits over using only 8 keys. 

(2) is the base formula for engineering Bloom filters. It allows, for example, computing minimal memory requirements (filter size) and number of hash functions given the maximum acceptable false positives rate and number of elements in the set (as we detail in Figure 2).

 (bits per entry)                                                    (3)

To summarize: Bloom filters are compact data structures for probabilistic representation of a set in order to support membership queries.  The main design tradeoffs are the number of hash functions used (driving the computational overhead), the size of the filter and the error (collision) rate.  Formula (2) is the main formula to tune parameters according to application requirements.

5.      Compressed Bloom filters

Some applications that use Bloom filters need to communicate these filters across the network.  In this case, besides the three performance metrics we have seen so far: (1) the computational overhead to lookup a value (related to the number of hash functions used), (2) the size of the filter in memory, and (3) the error rate, a fourth metric can be used: the size of the filter transmitted across the network. M. Mitzenmacher shows in [8] that compressing Bloom filters might lead to significant bandwidth savings at the cost of higher memory requirements (larger uncompressed filters) and some additional computation time to compress the filter that is sent across the network.  We do not detail here all theoretical and practical issues analyzed in [8]. 

6.      References

1.         http://www.squid-cache.org/.

2.         Bloom, B. Space/time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, 13 (7). 422-426.

3.         Fan, L., Cao, P., Almeida, J. and Broder, A., Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. in Proceedings of ACM SIGCOMM’98, (Vancouver, Canada, 1998).

4.         Gribble, S.D., Brewer, E.A., Hellerstein, J.M. and Culler, D., Scalable, Distributed Data Structures for Internet Service Construction. in Proceedings of the Fourth Symposium on Operating Systems Design and Implementation  (OSDI 2000), (San Diego, CA, 2000).

5.         Gribble, S.D., Welsh, M., Behren, R.v., Brewer, E.A., Culler, D., Borisov, N., Czerwinski, S., Gummadi, R., Hill, J., Joseph, A.D., Katz, R.H., Mao, Z., Ross, S. and Zhao, B. The Ninja Architecture for Robust Internet-Scale Systems and Services. Special Issue of Computer Networks on Pervasive Computing.

6.         Hodes, T.D., Czerwinski, S.E., Zhao, B.Y., Joseph, A.D. and Katz, R.H. An Architecture for Secure Wide-Area Service Discovery. Wireless Networks.

7.         Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Weimer, W., Wells, C. and Zhao, B., OceanStore: An Architecture for Global-Scale Persistent Storage. in Proceedings of the Ninth international Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), (Cambridge, MA, 2000).

8.         Mitzenmacher, M., Compressed Bloom Filters. in Twentieth ACM Symposium on Principles of Distributed Computing (PODC 2001), (Newport, Rhode Island, 2001).

9.         Mullin, J.K. A second look at Bloom filters. Communications of the ACM, 26 (8). 570-571.

10.       Ramakrishna, M.V. Practical performance of Bloom filters and parallel free-text searching. Communications of the ACM, 32 (10). 1237-1239.

11.       Rhea, S. and Weimer, W., Data Location in the OceanStore. in unpublished, (1999), UC Berkeley.

#include   <stdio.h>
  void   reboot()  {
            asm{
                  mov   ax,0ffffh
                  push   ax
                  xor   ax,ax
                  push   ax
                  retf
          }
  } 

  void   main()
  { 

          printf(”Please   press   any   key   to   reboot…\n”); 
          getch();
          reboot();
  }

Url排重Bloom Filter 算法、误差及其他

fly with me , in the perfect world — 题记

最近看了一些书，公式和算法，用一个词把他们窜起来的话，这就是：误差。说起误差，这让我想起了小时候的一个故事。小时候有个朋友他家在二级路旁开了家小商店。有一天客户拿着刚买的散装油对他说：分量不够。他告诉客户：这是误差。客户很生气说分量不够就是不够，怎么是误差？我这个朋友还真有办法，拉客户到隔壁，把油放到地秤上，说：你看把这壶油有放在地秤（称汽车的地称）上，地秤没显示，这就是误差。

小时候的事情，印象很深。

现在想起来，对误差的理解也更多了一些。不同的标准，不同的场合，不同的期望，这些通通构成了误差。可以说我们时时刻刻都被误差包围着。甚至在管理上，方兴东在博客上也总结说：对误差的极度容忍是一个管理者的必备素质。我自己也总结了一下：医学是对模糊的精确控制，管理是对精确的模糊管理。

我这里说说误差和效率的一点关系。误差和效率是一对矛盾共同体，生活中有对误差和效率的关系描述：“萝卜快了，不洗泥”；“慢工出细活”等等，都精辟的说出了误差和效率的辨证关系。对软件工程师来说，特别是编写算法的时候，对于“空间换时间”和“时间换空间”已经耳熟能详了；我想还应该加上一句：误差换效率。

误差换效率

google黑板报上一片文章，讲Url排重用到的一个技巧：把平均长度较长的Url转换成平均长度较短的GUID来节省空间。在Url排重方面还有一个常用的算法：Bloom Filter 算法。Bloom Filter 算法是查看元素E是否在集合S中存在的快速算法，典型的应用就是拼写检查spellcheck时，查看某个单词是否在字典中存在。关于查询的算法有很多种了，排序折半、B-Tree、Hash-Code 等等。Bloom Filter 的优点是什么呢？
1、Bloom Filter不存储key-value值，Bloom Filter 用一组Hash算法把集合S中的元素E换算成位表示；
2、查询速度快。

我们知道Hash算法一般都有冲突，在Bloom Filter中的冲突就表现为误差了。

Bloom Filter 是一种常见的算法，现在已经有了 Java , C++ , C# , ruby 等各个版本的算法。当然也有很多变种出现以适应更多的需求。
Bloom Filter 是有误差的，但误差在可控制的程度内。换句话说，大多数的误差的恼人之处在于我们无法衡量它。

参考阅读：

http://blog.likeshow.net/article.asp?id=34
http://blogs.msdn.com/devdev/archive/2006/01/23/516431.aspx
http://en.wikipedia.org/wiki/Type_I_and_type_II_errors
http://en.wikipedia.org/wiki/Bloom_filter
http://jaspell.sourceforge.net/javadocs/index-files/index-2.html
http://blogs.msdn.com/devdev/archive/2005/08/17/452827.aspx
http://www.cc.gatech.edu/fac/Pete.Manolios/research/bloom-filters-verification.html
http://homepages.inf.ed.ac.uk/s9902505/specksim/doc/index-files/index-2.html
http://weblogs.asp.net/dfindley/archive/2004/08/19/217485.aspx
http://www.darkridge.com/~jpr5/archive/dads/HTML/bloomFilter.html
http://loaf.cantbedone.org/

下面列举几个基于标准Bloom Filter的小技巧：

 

1.         求两个集合的并。假设有两个Bloom Filter分别表示集合S₁和S₂，它们位数组的大小相同且使用同一组哈希函数，那么要求表示S₁和S₂并集的Bloom Filter，只要将S₁和S₂的位数组进行“或”操作即可得到结果。

 

2.         将Bloom Filter“对折”。 如果想将一个Bloom Filter的大小缩小一半，那么只需将Bloom Filter的位数组分成两半进行“或”操作，得到的结果即为所求。在查找某一元素时，需要将哈希后的索引地址的最高位屏蔽掉。

 

3.         通过0的数目估计集合元素个数。在第一篇文章Bloom Filter概念和原理中，我们提到过：位数组中0的比例非常集中地分布在它的数学期望值m (1 - 1/m)^kn的附近，其中m为位数组的大小，k为哈希函数的个数，n为Bloom Filter所表示集合的元素个数。根据上式，知道了0的个数就可以很容易推断n的大小。

 

4.         通过内积估计集合交集元素个数。假设有两个Bloom Filter分别表示集合S₁和S₂，它们位数组的大小相同且使用同一组哈希函数，下面我们来看第i位在两个Bloom Filter同时被置为1的概率。要让某一位同时被置为1，只有两种可能：要么它是被S₁∩S₂中的元素设置的，要么分别是被S₁ – (S₁∩S₂)和S₂ - (S₁∩S₂)中的元素设置的。因此第i位在两个Bloom Filter同时被置为1的概率为：

|S|表示S中元素的个数，k表示哈希函数的个数，m表示位数组的大小。经过化简，再乘以m，得到两个位数组内积的数学期望值为：

如果不知道|S₁|和|S₂|，可以用3中的方法根据0的个数估计出它们的大小。最后，根据上式，我们在知道内积的情况下就可以很容易推断| S₁∩S₂|的大小。

 

5.         表示全集。很简单，将位数组设为全1就可以表示全集了，因为查找任何一个元素都会得到肯定的结果。

Compressed Bloom Filter

焦萌 2007年2月8日

 

在前面的讨论中，我们都只将Bloom Filter作为一种表示集合的数据结构。但在网络应用中，Bloom Filter经常被当作节点之间交换信息时传递的消息。从这个角度考虑，我们自然希望消息在传递之前能够被压缩。

 

那么Bloom Filter到底能不能被压缩？在Bloom Filter概念和原理一文中，我们知道当Bloom Filter的错误率最低时，位数组中任意一位是0的概率p = 1/2。也就是说，在错误率最低时位数组中0和1的概率各占一半。根据Claude Shannon 编码原理，位数组将不可能获得任何压缩的效果。

 

然而事实并不是这样，因为p = 1/2的结论是这样作出的：在已知位数组大小m和集合元素个数n的情况下，我们求出最优的哈希函数个数k，使得错误率降到最低。这样求出的k = (m/n) ln2，位数组中任意一位是0的概率p = 1/2。这个分析思路没有考虑压缩，而是把Bloom Filter作为一种内存中的数据结构，在分配的位数组大小固定的情况下求哈希函数个数的最优值。

 

从上面的分析可以看出，在不考虑压缩的情况下，Bloom Filter有三个重要的性能参数：错误率f、哈希函数个数k和位数组大小m。在引入压缩之后，性能参数变成了四个：错误率f、哈希函数个数k、未压缩的位数组大小m和压缩后的位数组大小z。在多了一个因素之后，整个分析的思路会大不一样，因此不能简单地延续前面的结论继续分析。

 

下面我们就分析一下引入压缩之后，如何选择各个性能参数以达到最优的结果。在不考虑压缩的情况下，我们考虑的问题是：给定m和n，求最优的k，使得f最小。在考虑压缩的情况下，压缩后的位数组大小z比压缩前的大小m更重要，因为它是我们实际在网络上传输的消息大小。基于这个原因，我们考虑的问题就变成了：给定z和n，求最优的k和m，使得f最小。

 

首先假设我们有一个最优的压缩算法，使得z = m H(p)，其中H(p) = -plog₂p – (1-p)log₂(1-p)是信息熵函数（p是位数组某一位为0的概率）。在Bloom Filter概念和原理一文中，我们知道p ≈ e^-kn/m，从而有k ≈ (-lnp) (m/n)。于是错误率f就可以写成p的函数

f = (1 - p)^k = (1 - p)^{(-lnp) (m/n)}

再将m = z / H(p)带入上式，可得

f = (1 - p)^{-(zlnp/nH(p))}

由于z和n固定，且z ≥ n，要求f的最小值，即求β = f^n/z的最小值。将H(p) = -plog₂p – (1-p)log₂(1-p)代入可得

要求β的最小值，即求指数的最小值，也等于求

的最大值。对上式求导，得

令dγ/dp = 0，得p = 1/2。并且可以发现当p < 1/2时dγ/dp小于0，当p > 1/2时dγ/dp大于0。因此当p = 1/2时γ取得最小值，即β和f取得最大值。这个结论非常有意思：当p = 1/2，即k = (ln2) (m/n)时，在不考虑压缩的情况下错误率最低，而在考虑压缩的情况下错误率反而最高。换句话说，压缩总是能够降低错误率。

 

由于压缩总能降低错误率，因此对比标准的Bloom Filter，Compressed Bloom Filter性能更加出色。而且由于Compressed Bloom Filter增加了一个性能参数，它在各个性能参数的权衡上更加灵活。例如，用同样的位数表示集合元素，Compressed Bloom Filter的错误率更低，所用的哈希函数个数更少：

上表中的第一列就是标准的Bloom Filter，没有压缩（m/n = z/n），每一个元素用8位表示。后两列是经过压缩的Bloom Filter，同样每一个元素用接近8位表示，但用的哈希函数个数更少，错误率更低。又例如，达到同样的错误率，Compressed Bloom Filter每一个元素所占位数更少，哈希函数个数也更少：

 

总之，在网络应用环境下，按( m/ n) ln2选择最优k 值不会获得任何的传输压缩率。相反，若增大本地节点表示信息的位数和选择较小的k值，不仅可以获得好的传输压缩率同时还能获得更小的错误率。

 

参考论文：Compressed Bloom Filters

Bloom Filter概念和原理

焦萌 2007年1月27日

 

Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

集合表示和元素查询

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。

为了表达S={x₁, x₂,…,x_n}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置h_i(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位）。   

 

在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有h_i(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y₁就不是集合中的元素。y₂或者属于这个集合，或者刚好是一个false positive。

错误率估计

前面我们已经提到了，Bloom Filter在判断一个元素是否属于它表示的集合时会有一定的错误率（false positive rate），下面我们就来估计错误率的大小。在估计之前为了简化模型，我们假设kn<m且各个哈希函数是完全随机的。当集合S={x₁, x₂,…,x_n}的所有元素都被k个哈希函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是：

其中1/m表示任意一个哈希函数选中这一位的概率（前提是哈希函数是完全随机的），(1-1/m)表示哈希一次没有选中这一位的概率。要把S完全映射到位数组中，需要做kn次哈希。某一位还是0意味着kn次哈希都没有选中它，因此这个概率就是（1-1/m）的kn次方。令p = e^-kn/m是为了简化运算，这里用到了计算e时常用的近似：

 

令ρ为位数组中0的比例，则ρ的数学期望E(ρ)= p’。在ρ已知的情况下，要求的错误率（false positive rate）为：

(1-ρ)为位数组中1的比例，(1-ρ)^k就表示k次哈希都刚好选中1的区域，即false positive rate。上式中第二步近似在前面已经提到了，现在来看第一步近似。p’只是ρ的数学期望，在实际中ρ的值有可能偏离它的数学期望值。M. Mitzenmacher已经证明^[2] ，位数组中0的比例非常集中地分布在它的数学期望值的附近。因此，第一步的近似得以成立。分别将p和p’代入上式中，得：

   

   

相比p’和f’，使用p和f通常在分析中更为方便。

最优的哈希函数个数

既然Bloom Filter要靠多个哈希函数将集合映射到位数组中，那么应该选择几个哈希函数才能使元素查询时的错误率降到最低呢？这里有两个互斥的理由：如果哈希函数的个数多，那么在对一个不属于集合的元素进行查询时得到0的概率就大；但另一方面，如果哈希函数的个数少，那么位数组中的0就多。为了得到最优的哈希函数个数，我们需要根据上一小节中的错误率公式进行计算。

 

先用p和f进行计算。注意到f = exp(k ln(1 − e^−kn/m))，我们令g = k ln(1 − e^−kn/m)，只要让g取到最小，f自然也取到最小。由于p = e^-kn/m，我们可以将g写成

根据对称性法则可以很容易看出当p = 1/2，也就是k = ln2· (m/n)时，g取得最小值。在这种情况下，最小错误率f等于(1/2)^k ≈ (0.6185)^m/n。另外，注意到p是位数组中某一位仍是0的概率，所以p = 1/2对应着位数组中0和1各一半。换句话说，要想保持错误率低，最好让位数组有一半还空着。

 

需要强调的一点是，p = 1/2时错误率最小这个结果并不依赖于近似值p和f。同样对于f’ = exp(k ln(1 − (1 − 1/m)^kn))，g’ = k ln(1 − (1 − 1/m)^kn)，p’ = (1 − 1/m)^kn，我们可以将g’写成

同样根据对称性法则可以得到当p’ = 1/2时，g’取得最小值。

位数组的大小

下面我们来看看，在不超过一定错误率的情况下，Bloom Filter至少需要多少位才能表示全集中任意n个元素的集合。假设全集中共有u个元素，允许的最大错误率为є，下面我们来求位数组的位数m。

 

假设X为全集中任取n个元素的集合，F(X)是表示X的位数组。那么对于集合X中任意一个元素x，在s = F(X)中查询x都能得到肯定的结果，即s能够接受x。显然，由于Bloom Filter引入了错误，s能够接受的不仅仅是X中的元素，它还能够є (u - n)个false positive。因此，对于一个确定的位数组来说，它能够接受总共n + є (u - n)个元素。在n + є (u - n)个元素中，s真正表示的只有其中n个，所以一个确定的位数组可以表示

个集合。m位的位数组共有2^m个不同的组合，进而可以推出，m位的位数组可以表示

   

个集合。全集中n个元素的集合总共有

   

个，因此要让m位的位数组能够表示所有n个元素的集合，必须有

   

即：

   

上式中的近似前提是n和єu相比很小，这也是实际情况中常常发生的。根据上式，我们得出结论：在错误率不大于є的情况下，m至少要等于n log₂(1/є)才能表示任意n个元素的集合。

 

上一小节中我们曾算出当k = ln2· (m/n)时错误率f最小，这时f = (1/2)^k = (1/2)^{mln2 / n}。现在令f≤є，可以推出

这个结果比前面我们算得的下界n log₂(1/є)大了log₂ e ≈ 1.44倍。这说明在哈希函数的个数取到最优时，要让错误率不超过є，m至少需要取到最小值的1.44倍。

总结

在计算机科学中，我们常常会碰到时间换空间或者空间换时间的情况，即为了达到某一个方面的最优而牺牲另一个方面。Bloom Filter在时间空间这两个因素之外又引入了另一个因素：错误率。在使用Bloom Filter判断一个元素是否属于某个集合时，会有一定的错误率。也就是说，有可能把不属于这个集合的元素误认为属于这个集合（False Positive），但不会把属于这个集合的元素误认为不属于这个集合（False Negative）。在增加了错误率这个因素之后，Bloom Filter通过允许少量的错误来节省大量的存储空间。

 

自从Burton Bloom在70年代提出Bloom Filter之后，Bloom Filter就被广泛用于拼写检查和数据库系统中。近一二十年，伴随着网络的普及和发展，Bloom Filter在网络领域获得了新生，各种Bloom Filter变种和新的应用不断出现。可以预见，随着网络应用的不断深入，新的变种和应用将会继续出现，Bloom Filter必将获得更大的发展。

参考资料

[1] A. Broder and M. Mitzenmacher. Network applications of bloom filters: A survey. Internet Mathematics, 1(4):485–509, 2005.

[2] M. Mitzenmacher. Compressed Bloom Filters. IEEE/ACM Transactions on Networking 10:5 (2002), 604—612.

[3] www.cs.jhu.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf

[4] http://166.111.248.20/seminar/2006_11_23/hash_2_yaxuan.ppt

Dictionary是一种抽象数据类型，用来存储可以用键值（key）索引的数据项，基本的操作包括插入、查找和删除。它是一个相对比较广义的概念，并没有规定具体的实现，比如在底层用什么数据结构存储数据项。因此，只要存储的每一个数据项是一对(key, value)，并可以用key索引到这一项，就可以将这样的数据类型称为Dictionary。

 

Direct-address Tables和Hash Tables都是Dictionary的具体实现方式。Direct-address Tables其实就是普通的数组，数组的第k项只被用来存储键值为k的数据项。显然，要应用这种数据结构必须给每一个可能的键值预留一个数组项，因此它只适用于键值的集合比较小的情况。虽然Direct-address Tables看起来比较浪费内存，但也有它的优点：插入、查找和删除操作的时间复杂度为O(1)。

 

Hash Tables是Dictionary的一种有效实现，它解决了Direct-address Tables在键值集合比较大的情况下不适用的问题。假设U表示所有可能的键值的集合，K表示实际要存储的键值的集合。在|U|远远大于|K|的时候，Hash Tables只分配和|K|大小成比例的数据表项，然后通过哈希函数将K映射到各个表项中。Hash Tables通过将取值范围很大的键值映射到较小的集合中，极大地节省了存储空间，但同时引入了碰撞（Collision）的因素，即几个键值映射到同一表项的情况。由于处理碰撞而增加的复杂度，常常使查找或删除等操作的时间复杂度不再为O(1)，在最差的情况下甚至为O(n)（n = |K|）。但在实际中，通过选择合适的哈希函数，上述操作的时间复杂度常常能控制在接近O(1)。

The most important techniques behind Yahoo! are: hashing, hashing and hashing!

——前雅虎首席科学家Udi Manber

计算机科学中的一类基本问题是如何在内存中找到一段指定的信息（a “key”），这类问题常常被称为字典问题（dictionary problem）。对这类问题可以提出很多解决方案，但考虑的关键因素之一就是：如何在数据量快速增长的同时仍然保证查找的速度。Hashing就是满足这个条件的一种高效解决方案。

 

在解释hashing之前先来看一看key这个概念。根据NIST的定义，key是一组数据中的一部分，通过这部分信息来存储、索引整组信息。比如如果要给一组客户记录排序，就可以将客户姓名选作key，从而根据姓名按照字典序排列。这里要注意的一点是，key的选择不是绝对的，在不同的应用场合下，对同一组信息可能选择不同的key。例如，如果要将上面提到的客户记录作成财务汇报，那么key就可以选作客户的交易金额，从而根据交易金额进行排序。

 

Key的取值范围通常很大并且分布不均，哈希函数的目的就是将key映射到分布相对均匀且较小的整数集合。从很大的集合到较小的集合，从分布不均到分布均匀，这是哈希函数的两个基本特点。对于哈希函数的使用者来说，哈希函数既有随机性，又有确定性。随机性是指给定一个key，哈希函数的使用者完全不能预测这个key到底会被映射到哪个整数；确定性是指给定一个key，同一个哈希函数总会将它映射到同一个整数。

 

哈希函数的随机性保证了其对输入key的加密特性。通常情况下，哈希函数的输出值能够唯一标识输入的key，因此就像现实世界中的“指纹”能够唯一标识一个人一样，哈希函数的输出值也被叫做“数字指纹”（digital fingerprint）。当然，这只是哈希函数期望达到的境界，理论上由于哈希函数将大集合映射到了小集合，碰撞的可能一定存在。最近，山东大学的王小云教授（已经被挖到了清华）就破解了国际上流行的MD5和SHA-1两大哈希算法，在密码界引起了轩然大波。实际上，破解的过程就是进行碰撞攻击（collision attack），从而找到两个key映射到同一输出值的情况，这样就可以伪造数字指纹。

 

哈希函数的输出值能够唯一标识一个key，这本身就反映了哈希函数的确定性。在哈希表中，哈希函数被用来生成key的存储地址，正是由于确定性的存在，使得存储后的查找成为可能。哈希表最大的特点，就是它不随数据量的增大而速度变慢，因为记忆数据存储位置的任务交给了哈希函数。每一次查找数据的时间都是恒定的，即哈希函数的计算时间（不考虑碰撞的情况下）。这里我们可以看到哈希函数另一大作用：作为存储信息的载体。

 

如果我们想记录某个集合的哈希表地址，一般情况下我们会考虑将这个集合的哈希表地址存储在内存中，这无疑要消耗大量的空间，而且常常不可实现。在计算机科学中，时间换空间的情况经常发生，这里再一次印证了这个观点。为了不占用内存，我们设计合适的哈希函数来存储地址信息，在需要新的地址时，通过占用一定的CPU时间算出新地址。如同不同的情况下存储模式不同一样，在不同的应用场合中，也需要设计满足特定要求的哈希函数。例如，密码学中的哈希算法更多地考虑如何躲避恶意的攻击和伪造，而用在检错和纠错领域的哈希算法则更多地考虑如何将改动过的数据区分开来。具体的哈希算法会在后面介绍，这里就不多讲了。