Hash, Yer Değiştirme ve Sıkıştırma

Djamal Belazzougui¹, Fabiano C. Botelho² ve Martin Dietzfelbinger³

¹ Ecole Nationale Supérieure d’Informatique, ENI Oued Smar, Cezayir, Cezayir
d_belazzougui@ini.dz

² Bilgisayar Mühendisliği Bölümü, Minas Gerais Federal Teknolojik Eğitim Merkezi, Belo Horizonte, Brezilya
fabiano@decom.cefetmg.br

³ Bilgisayar Bilimi ve Otomasyon Fakültesi, Technische Universität Ilmenau, P.O. Box 100565, 98684 Ilmenau, Almanya
martin.dietzfelbinger@tu-ilmenau.de

Özet

Bir hash fonksiyonu h, yani tüm anahtarların kümesi U'dan aralık ([m] = {0, ..., m − 1}) içine giden bir fonksiyon, n ≤ m büyüklüğünde S ⊆ U altkümesi için mükemmel hash fonksiyonu (PHF) olarak adlandırılır; eğer h, S üzerinde bire bir ise.

Bir PHF'nin önemli performans parametreleri temsil boyutu, değerlendirme süresi ve oluşturma süresidir.

Bu makalede, temsil boyutu optimal değere çok yakın olan PHF'lerin elde edilmesini sağlayan bir algoritma sunuyoruz; bu sırada O(n) oluşturma süresi ve O(1) değerlendirme süresi korunur. Örneğin m = 2n durumunda anahtar başına 0.67 bit alan kullanan bir PHF elde ediyoruz; m = 1.23n için ise anahtar başına 1.4 bit elde ediyoruz. Bu sonuçlar daha önce bilinen yöntemlerle mümkün değildi.

Algoritmamız birkaç bilinen algoritmadan esinlenmiştir; temel yeni özellik, Pagh’ın hash-and-displace yaklaşımının bir uyarlamasını, hash fonksiyonu indekslerinden oluşan bir dizi üzerinde veri sıkıştırma ile birleştirmemizdir. Bu birleşim, doğrusal oluşturma süresi ve sabit sorgu süresi korunurken alan kullanımını önemli ölçüde azaltmayı mümkün kılar.

Algoritmamız ayrıca k-perfect hashing için de kullanılabilir; burada en fazla k anahtar aynı değere eşlenebilir. Analiz için tamamen rastgele hash fonksiyonlarının ücretsiz olarak verildiğini varsayıyoruz; bu tür varsayımlar gerekçelendirilebilir ve önceki çalışmalarda da kullanılmıştır.

1 Giriş

Bu makalede mükemmel hash fonksiyonları, minimal mükemmel hash fonksiyonları ve k-perfect hash fonksiyonları problemini inceliyoruz. Tüm durumlarda olası anahtarların bir "evreni" U verilir ve ilgili anahtarların n = |S| büyüklüğünde S ⊆ U kümesi girdi olarak sağlanır. Aralık şu şekildedir

[m] = {0, 1, ..., m − 1}.

Tanım 1

(a) h : U → [m] fonksiyonu, eğer h, S üzerinde bire bir ise, S ⊆ U için mükemmel hash fonksiyonu (PHF) olarak adlandırılır.

(b) h : U → [m] fonksiyonu, eğer h bir PHF ise ve m = n = |S| ise, S ⊆ U için minimal mükemmel hash fonksiyonu (MPHF) olarak adlandırılır.

(c) k ≥ 1 tamsayısı için, h : U → [m] fonksiyonu, eğer her j ∈ [m] için

|{ x ∈ S | h(x) = j }| ≤ k

sağlanıyorsa, S ⊆ U için k-perfect hash fonksiyonu (k-PHF) olarak adlandırılır.

Bir hash fonksiyonu oluşturma süreci şu şekilde tanımlanır: verilen bir S kümesi için, girdi x ∈ U olduğunda h(x) ∈ [m] değerinin hesaplanmasını sağlayan bir (statik) veri yapısı DS oluşturan algoritmalar düşünülür; burada h, S için bir PHF (MPHF, k-PHF) özelliğine sahiptir. Değerlendirme süresi sabit olmalıdır.

Mükemmel hashing, bir anahtara ait herhangi bir bilgiyi saklamadan her anahtara benzersiz bir tanımlayıcı atamak istediğimiz birçok uygulamada kullanılabilir. Bunun açık bir uygulaması, küçük ve hızlı bir belleğin mükemmel hash fonksiyonunu sakladığı; anahtarların ve ilişkili ek verilerin ise daha yavaş fakat daha büyük bir bellekte tutulduğu durumdur.

Bir blok veya aktarım biriminin boyutu, tek bir okuma erişiminde k veri öğesinin alınabileceği şekilde seçilebilir. Bu durumda bir anahtarla ilişkili verinin daha yavaş belleğe tek bir erişimle alınması sağlanabilir. Bu yaklaşım örneğin donanım yönlendiricilerinde kullanılmıştır [21].

Mükemmel hashing ayrıca standart bilgisayarlarda dahili bellekte geleneksel hashing ile rekabet edebilecek performans göstermiştir [1]. Yakın zamanda, graf temsilinin ana belleğe sığmadığı durumlarda grafik algoritmalarını hızlandırmak için de kullanılmıştır [8].

Bu makalede sunulan algoritma hem mükemmel hashing hem de k-perfect hashing için aynı şekilde uygulanabilir. Ancak analiz ve deneylerde çoğunlukla mükemmel hashing üzerinde yoğunlaşıyoruz.

PHF'lerle ilgili en önemli ölçütlerden biri, böyle bir fonksiyonun tanımlanması için gereken alan miktarıdır. Bir PHF'yi tanımlamak için gereken bilgi kuramsal alt sınır [10, 17] çalışmalarında incelenmiştir. Daha basit bir ispat daha sonra [22]'de verilmiştir.

[17, Theorem III.2.3.6 (a)] içindeki formüllerden yola çıkarak oldukça iyi alt sınırlar elde etmenin kolay bir yolu vardır. Orada S için bir mükemmel hash fonksiyonunun tanımının bit uzunluğunun en az

∑₀≤i<n log(1 − i/m)

olması gerektiği belirtilmiştir.

∑₀≤i<n log(1 − i/m)

şeklindeki toplamların integral ile yaklaşık hesaplanmasına dayanan basit bir argüman kullanıldığında şu alt sınırlar elde edilir:

(m − n) log(1 − n/u) − log n − (u − n) log(1 − n/u)

PHF'ler için ve

−(u − n) log(1 − n/u)

MPHF'ler için.

u ≫ n varsayımı altında, m = 1.23n olan PHF'ler için bu değer yaklaşık anahtar başına 0.89n bit verir ve MPHF'ler için (n = m) alt sınır yaklaşık olarak

n / ln 2 ≈ 1.44n bit

olur.

1.1 Alan Alt Sınırları

k-perfect hashing için km = (1 + ε)n olduğunda benzer alt sınırları elde etmek kolay görünmemektedir. n = km durumu için (k > 1 olan MPHF'ye karşılık gelir), [17, Theorem III.2.3.6 (a)] çalışmasındaki gibi bir argümanla şu alan alt sınırı elde edilebilir

log n + (n/k) log(k! / kᵏ).

u ≫ n ve büyük n için alt sınır şu hale gelir

n (log e + log(k! / kᵏ)/k − o(1)).

Örnekler:

• k = 4 için: alt sınır ≈ 0.589n
• k = 8 için: alt sınır ≈ 0.355n
• k = 16 için: alt sınır ≈ 0.208n

1.2 Bilinen Yapılar

Mükemmel hash fonksiyonları için birçok yapı bilinmektedir. O(n) alan gerektiren ilk yapılar Schmidt ve Siegel [25] tarafından verilmiştir. Daha sonra Hagerup ve Tholey [13], rastgele hash fonksiyonları hakkında varsayım yapmadan MPHF'ler için asimptotik olarak optimal bir yapı sunmuştur; ancak bu düzen pratik görünmemektedir.

1999 yılında Pagh [20], yalnızca basit hash fonksiyonları kullanan ve analizde anahtar başına (2 + ε) log n bit gerektiren oldukça açık fakat optimal olmayan bir yöntem önermiştir. Deneylerde anahtar başına yaklaşık 0.35 log n bit değerlerine ulaşılabildiği gösterilmiştir.

Bölme teknikleri kullanılarak (örneğin bkz. [6]) alan anahtar başına δ log n değerine indirilebilir; burada δ > 0 sabit bir değerdir.

Son beş yılda birkaç şaşırtıcı gelişme yaşanmıştır. [4] çalışmasında basit mükemmel hash fonksiyonlarının nasıl kurulabileceği örtük biçimde gösterilmiş, ardından [2] çalışmasında çok büyük n değerleri için anahtar başına 2 bitten daha az alan kullanan bir PHF'nin çok basit bir şekilde kurulabileceği açık biçimde gösterilmiştir.

Son iki yöntem rastgele hash fonksiyonlarının ücretsiz olarak sağlandığını varsayar.

1.3 Tam Rastgelelik Varsayımı

Bu çalışmada kullanılan tüm aralıklar [r] için tamamen rastgele hash fonksiyonları ailesine erişimimiz olduğunu varsayıyoruz.

Bu şu anlama gelir: r ve bir indeks q ≥ 1 verildiğinde

h_{r,q} : U → [r]

şeklinde bir hash fonksiyonu vardır; bu fonksiyon U üzerinde tamamen rastgeledir ve farklı (r, q) çiftlerine karşılık gelen tüm hash fonksiyonları birbirinden bağımsızdır. Ayrıca x ∈ U ve r ile q verildiğinde h_{r,q}(x) değeri O(1) sürede bulunabilir.

Bu güçlü bir varsayım gibi görünse de, alanın n^{1−Ω(1)} bitten fazlasını harcamadan bunu gerekçelendiren basit yöntemler vardır ( split-and-share yöntemi ). Ayrıntılar için bkz. [6].

Deneysel uygulamalarımızda split-and-share kullanmadık; bunun yerine pratikte iyi davrandığı bildirilen basit indeksli hash fonksiyonu aileleri kullandık. "İndeksli" ifadesi, gerektiğinde çok fazla alan kullanmadan yeni hash fonksiyonlarının seçilebilmesi anlamına gelir.

Burada tartışılan tüm yapılarda başarı çalışma zamanında kontrol edilebilir. Gerekirse önce ucuz hash fonksiyonları denenebilir ve yalnızca ihtiyaç duyulduğunda daha karmaşık olanlara geçilebilir. Deneylerimizde buna hiç ihtiyaç duyulmamıştır.

2 Veri Yapısı ve Kurulumu

PHF yapısının açıklamasıyla başlıyoruz. (MPHF yapısı, [(1 + ε)n] aralığına sahip bir PHF'den, [2]'de olduğu gibi aralık üzerinde standart sıkıştırma teknikleri uygulanarak elde edilir.)

Veri yapısı iki seviyeden oluşur.

Ara bir tablo için r boyutu seçilir. Birinci seviye hash fonksiyonu

g : U → [r]

U kümesini [r] aralığına eşler ve S kümesini r kovaya böler:

Bᵢ = { x ∈ S | g(x) = i }, 0 ≤ i < r.

Her kova için ikinci bir hash fonksiyonu vardır

fᵢ : U → [m]

ve bu fonksiyon oluşturma algoritması tarafından

(φ₁, φ₂, φ₃, ...)

bağımsız tamamen rastgele hash fonksiyonlarından oluşan bir diziden seçilir.

fᵢ fonksiyonunu adlandırmak için yalnızca şu indeksi saklamak yeterlidir:

σ(i)

yani

fᵢ = φ_{σ(i)}.

Şu şekilde tanımlarız

h(x) = f_{g(x)}(x) = φ_{σ(g(x))}(x).

g ve (φ₁, φ₂, ...) ailesinin ücretsiz olarak verildiği varsayıldığından, veri yapısının yalnızca şu diziyi saklaması gerekir:

Σ = (σ(i), 0 ≤ i < r)

ve σ(i) değerinin O(1) sürede elde edilmesini sağlaması gerekir.

Pagh [20] tarafından önerilen ve temeli Tarjan ve Yao [26] fikrine dayanan yöntemi izleyerek kovaları boyutlarına göre azalan sırada sıralar ve yer değiştirme değerlerini sırayla buluruz.

Ancak Pagh'ın yönteminden farklı olarak — orada yer değiştirme değerleri [r] aralığındaydı ve r > n gerekliydi — biz tamamen rastgele fonksiyonların gücünden yararlanıyoruz.

Her Bᵢ kovası için uygun σ(i) indeksi şu şekilde bulunur.

Algoritma 1 — Hash, Yer Değiştirme ve Sıkıştırma

1. S kümesini kovalar halinde ayır: Bᵢ = g⁻¹({i}) ∩ S, 0 ≤ i < r.

2. Kovaları |Bᵢ| boyutuna göre azalan sırada sırala. (Sayılar küçük olduğu için bu işlem O(n) sürede yapılabilir.)

3. T[0 … m−1] dizisini sıfırlarla başlat.

4. Adım 2'deki sıraya göre tüm i ∈ [r] için:

5. ℓ = 1, 2, ... için tekrar ederek

   Kᵢ = { φ_ℓ(x) | x ∈ Bᵢ }

   kümesini oluştur.

6. Aşağıdaki koşul sağlanana kadar devam et:

   |Kᵢ| = |Bᵢ| ve Kᵢ ∩ { j | T[j] = 1 } = ∅.

7. Başarılı ℓ değerini σ(i) olarak ata.

8. Kᵢ içindeki tüm j için T[j] = 1 yap.

9. (σ(i))_{0 ≤ i < r} dizisini O(1) erişimi koruyacak şekilde sıkıştırılmış forma dönüştür.

Eğer Bᵢ = ∅ ise σ(i) = 1 alınır.

Bu prosedürün çıktısı şu dizidir:

Σ = (σ(i), 0 ≤ i < r).

İkili T[0 … m−1] dizisini 0'dan k'ya kadar sayan sayaçlardan oluşan bir diziyle değiştirip gerekli küçük düzenlemeleri yaparsak k-perfect hash fonksiyonu oluşturmak için bir algoritma elde ederiz.

Aşağıda göreceğimiz üzere, m = (1 + ε)n olacak şekilde sabit bir ε > 0 için Σ dizisinin hesaplanması beklenen doğrusal zamanda başarıyla tamamlanır.

Analizden, yüksek olasılıkla σ(i) değerlerinin bazı sabit C için C log n ile sınırlı olduğu sonucu çıkar. Böylece her σ(i) sayısı

log log n + O(1)

bit kullanılarak temsil edilebilir.

Bu uzunlukta sabit boyutlu çerçevelere yerleştirmek şu alan gereksinimini verir:

n (log log n + O(1)) bit

ve aynı zamanda h için sabit değerlendirme süresi korunur.

Ancak bir adım daha ileri gidebiliriz. σ(i) değerleri sınırlı beklentiye sahip geometrik dağılıma uyar ve E(σ(i)) sabit bir değerle sınırlıdır. [11]'de açıklanan sıkıştırma yöntemleri kullanılarak (σ(i)) dizisinin tamamı O(n) bit içinde kodlanabilir ve yine rastgele erişim desteklenir; böylece O(1) değerlendirme süresi korunur.

Bu yöntem, yeterince güçlü kodlama teknikleri kullanıldığında MPHF için

n log e bit

olan teorik optimal alana küçük bir sabit çarpan kadar yaklaşır.

3 Analiz

Gerçek 1

E(log₂(σ(i))) ≤ log₂(E(σ(i))).

3.1 Büyük Kovalar

Şöyle tanımlayalım

λ = n / r

Bu değer ara tablonun yük faktörüdür. Bᵢ kovasının ortalama boyutu λ'dır ve |Bᵢ|, beklentisi λ olan Bi(n, 1/r) binom dağılımını izler.

Poisson(λ), şu olasılık dağılımına sahip rastgele değişken X için kullanılan gösterimdir:

Pr(X = t) = e^{-λ} λ^t / t!.

n, r → ∞ ve n/r = λ olduğunda binom dağılımı Bi(n, 1/r)'nin Poisson(λ) dağılımına yakınsadığı iyi bilinir.

Dolayısıyla sabit bir t ve her i ∈ [r] için:

Pr(|Bᵢ| = t) = e^{-λ} λ^t / t! (1 + o(1)).

Bu sonuç ve Azuma eşitsizliği kullanılarak aşağıdaki tahminler elde edilir.

Lemma 2

Her sabit t ≤ 2λ + 2 için, keyfi c > 0 olmak üzere yüksek olasılıkla (1 − n^{-c}):

• a_{≥}(λ, t) = |{ i | |Bᵢ| ≥ t }| = r · Poisson(λ, ≥ t) (1 + o(1))
• b_{≥}(λ, t) = |{ x ∈ S | |B_{g(x)}| ≥ t }| = n · Poisson(λ, ≥ t − 1) (1 + o(1))

Şimdi t = |Bᵢ| ≥ 2λ + 1 olduğunu varsayalım. Algoritma bu kova için fᵢ = φ_{σ(i)} bulmaya çalışırken, T[0 … m−1] tablosunda en fazla b_{≥}(λ, t) anahtar depolanmıştır.

Yukarıdaki sınırlardan şu sonuç elde edilir:

b_{≥}(λ, t) = n · Poisson(λ, ≥ t − 1) ≤ n e^{-λ} (eλ/(t − 1))^{t−1}.

Bu, bazı φ_ℓ fonksiyonları denenirken başarı olasılığının şu alt sınırla sınırlı olduğunu gösterir:

(1 − (n/m) e^{-λ} (eλ/(t − 1))^{t−1})^t.

Bu sınır t ≥ 2λ + 1 için t ile birlikte artar. Dolayısıyla başarı olasılığı en az

(1 − (e/4)^λ)^{2λ + 1}

olur.

Bundan

E(σ(i)) < (1 − (e/4)^λ)^{-(2λ + 1)} < 31

sonucu elde edilir.

Gerçek 1 kullanılarak şu sonuca varılır

E(log(σ(i))) < log(31) < 5.

Dolayısıyla büyük kovalar için hem σ(i) değerini bulma süresi hem de onu saklamak için gereken alan şu şekilde sınırlıdır:

a_{≥}(λ, t) · O(1) < r · Poisson(λ, ≥ 2λ) · O(1) ≤ e^{-dλ} n

burada d > 0 sabittir. Bu nedenle λ büyüdükçe bu kovaların etkisi ihmal edilebilir hale gelir.

E( ∑_{1 ≤ i < r} log(σ(i)) )

ifadesini tahmin etmek için şu tanımları yaparız:

• L_{=t} = t · T_t = boyutu t olan kovaların içindeki anahtar sayısı
• L_{≥t} = boyutu t veya daha büyük olan kovaların içindeki anahtar sayısı
• β_{=t} = L_{=t} / n
• β_{≥t} = L_{≥t} / n

Algoritma 1'de t boyutunda s − 1 kova zaten işlenmiş ve sıradaki kova Bᵢ olsun. Bu durumda T tablosuna tam olarak

L_{≥t+1} + (s − 1)t

anahtar yerleştirilmiştir.

Bᵢ içindeki anahtarların hash değerlerini inceleriz. Hepsinin T içinde boş konumlara düşme olasılığı en az

(1 − β_{≥t+1} − (st − 1)/n)^t

değeridir.

Bu değeri t boyutundaki tüm kovalar üzerinde topladığımızda gerekli sınırlar elde edilir.

3.2 Genel Analiz

t boyutundaki kovaların sayısı T_t olsun. Gerçek 1'den şu sonucu çıkarırız

[ n \sum_{t} . ]

Dolayısıyla

[ E(\sigma(i)) \le \sum_{1 \le s \le L=t} \frac{1}{1-\beta_{\ge t+1}^{,s t-1}} ]

ve

[ E(\log(\sigma(i))) \le t \log \left( \frac{1}{1-\beta_{\ge t+1}^{,s t-1}} \right). ]

Buna göre

[ \sum_{1 \le s \le L=t} \log \left( \frac{1}{1-\beta_{\ge t+1}^{,s t-1}} \right). ]

(2)

(2) içindeki toplamı bir integral ve bir düzeltme terimi ile tahmin edebiliriz:

[ \int_0^L \log \left( \frac{1}{1-\beta_{\ge t+1}^{,x t-1}} \right) dx + t (C_t - C_{t+1}). ]

(3)

Şöyle tanımlayalım

[ C_t = \log\left(\frac{1}{1-\beta_{\ge t} + \frac{1}{n}}\right). ]

İntegrali değerlendirmek için şu değişken dönüşümünü yaparız:

[ y = 1 - \beta_{\ge t+1} - x t^{-1}. ]

Böylece

[ dy = \frac{n}{t y} ]

ve

[ \int \log\left(\frac{1}{y}\right) dy. ]

(4)

Şu eşitlikten dolayı

[ \int \log(1/y) , dy = -y(\log y - \log e), ]

(2), (3) ve (4)'ten şu sonucu elde ederiz:

[ \sum_{i : |B_i| = t} E(\log(\sigma(i))) \le n[-y(\log y - \log e)]{1-\beta{\ge t+1}+1/n}^{1-\beta_{\ge t+1}/n}

• t(C_t - C_{t+1}). ]

(5)

(5) ifadesini, (\beta_{t_0+1} = 0) olan ilk (t_0) değerine kadar toplarız. Bu durumda

[ C_{t_0+1} = -\log\left(1 + \frac{1}{n}\right), ]

ve şu sonucu elde ederiz

[ \sum_{0 \le i < r} E(\log(\sigma(i))) \le n[-y(\log y - \log e)]_{1/n}^{1+1/n}

• \sum C_t. ]

Şu eşitsizlik kullanılarak

[ (n+1) \ln\left(1 + \frac{1}{n}\right) > \frac{1}{n}, ]

şu sonuç elde edilir

[ n[-y(\log y - \log e)]_{1/n}^{1+1/n} < n \log e - \log n - 2\log e. ]

(7)

Bu, istenen sınırı verir.

(C_t)-toplamı, kovaların boyutlarının dağılımına (ve (\varepsilon)’e) bağlıdır. (\varepsilon = 0) için ilk toplanan (C_1), (\log n)’e eşittir ve bu değer (7)’deki (-\log n) terimi ile birbirini götürür. Eğer (\varepsilon > 0) ise, tüm (C_t) değerlerinin (O(\log(1/\varepsilon))) olduğu kolayca doğrulanabilir.

Aşağıdakini tahmin etmek için

[ \sum_{2 \le t \le t_0+1} C_t ]

(\beta_2, \beta_3, \ldots) dizisi hakkında bir varsayım yapmamız gerekir. Poisson dağılımı durumunda

[ C_t < \log\left(\frac{1}{1-\beta_{\ge t}}\right) \le \log\left(\frac{1}{1-\beta_{\ge 2}}\right) = \log\left(\frac{1}{e^{-\lambda}}\right) = \lambda \log e. ]

Bölüm 3.1’de görüldüğü gibi, boyutu (2\lambda + 2) ve daha büyük olan kovaların

[ \sum_{0 \le i < r} E(\log(\sigma(i))) ]

içindeki toplam katkısı (\le e^{-d\lambda} n)’dir. Dolayısıyla

[ \sum_{2 \le t \le 2\lambda+1} C_t ]

kabaca (O(\lambda^2)) ile tahmin edilebilir.

[11]’deki sıkıştırma şeması böylece beklenen alan sınırını

[ n(\log e + O((\log(\lambda)+1)/\lambda)) + O(\lambda^2), ]

şeklinde verecektir; burada (O)-gösterimi, Ek A.2’de gösterildiği gibi büyüyen (\lambda)’yı ifade eder. (T) indeks tablosu için, kod uzunluğunun tam sayı olması gerekirken (\log(\sigma(i)))’nin tam sayı olmamasından kaynaklanan etkiyi azaltabilen daha gelişmiş sıkıştırma şemaları, en uygun değer olan (n \log e)’yi daha iyi yaklaştırabilecektir.

Son olarak, oluşturma süresinin (\lambda) ve (\varepsilon)’e bağımlılığını açık biçimde gösteren daha basit bir sonuç da elde ettik. Teorem 2, Ek B’de tam kanıtı verilen sonucu göstermektedir.

Teorem 2

Compressed hash-and-displace algoritması beklenen

[ O(n(2\lambda + (1/\varepsilon)\lambda)) ]

zamanı ve

[ O(\log(1/\varepsilon) n), ]

alanı gerektirir; burada (\lambda)’ya bağlılık yoktur.

4 Deneysel Sonuçlar

Bu bölümün amacı, bundan sonra CHD algoritması olarak adlandırılacak olan sıkıştırılmış hash-and-displace algoritmasının performansını değerlendirmektir. Deneylerde kullanılan uygulama Ek A’da açıklanmaktadır. Ayrıca Botelho, Pagh ve Ziviani [2] tarafından önerilen algoritma ile karşılaştırma yapıyoruz. Bu algoritma literatürde bulduğumuz başlıca pratik perfect hashing algoritmasıdır ve bundan sonra BPZ algoritması olarak adlandırılacaktır.

Deneyler, Linux işletim sistemi (sürüm 2.6) çalıştıran bir bilgisayarda gerçekleştirildi. Sistem özellikleri: 1.86 GHz Intel Core 2 işlemci, 4 MB L2 önbellek ve 4 GB ana bellek. Algoritmalar C dilinde gerçekleştirildi ve şu adreste bulunmaktadır:

http://cmph.sf.net

GNU Lesser General Public License (LGPL) altında.

Algoritmaları karşılaştırmak için aşağıdaki ölçütleri kullandık:

• PHF veya MPHF üretmek için gereken zaman miktarı.
• Ortaya çıkan PHF veya MPHF’leri depolamak için gereken alan.
• Bir PHF veya MPHF’nin her bir erişim için gerektirdiği süre.

Tüm sonuçlar 50 denemenin ortalamasıdır ve %95 güven düzeyi ile istatistiksel olarak doğrulanmıştır.

Deneylerimizde iki anahtar kümesi kullandık:

• AllTheWeb sorgu günlüğünden çıkarılan 5.000.000 benzersiz sorgu teriminden oluşan bir anahtar kümesi; buna AllTheWeb anahtar kümesi denmektedir.
• TodoBr arama motoru tarafından Brezilya Web’inden toplanmış 20.000.000 benzersiz URL’den oluşan bir anahtar kümesi; buna URL anahtar kümesi denmektedir.

Tablo 1: Deneylerde kullanılan anahtar kümelerinin özellikleri

• AllTheWeb: n = 5.000.000; en kısa anahtar = 2; en uzun anahtar = 31; ortalama anahtar uzunluğu = 17.46 bayt; anahtar kümesi boyutu = 91 MB.
• URL: n = 20.000.000; en kısa anahtar = 8; en uzun anahtar = 496; ortalama anahtar uzunluğu = 58.77 bayt; anahtar kümesi boyutu = 2.150 MB.

Dipnotlar:

5. AllTheWeb (www.alltheweb.com), Fast Search & Transfer şirketine ait bir ticari markadır ve Şubat 2003’te Overture Inc. tarafından satın alınmıştır. Mart 2004’te ise Overture, Yahoo! tarafından devralınmıştır.
6. TodoBr (www.todobr.com.br), Akwan Information Technologies şirketine ait bir ticari markadır ve Temmuz 2005’te Google Inc. tarafından satın alınmıştır.

4.1 CHD ve BPZ Algoritmalarının Karşılaştırılması

Bu bölümde CHD algoritmasının pratikte oldukça rekabetçi olduğunu gösteriyoruz. Bu algoritma doğrusal zamanda bildiğimiz en kompakt PHF ve MPHF’leri üretir ve bu fonksiyonlar sabit zamanda da hesaplanabilir.

Yük faktörü için dört farklı değerle deney yaptık:

• (\alpha = 0.81)
• (\alpha = 0.90)
• (\alpha = 0.99)
• (\alpha = 1.00)

(\alpha = 1.00) olduğunda MPHF’ler elde edilir. Her (\alpha) için, üretim süresi ile temsil boyutu arasında bir denge sağlamak amacıyla kova başına ortalama anahtar sayısını ((\lambda)) değiştiriyoruz. Deneylerde Ek A.1’de açıklanan sezgisel yöntemi kullandık; çünkü bu yöntem sürekli olarak daha iyi alan kullanımı sağladı ve üretim süresini yalnızca yaklaşık %25 artırdı.

Şekil 1, CHD algoritmasını BPZ algoritması [2] ile karşılaştırmaktadır. BPZ algoritması yalnızca (\alpha = 0.81) ile PHF üretebilirken, CHD algoritması çok daha yüksek yük faktörlerine ulaşabilir (örneğin (\alpha = 0.99)). Ayrıca CHD algoritması daha esnektir ve alan kullanımı ile yük faktörü arasında tam bir denge sunar.

Örneğin CHD, (\alpha = 0.5) için anahtar başına 0.67 bit (deneylere dahil edilmemiştir) ve (\alpha = 0.99) için anahtar başına 1.98 bit elde edebilir.

(\alpha = 1.00) ile MPHF elde etmek için her iki algoritmanın da rank ve select işlemlerini destekleyen özlü (succinct) bir veri yapısı kullanması gerekir; bu da ek bitler gerektirir.

CHD algoritması, hem üretim süresi hem de tanım boyutu açısından BPZ algoritmasından daha iyi performans gösterecek şekilde ayarlanabilir. Örneğin (\lambda \le 3) olduğunda her zaman en hızlı algoritmadır. Ayrıca doğrusal zamanda çalışmaya devam ederken bilgi kuramsal alt sınırın 1.43 katı içinde PHF ve MPHF üretilebilir. Perfect hashing literatüründe başka hiçbir algoritma teorik sınıra bu kadar yakın sonuçlar elde ederken aynı zamanda pratik kalmayı başaramamıştır.

Değerlendirme Süresi

Algoritmaları aşağıdakileri değerlendirerek karşılaştırdık:

• AllTheWeb koleksiyonundan (5 \times 10^6) anahtar
• URL koleksiyonundan (2 \times 10^7) anahtar

BPZ tarafından üretilen fonksiyonlar, CHD tarafından üretilenlerden biraz daha hızlıdır. Ancak tüm fonksiyonlar şu süreleri gerektirir:

• Fonksiyon tanımı önbelleğe sığdığında 0.8 mikrosaniyeden az (AllTheWeb veri kümesi).
• Ön belleğe sığmadığında 1.4 mikrosaniyeden az (URL veri kümesi).

Tanımı daha büyük olan fonksiyonlar, önbellek kaçırmaları nedeniyle genellikle biraz daha yavaştır. MPHF’ler de ek rank ve select hesaplamaları gerektirdiğinden biraz daha yavaştır.

CHD ile üretilen PHF ve MPHF’lerin değerlendirme süresi kullanılan sıkıştırma tekniğine bağlıdır. Örneğin Elias–Fano şeması [27] kullanıldığında fonksiyonlar daha hızlı olabilir; ancak tanım boyutları biraz daha büyük olur (örneğin (\alpha = 0.99) ve (\lambda = 5) için anahtar başına 1.98 bit yerine 2.08 bit).

4.2 k-perfect Hashing için Sonuçlar

Bu bölüm, CHD algoritmasının çok kompakt k-perfect hash fonksiyonları üretebildiğini gösteren sonuçları sunmaktadır. Bu fonksiyonlar, daha yavaş bellekte depolanan veriler için hızlı bellekte tutulan bir indeks olarak kullanılabilir.

Bellek blokları birden fazla eleman içerebileceğinden, blok başına eleman sayısı küçük bir sabit (k) ise, standart bir perfect hash fonksiyonundan daha az alan kullanan bir k-perfect hash fonksiyonu kurabiliriz.

k-perfect hashing’in temel avantajı, en kötü durumda yavaş belleğe yalnızca bir rastgele erişim gerektirmesidir. Bu özellik aşağıdaki diğer yöntemler için geçerli değildir:

• Litwin tarafından önerilen doğrusal hashing [15]
• Bucketed cuckoo hashing [9]

Deneylerde yük faktörü (\alpha = 0.99) kullanıldı; çünkü bu durum Bölüm 1.1’de türetilen teorik alt sınırlara en yakın olandır.

Tablo 3

(\alpha = 0.99) için k-perfect hash fonksiyonlarının üretim süresi ve tanım boyutu.

Veri kümeleri:

• AllTheWeb ((n = 5 \times 10^6))
• URL ((n = 2 \times 10^7))

Test edilen ortalama kova boyutları: 2, 4 ve 8.

Değerlendirme süresi sonuçları, Tablo 2’de gösterilenlerle benzer olduğu için verilmemiştir.

5 Sonuçlar

Sıkıştırılmış hash-and-displace yöntemi için yeni bir yaklaşım sunduk. CHD algoritması, günümüzde bilinen en kompakt PHF ve MPHF’leri O(n) zamanda üretir.

Temel özellikler:

• Üretilen fonksiyonların değerlendirme süresi sabittir (pratikte 1.4 mikrosaniyeden az).
• Depolama alanı, bilgi kuramsal alt sınırın 1.43 katı içindedir.
• En yakın rakip Martin ve Pagh [7] tarafından geliştirilen algoritmadır; ancak bu algoritma doğrusal zamanda çalışmaz.

CHD algoritması ayrıca BPZ algoritmasından daha hızlı çalışacak ve daha kompakt fonksiyonlar üretecek şekilde ayarlanabilir. En dikkat çekici özelliği, pratik kalmaya devam ederken bilgi kuramsal alt sınıra oldukça yaklaşabilmesidir.

6 Teşekkür

Üçüncü yazar, Pagh’in hash-and-displace yöntemindeki kovalar için rastgele fonksiyonların kullanılmasına ilişkin fikri paylaştığı için Peter Sanders’a teşekkür eder. Bu fikir daha sonra Lars Dietzel’in TU Ilmenau’daki yüksek lisans tezinde [5] incelenmiş ve doğrusal üstü alan kullanan bir çözüme ulaşılmıştır.

Kaynaklar

1. F. C. Botelho, H. R. Langbehn, G. V. Menezes ve N. Ziviani. Minimal perfect hash fonksiyonları ile iç belleğin indekslenmesi. Proc. of the 23rd Brazilian Symposium on Database (SBBD’08), sayfa 16–30, Ekim 2008.

2. F. C. Botelho, R. Pagh ve N. Ziviani. Basit ve alan açısından verimli minimal perfect hash fonksiyonları. Proc. of the 10th Workshop on Algorithms and Data Structures (WADS’07), sayfa 139–150. Springer LNCS 4619, 2007.

3. F. C. Botelho ve N. Ziviani. Çok büyük anahtar kümeleri için harici perfect hashing. Proc. of the 16th ACM Conference on Information and Knowledge Management (CIKM’07), sayfa 653–662. ACM Press, 2007.

4. Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld ve Ayellet Tal. Bloomier filtresi: Statik destek arama tabloları için verimli bir veri yapısı. Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’04), sayfa 30–39, 2004.

Kaynaklar

5. L. Dietzel. Speicherplatzeffiziente perfekte Hashfunktionen, Kasım 2005. Yüksek Lisans Tezi (Almanca).

6. Martin Dietzfelbinger. Minimal perfect hash fonksiyonları için tasarım stratejileri. SAGA, sayfa 2–17, 2007.

7. Martin Dietzfelbinger ve Rasmus Pagh. Erişim ve yaklaşık üyelik için özlü veri yapıları. Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP’08), sayfa 385–396, Berlin, Heidelberg, 2008. Springer-Verlag.

8. Stefan Edelkamp, Peter Sanders ve Pavel Simecek. Yarı-harici LTL model denetimi. CAV, sayfa 530–542, 2008.

9. Ulfar Erlingsson, Mark Manasse ve Frank McSherry. Geleneksel hash tablolarına serin ve pratik bir alternatif. Proceedings of the 7th Workshop on Distributed Data and Structures (WDAS 2006), sayfa 1–6, Santa Clara University, Santa Clara, California, ABD, 2006.

10. M. L. Fredman ve J. Komlós. Ayırıcı sistemlerin ve perfect hashing fonksiyonu ailelerinin boyutu üzerine. SIAM Journal on Algebraic and Discrete Methods, 5:61–68, 1984.

11. Kimmo Fredriksson ve Fedor Nikitin. Rastgele erişimi ve hızlı dizge eşleştirmeyi destekleyen basit bir sıkıştırma kodu. Proceedings of the 6th International Workshop on Efficient and Experimental Algorithms (WEA’07), sayfa 203–216, 2007.

12. Rodrigo Gonzalez ve Gonzalo Navarro. Özlü veri yapılarının istatistiksel kodlanması. CPM, sayfa 294–305, 2006.

13. T. Hagerup ve T. Tholey. Neredeyse minimal alanda verimli minimal perfect hashing. Proceedings of the 18th Symposium on Theoretical Aspects of Computer Science (STACS’01), sayfa 317–326. Springer LNCS cilt 2010, 2001.

14. Bob Jenkins. Algorithm alley: Hash fonksiyonları. Dr. Dobb’s Journal of Software Tools, 22(9), Eylül 1997.

15. Witold Litwin. Linear hashing: Dosya ve tablo adresleme için yeni bir araç. Proceedings of the Sixth International Conference on Very Large Data Bases (VLDB’80), sayfa 212–223. VLDB Endowment, 1980.

16. B. S. Majewski, N. C. Wormald, G. Havas ve Z. J. Czech. Bir perfect hashing yöntemleri ailesi. The Computer Journal, 39(6):547–554, 1996.

17. K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, 1984.

18. M. Mitzenmacher ve E. Upfal. Probability and Computing. Cambridge University Press, 2005.

19. Michael Mitzenmacher ve Salil Vadhan. Basit hash fonksiyonlarının neden çalıştığı: Bir veri akışındaki entropinin kullanılması. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’08), 2008.

20. R. Pagh. Hash and displace: Minimal perfect hash fonksiyonlarının verimli değerlendirilmesi. Workshop on Algorithms and Data Structures (WADS’99), sayfa 49–54, 1999.

21. B. Prabhakar ve F. Bonomi. Ağ uygulamaları için perfect hashing. Proceedings of the IEEE International Symposium on Information Theory. IEEE Press, 2006.

22. J. Radhakrishnan. Tam düzgün hipergrafları örtmek için geliştirilmiş sınırlar. Information Processing Letters, 41:203–207, 1992.

23. Kunihiko Sadakane ve Roberto Grossi. Özlü veri yapılarını entropi sınırları içine sıkıştırmak. SODA, sayfa 1230–1239, 2006.

24. P. Sanders. Kişisel iletişim, 2004.

25. J. P. Schmidt ve A. Siegel. Oblivious k-probe hash fonksiyonlarının uzamsal karmaşıklığı. SIAM Journal on Computing, 19(5):775–786, Ekim 1990.

26. R. E. Tarjan ve A. C. C. Yao. Seyrek bir tablonun depolanması. Communications of the ACM, 22(11):606–611, Kasım 1979.

27. Sebastiano Vigna. Rank/select sorgularının broadword uygulaması. Proceedings of the 7th International Workshop on Efficient and Experimental Algorithms (WEA’08), sayfa 154–168, 2008.

Pratik Bir Sürüm

Pratikte basit hash fonksiyonlarının çoğu zaman gerçekten rastgele hash fonksiyonlarına benzer şekilde davrandığı gözlemlenmiştir (bu olgunun teorik incelemesi için bkz. [19]). Bu nedenle gerçek rastgele hash fonksiyonları kullanmıyoruz; bunun yerine Jenkins tarafından önerilen sezgisel hash fonksiyonunu kullanıyoruz [14]. Bu fonksiyon pratikte çok iyi performans gösterir [2, 3] ve 12 bayt uzunluğunda bir tamsayı üretir; bu özellik aşağıda açıklanan uygulamamız için ilgi çekicidir.

Uygulamamızın aşağıdaki biçimde enjeksiyonlu bir eşleme bulması gerekir

x → (g(x), f₁(x), f₂(x))

burada tüm x ∈ S ⊆ U için

• g : U → [r]
• f₁ : U → [m]
• f₂ : U → [m]

tek bir Jenkins fonksiyonu tarafından hesaplanan üç hash fonksiyonudur; her biri için dört bayt kullanılır. Bu enjeksiyonlu eşlemenin olasılığının (O(1 − 1/m)) olduğu iyi bilinmektedir; örneğin bkz. [16]. Dolayısıyla ortalama olarak (1 + o(1)) deneme yapmamız gerekecektir.

Fonksiyon g, her anahtarı r kovasından birine eşler. Daha sonra her kova (B_i) (0 ≤ i < r) için, (B_i) içindeki her anahtarın aşağıdaki biçimde verilen boş bir hücreye yerleştirilmesini sağlayacak bir yer değiştirme çifti ((d_0, d_1)) atarız:

[ (f_1(x) + d_0 f_2(x) + d_1) \bmod m. ]

Her (B_i) kovası için, ((d_0, d_1)) çiftlerinden farklı seçenekler deneriz ve bunlardan biri (B_i) içindeki tüm anahtarları başarıyla yerleştirene kadar devam ederiz. Her denemede aşağıdaki diziden bir çift kullanılır:

(0,0), (0,1), …, (0,m−1), (1,0), (1,1), …, (1,m−1), …, (m−1,m−1).

Her bir Bᵢ kovası için bir (d₀, d₁) çifti saklamak yerine, Bᵢ içindeki tüm anahtarları başarıyla yerleştiren dizideki ilk çiftin indeksini saklarız.

İndeks dizisinin entropisini daha da azaltmak için aşağıdaki açgözlü stratejiyi kullanırız: önce, boyutu s olan tüm kovaları 0 indeks değeriyle yerleştirmeyi deneriz; bu değer (0,0) çiftini temsil eder. Ardından kalan kovaları ikinci indeks değeri olan 1 ile yerleştirmeyi deneriz; bu değer (0,1) çiftini temsil eder, ve bu şekilde devam eder. Elbette yerleştirilmeyen kovaların bir listesini tutarız ve her bir kovayı yerleştirdiğimizde onu listeden çıkarırız.

Bu açgözlü sezgisel yöntemin üretim süresi, belirli bir s boyutundaki kovaları tek tek yerleştirmeye çalıştığımız ve verilen bir Bᵢ kovasını yerleştirirken tüm olası (d₀, d₁) çiftlerini araştırdığımız duruma kıyasla yaklaşık %25 daha uzundur (0 ≤ i < r). Bununla birlikte açgözlü strateji, %5'e kadar daha sıkıştırılmış fonksiyonlar elde etmemizi sağlar.

Kovaları yerleştirmek için kullanılan indeks değerlerini sıkıştırmak amacıyla, ek olarak alt doğrusal alan kullanırken ampirik entropiyle orantılı alan sağlayan birçok yöntem vardır. Bizim durumumuzda yalnızca H₀ entropisiyle ilgileniyoruz. Şemamızda bu entropi anahtar başına O(1) bittir. Literatürde [23,12], n adet değerden oluşan bir diziyi nH₀ + o(n) bit alan kullanarak sıkıştıran ve dizinin herhangi bir elemanına sabit zamanda erişimi destekleyen sıkıştırma şemaları bulunabilir. Ancak o(n) ve O(1) gösterimlerindeki gizli sabitler pratikte uygun olmayabilir. Daha pratik bir çözüm için Fredriksson ve Nikitin tarafından önerilen yöntemi [11] kullanabiliriz. Bu çözüm özellikle bizim durumumuz için ilgi çekicidir çünkü kodlama veya kod çözme tabloları gerektirmez.

A.1 Entropiyi Azaltmak İçin Açgözlü Strateji

A.2 Sıkıştırma Şemaları

Fredriksson–Nikitin Kodlaması

Bu şemada dizideki her sayıyı ayrı ayrı değişken uzunluklu bir kodlama kullanarak kodlarız. Yer değiştirme dizisindeki tüm kodlanmış sayıları bitişik bir dizide saklarız. Daha sonra her kodlanmış sayının uzunluklarını Elias–Fano kodlaması kullanarak saklarız.

Örneğin:

• 1 sayısı 0 bit kullanılarak kodlanır.
• 2 ve 3 sayıları 1 bit kullanır.
• 4, 5, 6, 7 sayıları 2 bit kullanır.

Daha genel olarak, [2ᵗ, 2ᵗ⁺¹ − 1] aralığındaki herhangi bir sayıyı kodlamak için t bit kullanırız. x sayısı için

⌈log(x + 1)⌉ − 1 bit kullanırız.

Aşağıdaki yer değiştirme dizisi verildiğinde

x₀, x₁, …, xᵣ₋₁,

önce her xᵢ değerini yukarıda açıklandığı şekilde kodlayarak bir yᵢ dizgesi elde ederiz ve tüm kodlanmış dizgeleri birleştiririz:

y₀ y₁ … yᵣ₋₁.

Daha sonra aşağıdaki diziyi saklamak için Elias–Fano kodlamasını kullanırız

|y₀|, |y₁|, …, |yᵣ₋₁|.

Bu sayede herhangi bir i için, yᵢ kodlamasının başlangıcını ve ayrıca |yᵢ| değerini belirleyebiliriz.

Elias–Fano kodlaması kullanılarak herhangi bir s₀, s₁, …, sₘ₋₁ dizisi en fazla

(∑_{i=0}^{m−1} sᵢ)/m · 2 + log m

bit kullanılarak kodlanabilir.

Dolayısıyla x₀, x₁, …, xᵣ₋₁ dizisi için toplamda Y + Z bit kullanırız; burada

Y = ∑{i=0}^{r−1} |yᵢ| = ∑{i=0}^{r−1} (⌈log(xᵢ + 1)⌉ − 1).

Artık σ(0), σ(1), …, σ(r−1) dizisinin Fredriksson–Nikitin kodlamasının alan kullanımını hesaplayabiliriz.

Ayrıca Z değerinin beklenti bakımından şu değerden küçük olduğunu da biliyoruz

r(2 + ⌈log(Y/r)⌉).

r yerine n/λ koyarsak

Z ≤ (n/λ) (2 + ⌈log(λ(log e + e^{−dλ}) + O(λ³/n))⌉).

Sonuç olarak Fredriksson–Nikitin kodlamasının kullandığı toplam alan

n(log e + O((log λ + 1)/λ)) + O(λ²).

PHF, MPHF ve k‑PHF üretebilen sıkıştırılmış hash‑and‑displace algoritmasının bir sürümünü uyguladık. Algoritma giriş olarak bir anahtar kümesi S ve aşağıdaki parametreleri alır.

A.3 Girdi Parametreleri

1. λ — kova başına anahtar sayısı. Bu parametre, elde edilen fonksiyonların açıklama boyutu ile üretim hızı arasındaki dengeyi belirler. Ayrıca kova sayısını r = ⌈n / λ⌉ şeklinde hesaplamak için kullanılır.

2. k — k‑PHF üretirken her bin başına izin verilen maksimum anahtar sayısıdır. PHF üretilirken 1 olarak ayarlanır.

3. α — hash tablosu yük faktörü. Bu parametre bin sayısını (hash fonksiyonunun aralığını) belirler. k‑mükemmel hashleme durumunda bin sayısı

m = ⌈ n / (k × α) ⌉

şeklindedir.

Aşağıda göreceğiz ki eğer m = (1 + ε)n ve ε > 0 sabit bir değer ise, Σ dizisinin hesaplanması beklenen doğrusal zamanda başarılı olur. Ayrıca σ(i) sayılarının, 0 ≤ i < r için küçük olduğunu da göstereceğiz: σ(i) sınırlı beklentiye sahip geometrik dağılımlıdır. Dolayısıyla E(σ(i)) bir sabitle sınırlıdır. Bunun sonucu olarak [11] gibi bir sıkıştırma şeması kullanıldığında (σ(i), 0 ≤ i < r) dizisi O(n) bit içinde kodlanabilir ve yine de rastgele erişime izin vererek h fonksiyonunun sabit zamanda değerlendirilmesini korur.

Lemma 3. [18, s. 97] Eğer X, λ ≥ 1 tamsayısı için Poisson(λ) dağılımına sahipse, o zaman …

B Daha Basit Analiz

Tanımlar:

• a=(λ, t) = |{ i | |Bᵢ| = t }|
• a≥(λ, t) = |{ i | |Bᵢ| ≥ t }|
• b=(λ, t) = |{ x ∈ S | |B_{g(x)}| = t }|
• b≥(λ, t) = |{ x ∈ S | |B_{g(x)}| ≥ t }|

Lemma 4. Her sabit t ≤ 2λ + 2 için, yüksek olasılıkla (keyfi c > 0 için 1 − n^{−c}):

• a=(λ, t) = r · Poisson(λ, t)(1 + o(1))
• a≥(λ, t) = r · Poisson(λ, ≥ t)(1 + o(1))
• b=(λ, t) = n · Poisson(λ, t − 1)(1 + o(1))
• b≥(λ, t) = n · Poisson(λ, ≥ t − 1)(1 + o(1))

Gösterimi basitleştirmek için aşağıdaki hesaplamalarda 1 + o(1) çarpanını ve yuvarlama etkilerini göz ardı ediyoruz.

İki büyüklükle ilgileniyoruz:

1. Bᵢ kovası için uygun bir hash fonksiyonu f_{σ(i)} bulunana kadar gereken deneme sayısı; bu E(σ(i)) ile ölçülür.
2. PHF h fonksiyonunu saklamak için gereken alan, yani tüm σ(i) değerleri. Bunu ⌊log₂(σ(i))⌋ + 1 ile yaklaşıklarız.

Aşağıdaki rastgele değişkeni tanımlayalım

s = ∑_{i<r} log₂(σ(i)).

E(s) değerini tahmin ederiz.

B.1 Ağır Kovalar

Ağır kovaların etkisi Bölüm 3.1'de gösterildiği gibi ihmal edilebilir düzeydedir.

B.2 Ortalama Üstü Kova Boyutları

Boyutu λ + 1 < t ≤ 2λ olan kovalar için her φₗ fonksiyonunun başarı olasılığı en az

(1/2)^{2λ}

kadardır.

Dolayısıyla

E(σ(i)) ≤ 2^{2λ}

ve

E(log σ(i)) ≤ 2λ.

Bu tür kovaların sayısı en fazla r = n/λ'dir. Test edilen fonksiyonların beklenen sayısı O(r · 2^{2λ}) olur. Deneme başına 2λ maliyet yüklendiğinde toplam maliyet O(n · 2^{2λ}) olur. σ(i) indekslerini saklamak için gereken bit sayısının beklenen değeri O(rλ) = O(n)'dir.

B.3 Ortalama Altı Kova Boyutları

Boyutu t < λ olan kovalar sorun çıkarabilir çünkü tablo neredeyse dolu olabilir ve tek bir hash değeri için başarı olasılığı küçük hale gelebilir. Bu kovalar için m değerinin n'den sabit bir (1 + ε) katsayısı kadar büyük olması kritik önemdedir.

Bᵢ kovasının boyutunun 1 ≤ t = |Bᵢ| ≤ λ + 1 olduğunu varsayalım. Herhangi bir φₗ fonksiyonu için başarı olasılığı en az

(ε / (1 + ε))^{λ + 1}

kadardır.

Dolayısıyla

E(σ(i)) ≤ ((1 + ε)/ε)^{λ + 1} = O((1/ε)^λ)

ve

E(log σ(i)) = O(log(1/ε) · λ).

r = n/λ kova bulunduğu dikkate alındığında, küçük kovalar için σ(i) değerlerini saklamak amacıyla gereken bit sayısının beklenen değeri O(n log(1/ε)) olur.

Not. Daha ayrıntılı bir analiz, E(σ(i)) için üst sınırın λ ≥ 2 için O((1/ε)^λ) değerine ve hatta λ = 1 için O(log(1/ε)) değerine indirilebileceğini göstermektedir.

Boş kovalar, genellikle φ₁ olan en kısa isimli hash fonksiyonuna atanır. Tüm sonuçları topladığımızda Teorem 2'nin sonucunu elde ederiz.