D-left hashing

转自:http://blog.sina.com.cn/s/blog_64668ff00100gkzm.html

在Network Applications of Bloom Filters: A Survey一文中，作者提到了一种基于Perfect hashing的方法，它在维持同样错误率的情况下比Bloom Filter占用更少的空间。但是这种方法只能使用在静态集合上，一旦集合发生变化，就需要进行重新计算。

假设我们要表示的静态集合X有n个元素，我们针对它可以找到一个perfect hash function，记作hx : [1…u] → [1…n]。所谓perfect hash function，即它针对不同的key能产生不同的hash value，也就是说没有collision。如果针对不同的key产生不同的hash value，且hash value分布在连续的整数区间内，则称之为minimal perfect hash function，或者minimal perfect hashing。所以上面提到的函数hx严格来说是一个minimal perfect hash function。

有了hx，我们就可以将X映射到n个连续的格子（bucket）中，每个元素对应其中一个格子。下面我们还需要另一个hash function，它针对每个元素完全随机地生成j位长的hash value，然后将hash value作为这个元素的fingerprint存储在对应的格子里。记这个函数为φ: [1…u] → [0…2j-1]。

有了hx和φ，我们就可以分两步将X映射到一个m = n .j位的内存中，且查找的错误率为1/2j，因为只有在j位fingerprint完全吻合的情况下才会出现false positive。在Bloom Filter概念和原理一文中，我们提到过Bloom Filter的错误率为(1/2)k ≥ (1/2)mln2/n。因此当m = n .j时，Bloom Filter的错误率为(0.6185)j，高于这种基于perfect hashing的方法。如果Bloom Filter要保持1/2j的错误率，必须有m = n .j / ln2，因此所占空间是基于perfect hashing方法的1 / ln2倍。

这种方法看起来很诱人，可惜只能用在静态集合上。在一些本身就具有静态集合特征的应用场合下，比如某种程序设计语言的关键字，或者某张光盘里的文件目录，它可以作为一种节省空间的方法得以应用。后续的文章中还会介绍一种d-left counting bloom filter，它借鉴了这种基于perfect hashing的方法，在保留counting bloom filter功能的前提下比它节省了大约一半空间。

哈希函数的输出值（hash value）通常有两种用途：一种用作地址，比如在哈希表中要存储一个元素，首先要针对这个元素生成一个随机地址；另一种用作fingerprint（或者叫digital summary），比如将密码字符串hash成一个fingerprint，验证时进行核对。今天我要介绍的这种存储信息的方式将以上两种用途结合了起来：一个hash value分作两部分，一部分用作存储地址，另一部分用作fingerprint。

你也许会问，这样有什么好处吗？当然有。上篇文章中提到了一种基于perfect hashing的方法，它用了两步存储每个元素的fingerprint。第一步用了一个（perfect）哈希函数生成了这个元素的存储地址，第二步用了另一个哈希函数生成这个元素的fingerprint，然后将fingerprint存储到第一步生成的地址中。由此可见，如果一个hash value能够完成两步工作，就省去了一半的工作量。

另外，我们要存储的其实是集合中每个元素的fingerprint，一个哈希函数生成很大的一个hash value会让碰撞的几率很小，从而让false positive的概率变小。通过将这个很大的hash value中的一部分信息用作地址，其实相当于把fingerprint压缩了：信息一点没少，存储位置本身就包含了一部分信息。

现在我们使用一个哈希函数，将它的hash value分作两部分，高位部分用作随机地址，低位部分留作fingerprint。如果我们用这一个哈希函数存储一个集合，会有什么问题？在基于perfect hashing的方法中，第一步用的哈希函数是perfect hash function，也就是说一个集合的n个元素会映射到n个bucket中，没有碰撞。由于perfect hash function不能应对变动的集合，并且对大多数应用来说开销太大，所以上述所说的一个哈希函数并不是perfect hash function。由此可知碰撞会产生，并且各个bucket的负载并不均衡，实际上单个哈希函数hash value的分布服从泊松（Poisson）分布。

说到这里，文章还没有提到d-Left Counting Bloom Filter，其实上面描述的也就是它的构造过程。我们从一个hash value同时用作地址和fingerprint出发，试图构造一个简洁的存储方式来存储一个集合的fingerprints，现在遇到了一个问题，就是负载不均衡。d-Left Counting Bloom Filter中的d-Left指的是d-Left hashing，解决的就是负载均衡问题。

下面介绍简单介绍一下d-left hashing。d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。

上面的介绍中有一点要注意，就是在作位置选择时，考虑的是两个哈希函数映射的位置中已经存储的key（包括碰撞的情况）的个数，而不是两个子表中已有key的个数。

了解了2-left hashing，d-left hashing就很好理解，它只是对前者的扩展。2-left hashing固定了子表的个数是2，d-left hashing更加灵活，子表的个数是一个变量d，同时也意味着哈希函数的个数是d。在d-left hashing中，整个哈希表被分成d个从左到右依次相邻的子表，每个子表对应一个相互独立的哈希函数。在加入新key时，这个key被d个哈希函数同时计算，产生d个相互独立的位置，然后将key加入到负载最轻的位置（bucket）中。如果负载最轻的位置有多个，就把key加入到最左边的负载最轻的子表中。同样地，如果要查找一个key，需要同时查找d个位置。

关于d-left hashing，上一篇文章已经介绍过了，这里不再多讲。前面提到过，使用d-left hashing是为了解决哈希表的负载平衡问题。为了了解d-left hashing如何解决这个问题，我们先来看没有d-left hashing的情况。同一个hash value高位用作地址低位用作fingerprint，这就意味着同一个地址对应着多个fingerprint。一个地址对应一个bucket，因此一个bucket需要存储多个fingerprint。由于单个哈希函数的hash value分布不均，各个bucket的负载也不均衡。如果每个bucket能存储的fingerprint数量固定，为了不溢出必须按最坏的情况来分配bucket的容量，这就造成了不小的浪费。

使用d-left hashing之后，fingerprint的分布相对比较均衡，因此大大减少了空间的浪费。原来即使分配很大的哈希表，由于按最坏情况分配bucket容量，仍然很难缩小bucket的容量，并且哈希表中大量空间闲置。而使用d-left hashing可以让存储的信息分布均匀，更加紧凑，从而用更小的空间存储同样多的信息。在Perfect Hashing VS. Bloom Filter一文中提到过，d-left counting bloom filter可以比counting bloom filter节省至少一倍的空间，就是因为counting bloom filter负载不均衡，很多空间都被浪费掉了。

从另一个角度考虑，d-left hashing扮演的其实是一个perfect hash function的角色。原来负载不均衡的情况下，碰撞的情况很严重，使用d-left hashing后大大减少了碰撞。当然，它不能完全消除碰撞，因此它只是用一种开销较小的方式模拟了perfect hash function，可以称它为almost-perfect hash function。

过以上的介绍，d-left counting bloom filter的主要思路已经呈现出来了，那就是利用d-left hashing的方法存储fingerprint。下面我们就总结一下d-left counting bloom filter的构造过程。

首先我们使用一个d-left哈希表，表中每个bucket可以容纳若干个（固定数量的）cell，每个cell的位数固定，包括一个fingerprint和一个counter。包含一个fingerprint或许你可以理解，可以为什么还要包含一个counter呢？很简单，就是为了处理碰撞（collision）。在d-left哈希表的d个子表中，每个子表都要处理碰撞的情况。在某一个子表出现碰撞时，会发现已经有同样的fingerprint被存储到同一位置，因此，有了counter只需把counter的值加1即可。

在没有应用d-left hashing的情况下，我们使用一个哈希函数，把它的hash value分成两段，高位作存储地址，低位作fingerprint。现在要应用d-left hashing，有d个存储地址需要生成，我们仍然用一个哈希函数，但把它的hash value分成d+1段：高位的d段分别用作d个存储地址，每个子表对应一个，剩下的低位部分作为fingerprint。

在添加一个key时，先对它作一次hash，得到d个存储位置和一个fingerprint，然后判断d个位置中的负载情况，并在负载最轻的几个位置中选择最左边的插入。如果选择的位置已经存储了相同的fingerprint，就把那个cell的counter加1。在删除一个key时，同样地作一次hash，然后在d个存储位置查找相应的fingerprint，如果找到就将这个cell置空或者将相应的counter减1。

一切看上去都很完美，d-left counting bloom filter的构造似乎也已经完成。但实际上，上面的构造过程中有一个缺陷，这个缺陷会在从集合中删除元素时出现。下面举一个例子演示这个缺陷如何出现。

假设有一个元素x要插入表中，它的d个存储位置对应每个子表的第一个bucket，它的fingerprint是a。再假设根据负载情况，x的fingerprint被存储到了最后一个子表的第一个bucket中。现在又有一个元素y要插入到表中，它的d个存储位置对应第i个子表的第i个bucket，它的fingerprint也是a。注意，由于x被存储在最后一个子表的第一个而非第d个bucket（对应y的位置选择），在插入y时，y根本感觉不到x的存在。假设根据负载情况，y的fingerprint被存储在第一个子表的第一个bucket中，现在我们来看看在删除x时会出现什么情况。很明显，删除x时我们会发现两个完全相同的fingerprint：一个在第一个子表中，另一个在最后一个子表中。我们该删除哪个？

简单概括上面的例子，x和y本不相同，但hash后的fingerprint相同。它们的d个位置选择中有一个重合，x不选择重合的位置，y选择重合的位置。这样就造成了我们在删除x时无法判断到底该删除哪个fingerprint。这个缺陷对上面的构造过程提出了挑战，但是别担心，扑救的办法还是有的。

根据前面的描述，d-left counting bloom filter构造过程中的缺陷有三个条件：1. x和y的fingerprint相同；2. 位置选择有重合；3. x不选择重合位置，y选择重合位置。其中fingerprint相同我们无法避免，因为碰撞总会出现，cell中的counter也是为此而设置的。元素选不选择重合位置我们也无法控制，因为这要根据当时的负载情况而定。所以我们想要弥补这个缺陷，只能从位置重合入手。换句话说，要想办法让不同元素的d个位置选择完全没有重合（不考虑碰撞）。

我们给出的解决方案是：将hashing的整个操作分成两个阶段。第一阶段，我们用一个哈希函数H计算要插入元素x的hash value，记做fx；第二阶段，为了获得d个存储位置，我们另外引入d个随机置换（random permutation）。令H(x) = fx = (b, r)，其中b是bucket index，表示存储位置；r是remainder，表示要存储的fingerprint。然后令d个置换为：

P1(fx) = (b1, r1), P2(fx) = (b2, r2), … , Pd(fx) = (bd, rd).

其中Pi(fx)对应着x在第i个子表的存储位置和fingerprint。我们知道置换意味着一一对应，因此不同元素（的hash value）作置换之后的值仍然不同。这样我们就达到了前面提到的让不同元素的d个位置选择完全没有重合的目标。

引入随机置换避免了位置重合之后，我们还需要在插入元素之前作一项工作。每次插入一个元素时，先要在它的d个位置选择中检查是否已经存有相同的fingerprint，如果有，就把相应cell的counter加1。由于不同元素的存储位置不会重合，因此只有在碰撞的情况下才会出现两个相同fingerprint能存入同一组存储位置的情况。而我们一旦在插入之前作了检测，再作删除操作时就永远不会发现d个位置中有两个完全相同的fingerprint。

到此为止，删除元素时的缺陷问题已经完全被解决了。但同时，我们也看到，为了解决缺陷而引入的随机置换让存储的过程变成了一种并不严格的d-left hashing。幸运的是，这个问题并不是很严重，至少在实现中很难看出什么差别。至于选择什么样的置换，论文作者给出的建议是：简单的线性函数。如果哈希函数的取值范围为[2q]，随机置换可以写成：

Pi(H(x)) = aH(x) mod 2q

其中a是区间[2q]中的随机奇数。

最后，我们将d-left counting bloom filter与标准的counting bloom filter作一比较。假设要表示的集合有m个元素，构造d-left counting bloom filter的各个参数如下：

1.         d-left哈希表包含4个子表；

2.         每个子表包含m/24个bucket，使得bucket的平均负载是6个元素；

3.         子表中每个bucket可以容纳8个cell，8个就能以很高的概率保证不会溢出；

4.         cell中每个counter包含2位，可以容纳4个相同的fingerprint；注意，我们必须给fingerprint设置一个表示空的状态，比如全0，这样才能用2位counter表示4个fingerprint。

假设用r位表示fingerprint，那么false positive的概率就是24 · 2-r。其中两个fingerprint完全相同的概率为(1/2)r，又因d-left hashing使得查找时有4个选择（有4个子表），每个选择对应一个bucket，一个bucket平均负载是6，所以需乘以24。整个d-left counting bloom filter所需的所有位数为4m(r+2)/3。其中r+2表示一个cell的位数，m是集合元素个数，一个bucket能容纳8个cell，但平均负载是6个，所以乘以4/3就得到全部的位数。

现在来看标准的counting bloom filter。假设对于m个元素的集合，counting bloom filter使用cm个counter，每个counter使用4位，哈希函数的个数k使用最优值cln2，得到false positive的概率为(2-ln2)c，总共使用4cm位。

如果令c = (r+2)/3，那么两种方法使用的位数相同，这时我们来比较一下false positive的概率。我们发现在r ≥ 7时

(2-ln2)(r+2)/3 > 24 · 2-r

而且使用的位数越多，两个false positive概率的差距就越大。当r = 14时，c = 16/3，虽然两个结构使用的位数相同，但counting bloom filter比d-left counting bloom filter的false positive概率大了100倍以上。

现在换个角度，看看在false positive概率相同的情况下两者占用空间的情况。假设标准的counting bloom filter使用9个4位的counter（每个元素36位），6个独立的哈希函数，得到的false positive概率为0.01327。d-left counting bloom filter使用11位的fingerprint（每个元素52/3位），得到的false positive概率为0.01172。我们计算一下，52/3÷36= 0.48，也就是说，d-left counting bloom filter只使用了counting bloom filter不到一半的空间，就得到了比counting bloom filter更低的错误率。