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倍。

這種方法看起來很誘人，可惜隻能用在靜态集合上。在一些本身就具有靜态集合特征的應用場合下，比如某種程式設計語言的關鍵字，或者某張CD光牒裡的檔案目錄，它可以作為一種節省空間的方法得以應用。後續的文章中還會介紹一種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更低的錯誤率。