WADS 1999, LNCS 1663, s. 49–54’te kısa bir sürümü yayımlanmıştır. © Springer Verlag. Çevrim içi erişim: http://www.brics.dk/~pagh/papers/
Hash ve Yer Değiştirme: Minimal Mükemmel Hash Fonksiyonlarının Verimli Değerlendirilmesi
Rasmus Pagh¹
BRICS², Bilgisayar Bilimi Bölümü, Aarhus Üniversitesi, 8000 Aarhus C, Danimarka
E‑posta: pagh@brics.dk
Özet
(Minimal) mükemmel hash fonksiyonlarının oluşturulmasına yönelik yeni bir yöntem açıklanmaktadır. Bu teknik, iki seviyeli hashing şemalarında kovaların çözülmesiyle ilişkili ek yükü önemli ölçüde azaltır. Bir hash fonksiyonunun değerlendirilmesi, ilkel bit işlemleri dışında yalnızca bir çarpma ve birkaç toplama gerektirir. Belleğe erişim sayısı ikidir ve bunlardan biri sabit bir konumadır. Bu durum, önceki minimal mükemmel hashing şemalarının probe performansını iyileştirir ve bunun en iyi mümkün değer olduğu gösterilir. Boyutu n olan bir küme için hash fonksiyonunun tanımı (“programı”) O(n) kelime yer kaplar ve beklenen O(n) zamanda oluşturulabilir.
Bu makale, sonlu evren (U = {0, \ldots, u-1}) içindeki n-alt kümeler için mükemmel olan hash fonksiyon sınıflarını ele almaktadır. (S \in \binom{U}{n}) için — yani U’nun boyutu n olan alt kümeleri — mükemmel bir sınıf, S üzerinde bire bir olan bir fonksiyon içerir (“S için mükemmel”). Aralığı ({0, \ldots, a-1}) olan mükemmel sınıfları ele alıyoruz.
Mükemmel bir hash fonksiyon sınıfı statik sözlükler kurmak için kullanılabilir ((S \in \binom{U}{n}) kümelerini depolayan ve üyelik sorgularını destekleyen veri yapıları, “(u \in S?)”). S kümesi üzerinde bire bir olan bir h fonksiyonu saklanır ve her (s \in S) elemanı için a elemanlı bir tablonun h(s) girişinde s saklanır. s için bir üyelik sorgusu, tablodaki h(s) girişindeki değerle s karşılaştırılarak işlenir. Bu amaçla mükemmel hash fonksiyonlarının kullanılmasının çekiciliği, sınıfın çeşitli özelliklerine bağlıdır.
- Değerlendirme verimliliği; hesaplama maliyeti ve tanım üzerinde yapılan probe sayısı açısından.
Uygun mükemmel hash fonksiyon sınıfları için bu soruların tümüne verilen yanıtların tatmin edici olduğu ortaya çıkmaktadır; yani, beklenebilecek en iyi düzeye (az çok) ulaşmak mümkündür.
Buna rağmen, kuramsal olarak en iyi şemalar pratikte sınırlı kullanım görmüş ve genellikle iyi çalışan sezgisel yöntemlerle değiştirilmiştir. Bu nedenle, hem kuramsal hem de pratik açıdan iyi özelliklere sahip sınıflar bulmak hâlâ ilgi çekicidir.
¹ Kısmen Avrupa Birliği ESPRIT Uzun Vadeli Araştırma Programı tarafından, proje numarası 20244 (ALCOM‑IT) kapsamında desteklenmiştir.
² Bilgisayar Biliminde Temel Araştırma, Danimarka Ulusal Araştırma Vakfı Merkezi.
Bu makale, çarpma işlemini destekleyen birim maliyetli word RAM modelinde, yukarıdaki 2 ve 3 numaralı maddeler açısından en iyi sonuçlarla eşleşen ve aynı zamanda bilinen en iyi değerlendirme verimliliğini geliştiren basit bir mükemmel hash fonksiyon sınıfı sunmaktadır. Gerekli hesaplama miktarı (sabit) yaklaşık yarıya indirilmektedir ve fonksiyon tanımına yapılan bağlama duyarlı probe sayısı (fonksiyon argümanına ve/veya önceki probelara bağlı olanlar) ikiden bire düşürülmektedir; bu da en iyi değerdir. Bu son özellik özellikle önemlidir; çünkü mükemmel hash fonksiyonu ikincil depolama üzerinde bulunduğunda baskın maliyet arama süresidir.
Bu sınıf, bellek kullanımı açısından (katı analizlere sahip şemalar arasında) yalnızca fonksiyon değerlendirmesi bakımından oldukça karmaşık ve verimsiz olan sınıflar tarafından aşılmaktadır. Genel olarak bu sınıfın pratikte çekici olduğu düşünülmektedir.
Czech, Havas ve Majewski mükemmel hashing üzerine kapsamlı bir inceleme sunmaktadır [3]. En önemli sonuçlardan bazılarını gözden geçiriyoruz.
Fredman, Komlós ve Szemerédi [8], aralığı a = O(n) olan ve sabit zamanda değerlendirilebilen, alan açısından verimli mükemmel hash fonksiyonlarının geliştirilebildiğini göstermiştir. Hesaplama modeli, U’nun bir elemanının bir makine kelimesine sığdığı³ ve aritmetik işlemler ile bellek erişimlerinin birim maliyetli olduğu bir word RAM modelidir. Bundan sonra bu hesaplama modelinde sabit zamanda değerlendirilebilen ve aralığı a = O(n) olan hash fonksiyonlarına odaklanacağız.
Bir FKS hash fonksiyonunun tanımı O(n) makine kelimesi yer kaplar. Ek bir dolaylı adresleme seviyesi karşılığında minimal mükemmel hash fonksiyonuna dönüştürülebilir; yani aralığı a = n olur. Bu durumda tanım boyutu 6n kelimedir (doğrudan bir uygulamada) ve değerlendirme sırasında üç kelimeye probe yapılır. Schmidt ve Siegel [12], kompakt kodlama teknikleri kullanarak tanımı en iyi değer olan O(n + log log u) bit’e sıkıştırır. Bu şema uygulanması zor bir yapıya sahiptir ve değerlendirme süresi (sabit olsa da) oldukça yüksektir. Bu nedenle esas olarak kuramsal ilgi taşır. Aşağıda, fonksiyonları O(n) makine kelimesinde saklanabilen sınıfları ele alacağız.
Sabit sorgu süresine sahip mükemmel bir hash fonksiyonunu deterministik olarak oluşturmak için bilinen en hızlı algoritma O(n log n) zaman çalışır [11]. Rastgeleleştirilmiş oluşturma algoritmaları daha iyi beklenen performans sunar. Algoritmanın rastgele bit kaynağına erişimi varsa bir FKS mükemmel hash fonksiyonu beklenen O(n) zamanda oluşturulabilir.
Minimal mükemmel hashing üzerine bazı çalışmalar, algoritmanın gerçekten rastgele fonksiyonlar seçip saklayabildiği varsayımı altında yapılmıştır [2, 9]. Gerçekten rastgele fonksiyonların alan gereksinimleri uygulamayı uygun olmaktan çıkardığı için pratikte pseudo‑rastgele fonksiyonlarla yetinmek gerekir. Deneysel çalışmalar, sınırlı rastgelelik özelliklerinin çoğu zaman tam rastgelelik kadar iyi olduğunu göstermektedir.
Fox ve arkadaşları [6, 7], burada sunulan sınıfla birçok özelliği paylaşan bazı sınıfları incelemiştir. Sonuçları güçlü bir pratik performans göstermekte ve depolama gereksinimlerinin burada kanıtlanandan daha da azaltılabileceğini düşündürmektedir. Ancak çoğu durumda iyi performans göstermek ile en kötü durumda iyi performans göstermek arasında önemli fark olabileceği unutulmamalıdır. [3, Bölüm 6.7]’de, minimal mükemmel hash fonksiyonları geliştirmek için yayımlanmış üç algoritmanın (deneysel verilere dayanarak) beklenen polinom zaman çalıştığı iddia edilmesine rağmen gerçekte beklenen üstel çalışma süresine sahip olduğu gösterilmiştir. Ancak kötü davranış o kadar nadir gerçekleşmiştir ki deneyler sırasında karşılaşılmamıştır.
³ Bu ciddi bir kısıtlama değildir; çünkü evrensel sınıflar, (O(\log n + \log \log u)) bitlik tanım ve (O(n^2)) aralığı olan (verimli) mükemmel hash fonksiyonları sağlar. Bu, söz konusu evrenin boyutunun (O(n^2))’ye indirilebileceği anlamına gelir.
1.1 Önceki Çalışmalar
1.2 Tarjan–Yao Yer Değiştirme Şeması
2 Bir Mükemmel Hash Fonksiyon Sınıfı
Burada sunulan hash fonksiyon sınıfı, Tarjan ve Yao [13] tarafından önerilen erken dönem bir mükemmel hash fonksiyon sınıfının bir varyasyonu olarak görülebilir. Onların sınıfı u = O(n²) boyutunda bir evren gerektirir (bunu c > 2 sabiti için u = O(nᶜ) olacak şekilde iyileştirirler).
Fikir, evreni her biri O(n) boyutunda bloklara ayırmak ve her bloğa bir “yer değiştirme” değeri atamaktır. j’inci blok içindeki i’inci eleman i + d_j değerine eşlenir; burada d_j blok j’nin yer değiştirme değeridir. Uygun yer değiştirme değerleri her zaman bulunabilir, ancak genel durumda yer değiştirme değerlerinin (ve dolayısıyla hash tablo boyutunun) n’den büyük olması gerekebilir.
Bloklar içindeki eleman dağılımına uygulanan bir “harmonik azalma” koşulu, ({0, \ldots, n}) aralığında uygun yer değiştirme değerlerinin bulunabilmesini ve bunların bloklardaki eleman sayısına göre azalan sırayla “açgözlü” bir biçimde bulunabilmesini sağlar. Harmonik azalmayı sağlamak için Tarjan ve Yao önce diğerine “dik” bir yer değiştirme gerçekleştirir.
Bu makalenin temel gözlemi, evrenin boyutunun O(n²)’ye indirgenmesinin ve ayrıca harmonik azalmanın evrensel hash fonksiyonları kullanılarak elde edilebileceğidir. Başka bir ifadeyle, (evrensel) bir hash tablosundaki kovalar yer değiştirmeler kullanılarak çözülebilir.
Şekil 1: Tarjan–Yao yer değiştirme şeması
Evrensellik kavramı [1], sınıfımızın analizinde önemli bir rol oynar. Aşağıdaki gösterimi kullanıyoruz.
Tanım 1. (H_r = {h_1, \ldots, h_k}) fonksiyon sınıfı, (h_i : U \to {0, \ldots, r-1}), herhangi (x, y \in U), (x \ne y) için
Prᵢ[ hᵢ(x) = hᵢ(y) ] ≤ c / r
koşulunu sağlıyorsa c-evrenseldir.
Sabit c değerine sahip birçok böyle sınıf bilinmektedir, örneğin bkz. [4]. Uygulamamız açısından önemli nokta, fonksiyonlarının verimli şekilde saklanmasına ve değerlendirilmesine izin veren evrensel sınıfların bulunmasıdır. Daha spesifik olarak, O(log u) (hatta O(log n + log log u)) bitlik depolama yeterlidir ve fonksiyonları değerlendirmek için sabit sayıda basit aritmetik ve bit işlemi yeterlidir. Ayrıca c genellikle (1 \le c \le 2) aralığındadır. Bundan sonra yalnızca bu tür verimli evrensel ailelere atıfta bulunacağız.
Sınıf tanımındaki ikinci bileşen bir yer değiştirme fonksiyonudur. Tarjan ve Yao’nun tam sayı toplamasını kullanmasını genelleyerek bloklar üzerinde herhangi bir grup yapısının kullanılmasına izin veriyoruz. Bir bloğun ({0, \ldots, a-1}) elemanlarının, grup işlemlerinin uygulanabildiği ((G, ⊞, e)) grubundaki (farklı) elemanlara karşılık geldiği varsayılır. Grup işleminin ve eleman tersinin sabit zamanda hesaplanabildiğini varsayıyoruz.
Tanım 2. ((G, ⊞, e)) grubu için bir yer değiştirme fonksiyonu şu biçimde bir fonksiyondur:
x ↦ x ⊞ d
burada (d \in G). d elemanına fonksiyonun yer değiştirme değeri denir.
Aşağıda yer değiştirme fonksiyonlarını basitçe a modunda toplama olarak düşünmek faydalı olabilir. Artık sınıfı tanımlamaya hazırız.
Tanım 3. ((G, ⊞, e)) bir grup, (D \subseteq G) bir yer değiştirme değerleri kümesi ve (H_a) ile (H_b) sırasıyla (c_f)- ve (c_g)-evrensel olsun. U’dan G’ye aşağıdaki fonksiyon sınıfını tanımlarız:
H(⊞, D, a, b) = { h | h(x) = f(x) ⊞ d_{g(x)}, f ∈ H_a, g ∈ H_b, d_i ∈ D için i = 0, …, b − 1 }.
(H(⊞, D, a, b)) içindeki bir fonksiyonun değerlendirilmesi, (g(x)) tarafından belirlenen bir yer değiştirme fonksiyonunun (f(x)) değeri üzerinde uygulanmasından oluşur. Tarjan–Yao şeması açısından bakıldığında, (g) U’nun her elemanına bir blok numarası atar ve (f) onun blok içindeki numarasını belirler.
Bir sonraki bölüm, (a > c_f n / 4) ve (b ≥ 2 c_g n) olduğunda, ortaya çıkan fonksiyonun mükemmel olmasını sağlayacak (f), (g) ve yer değiştirme değerlerinin bulunabileceğini gösterecektir. Bu sınıf b adet yer değiştirme değerinin saklanmasını gerektirir. Makul bellek kullanımı olan durumlara odaklanarak bundan sonra (b = O(n)) olduğunu ve (D) kümesinin elemanlarının bir makine kelimesinde saklanabildiğini varsayacağız.
(H(⊞, D, a, b)) içindeki fonksiyonların aralığı ({x ⊞ d \mid x ∈ {0, …, a−1}, d ∈ D}) kümesidir. Bu kümenin boyutu söz konusu gruba ve D kümesine bağlıdır. İlgi alanımız aralığı n (veya en fazla O(n)) olan fonksiyonlar olduğundan (a ≤ n) varsayımını yapıyoruz. Bölüm 3.2’de daha büyük aralığa sahip sınıflar kısaca ele alınacaktır.
Sınıfımız (grup işleci n modunda toplama ve (D = {0, …, n−1}) ile) [5, Bölüm 4]’te tanımlanan sınıfın özel bir durumudur. Orada bu sınıftan rastgele seçilen fonksiyonların bazı ilginç özellikleri gösterilmiştir, ancak sınıf içinde mükemmel fonksiyonların bulunması konusu ele alınmamıştır.
Bu bölüm, uygun D, a ve b değerleri için (H(⊞, D, a, b)) sınıfı içinde mükemmel hash fonksiyonları bulmak amacıyla yapıcı (ancak rastgeleleştirilmiş) bir yöntem sunmaktadır. Uygun yer değiştirme değerlerinin varlığının anahtarı, (f) ve (g) için belirli bir “iyi olma” koşuludur. Tanımlayalım:
B(g, i) = { x ∈ S | g(x) = i }
Bu ifade, (g) tarafından verilen i’inci bloktaki elemanları belirtir.
İlk koşul, (f) ve (g)’nin evreni başarıyla ab boyutuna indirgediğini söyler (açıktır ki ((f(x₁), g(x₁)) = (f(x₂), g(x₂))) ise yer değiştirme değerlerinden bağımsız olarak x₁ ve x₂ çakışacaktır). İkinci koşul Tarjan ve Yao’nun harmonik azalma koşulunu ima eder (ancak aşağıdaki kısmı anlamak için onların koşulunu bilmek gerekli değildir).
Rastgele olarak r-iyi bir hash fonksiyonu çifti bulma olasılığını tahmin eden teknik bir lemma gösteriyoruz.
2.1 Analiz
Tanım 4. (r ≥ 1) olsun. ((f, g) ∈ H_a × H_b) çifti, aşağıdaki koşullar sağlanıyorsa (S için) r-iyidir:
- (x ↦ (f(x), g(x))) fonksiyonu S üzerinde bire birdir.
Lemma 5. (a ≥ c_f n / 4r) ve (b ≥ 2 c_g r n) olduğunu varsayalım. Herhangi (S ∈ \binom{U}{n}) için rastgele seçilen ((f, g) ∈ H_a × H_b) çifti S için pozitif olasılıkla r-iyidir.
İspat. (c_g)-evrensellikten dolayı
∑ᵢ (|B(g,i)| choose 2)
ifadesinin beklenen değeri
(n choose 2) c_g / b < c_g n² / (2b)
ile sınırlıdır.
Markov eşitsizliği uygulanırsa bu toplamın değeri (n / 4r)’den küçük olur ve bunun olasılığı
1 − 2 c_g r n / b
ifadesinden büyüktür.
Ayrıca
|B(g,i)|² ≤ 4 (|B(g,i)| choose 2)
((|B(g,i)| > 1) için) olduğundan
∑_{i, |B(g,i)|>1} |B(g,i)|² ≤ n / r
sonucuna ulaşırız.
Bu eşitsizliklerin sağlandığı bir (g) fonksiyonu verildiğinde, (x ↦ (f(x), g(x))) fonksiyonunun S üzerinde bire bir olma olasılığını sınırlarız. Öncekiyle benzer bir akıl yürütmeyle, rastgele seçilen f için (B(g,i)) içindeki elemanlar arasındaki çakışmaların beklenen sayısı en fazla
(|B(g,i)| choose 2) c_f / a
değeridir.
i üzerinde toplandığında toplam beklenen çakışma sayısı
c_f n / (4 r a)
ifadesinden küçüktür.
Dolayısıyla çakışma olmama olasılığı
1 − c_f n / (4 r a)
ifadesinden büyüktür.
Koşullu olasılık yasasına göre her iki r-iyi koşulunun sağlanma olasılığı yukarıdaki olasılıkların çarpımıdır.
Teorem 6. ((f, g) ∈ H_a × H_b) çifti (S ∈ \binom{U}{n}) için r-iyi olsun, (r ≥ 1) ve (|D| ≥ n) olsun. Bu durumda
x ↦ f(x) ⊞ d_{g(x)}
fonksiyonunun S üzerinde bire bir olmasını sağlayan (d_0, …, d_{b−1} ∈ D) yer değiştirme değerleri vardır.
İspat. Yer değiştirme (d_i)’nin şu elemanlar üzerinde kullanıldığını gözlemleyin:
{ f(x) | x ∈ B(g,i) }.
Ayrıca herhangi (h ∈ H(⊞, D, a, b)) fonksiyonu her (B(g,i)) üzerinde bire birdir.
Yer değiştirme değerlerini bloklardaki eleman sayısına göre azalmayan sırada tek tek atıyoruz. k’inci adımda en büyük k−1 küme
{ B(g,i) | i ∈ I }, |I| = k−1
zaten yer değiştirmiştir ve şimdi (B(g,j)) kümesini önceki yer değiştirilmiş elemanlarla çakışma olmadan yer değiştirmek isteriz.
(|B(g,j)| ≤ 1) ise bu durum triviyaldir çünkü (|D| ≥ n). Bu nedenle (|B(g,j)| > 1) varsayalım. Aşağıdaki iddia ispatı tamamlar.
İddia 7. (|B(g,j)| > 1) ise rastgele seçilen (d ∈ D) değeri (B(g,j))’yi çakışma olmadan yer değiştirme işlemiyle eşleyebilir; bunun olasılığı pozitiftir (özellikle (1 − 1/r)’den büyüktür).
İspat. Kullanılamayan yer değiştirme değerleri şu kümededir:
{ f(x)⁻¹ ⊞ f(y) ⊞ d_i | x ∈ B(g,j), y ∈ B(g,i), i ∈ I }.
Bu kümenin boyutu en fazla
|B(g,j)| · ∑_{i∈I} |B(g,i)|
olur ve bu değer
∑_{i, |B(g,i)|>1} |B(g,i)|² ≤ n / r
ifadesinden küçüktür; burada önce azalmayan sıralama ve (|B(g,j)| > 1) kullanılmış, ardından r-iyi koşulu uygulanmıştır.
Dolayısıyla D kümesinde
(1 − 1/r) |D|
adet iyi yer değiştirme değeri bulunmalıdır.
Eğer (a ≥ (c_f / 4 + ε)n) ve (b ≥ (2 c_g r + ε)n) ise, r-iyi bir hash fonksiyonu çifti beklenen O(n) zamanda bulunabilir (ve r-iyi olduğu doğrulanabilir).
Teorem 6’nın kanıtı ve özellikle İddia 7, ((1 + ε))-iyi bir ((f, g)) çifti için D içinden rastgele yer değiştirme değerleri deneme stratejisinin, birden fazla eleman içeren tüm blokları blok başına beklenen (1/ε) denemede başarıyla yer değiştirdiğini gösterir. D içinden O(n) adet rastgele eleman O(n) zamanda seçilebiliyorsa, bu süreç beklenen O(n/ε) = O(n) zamanda çalışır.
Son olarak, yalnızca tek eleman içeren tüm blokları yer değiştirmek kolaysa (Bölüm 2.2’de ele aldığımız örneklerde olduğu gibi), tüm yapılandırma beklenen O(n) zamanda çalışır.
1-iyi bir ((f, g)) çifti için Teorem 6 yalnızca uygun yer değiştirme değerlerinin varlığını garanti eder.
Lemma 5, a ≥ (cf olduğunda
Sınıfımızı oldukça soyut bir düzeyde tanımladık, bu nedenle bazı belirli örneklere bakalım. Özellikle grup seçimi ve yer değiştirme değerleri kümesi ele alınır. Basitlik amacıyla sabiti 1 olan evrensel sınıflar kullanıyoruz. Yer değiştirme değerlerinin sayısı b, mükemmel fonksiyonların varlığını garanti etmek için en az 2n olmalı ve beklenen doğrusal zamanlı yapılandırma için en az (2 + ϵ)n, ϵ > 0 olmalıdır. Kolaylık açısından sınıfların kendi içinde yeterli tanımları verilmiştir.
Toplama işlemiyle birlikte tam sayılar kümesi grup olarak oldukça doğal bir seçimdir. D = {0, . . . , n − 1} için aşağıdaki sınıf elde edilir:
2.2 Sınıfın Örnekleri
Toplama
HZ = {h | h(x) = f(x) + d_{g(x)}, f ∈ H_{n/4}, g ∈ H_b, 0 ≤ d_i < n for i = 0, . . . , b − 1}
Bu sınıftaki hash fonksiyonlarının aralığı {0, . . . , 5/4 n − 2} kümesidir, dolayısıyla minimal değildir.
n Modunda Toplama
Önceki sınıf, daha pahalı bir grup işleci olan n modunda toplama kullanılması pahasına minimal hâle getirilebilir:
HZ_n = {h | h(x) = (f(x) + d_{g(x)}) mod n, f ∈ H_n, g ∈ H_b, 0 ≤ d_i < n for i = 0, . . . , b − 1}
n mod işleminin argümanı 2n’den küçük olduğundan, bunun bir karşılaştırma ve bir çıkarma kullanılarak uygulanabileceğine dikkat edin.
Bit Düzeyinde Exclusive Or
Uzunluğu ℓ = ⌈log n⌉ olan bit dizileri kümesi, bit düzeyinde exclusive or işlemi altında Z_2^ℓ grubunu oluşturur; bu işlem ⊕ ile gösterilir. {0, . . . , n − 1} kümesini ikili gösterimlerinin ℓ bitlik dizilerine karşılık gelecek şekilde alırsak şu sınıf elde edilir:
HZ_2^ℓ = {h | h(x) = f(x) ⊕ d_{g(x)}, f ∈ H_{2^ℓ−1}, g ∈ H_b, d_i ∈ {0, 1}^ℓ for i = 0, . . . , b − 1}
Bu sınıftaki fonksiyonların aralığı {0, . . . , 2^ℓ − 1} sayılarıyla örtüşür. Bu nedenle yalnızca n iki’nin kuvveti olduğunda minimaldir. Bununla birlikte b ≥ 4n^2 / 2^ℓ olduğunda, yer değiştirme değerleri kümenin elemanlarının {0, . . . , n − 1} aralığına eşlenmesini sağlayacak şekilde seçilebilir. Birden fazla eleman içeren kümeler için tüm yer değiştirme değerleri {0,1}^{ℓ−1} kümesinden seçilebilir ve tek elemanlar istenen herhangi bir değere yer değiştirilebilir. Kümede bulunmayan bazı elemanlar {0, . . . , n − 1} aralığının dışına eşlenebileceğinden, n − 1’den büyük değerler için bir kontrol eklenmelidir.
Bölüm 2.1’deki tartışma, yukarıdaki sınıflarda mükemmel fonksiyonların verimli biçimde bulunabileceğini ima eder. Ayrıca tüm yer değiştirme değerlerinin b⌈log n⌉ bit içine "paketlenebileceğini" de not edin.
Teorem 8
S ∈ (U choose n) ve ϵ > 0 olsun. Depolama gereksinimi (2 + ϵ)n kelime (veya (2 + ϵ)n⌈log n⌉ bit) olan HZ, HZ_n ve HZ_2^ℓ sınıflarında bir mükemmel hash fonksiyonu beklenen O(n) zamanda bulunabilir.
HZ_n için yapılandırma algoritmasının ve değerlendirme fonksiyonunun sözde kodu Ek A’da verilmiştir.
2.2.1 Yapılandırma Zamanı
3 Varyantlar
Bu bölüm, önceki bölümde sunulan temel şemanın bazı varyantlarını açıklar.
3.1 Birinin Bedeline İki Hash Fonksiyonu
2ab, belirtilen r-iyilik olasılığı buradan elde edilir.
Giriş bölümünde, yalnızca tanıma yapılan sorgu sayısı açısından değil, aynı zamanda yapılan hesaplama miktarı açısından da verimli olan bir sınıf sunacağımızı söylemiştik. İlk bakışta f ve g hash fonksiyonlarının değerlendirilmesi, burada sunulan şemanın hesaplama maliyetini örneğin FKS şemasıyla karşılaştırılabilir kılıyor gibi görünebilir. Ancak yararlanabileceğimiz bir avantajımız vardır: Kullanılan hash fonksiyonları önceden sabittir; diğer şemalarda ise ikinci hash fonksiyonunun seçimi birincinin değerine bağlıdır. İki evrensel hash fonksiyonumuzu tek bir (c,2)-evrensel hash fonksiyonu ile nasıl “benzetebileceğimizi” göstereceğiz.
Tanım 9
V = {0, . . . , ab − 1} olsun. p_f : V → {0, . . . , a − 1} ve p_g : V → {0, . . . , b − 1} fonksiyonları, x → (p_f(x), p_g(x)) eşlemesi V üzerinde 1–1 ise V’yi ayrıştırıyor denir.
H_ab, aralığı {0, . . . , ab − 1} olan bir (c,2)-evrensel hash fonksiyonları sınıfı olsun ve p_f ile p_g {0, . . . , ab − 1} kümesini ayrıştırsın. {p_f ∘ h | h ∈ H_ab} ve {p_g ∘ h | h ∈ H_ab} sınıflarının (c,2)-evrensel ve dolayısıyla c-evrensel olduğunu göstermek zor değildir. Ancak olası bağımlılıklar nedeniyle bu durum, rastgele seçilen h ∈ H_ab için (p_f ∘ h, p_g ∘ h) çiftinin pozitif olasılıkla r-iyi olacağını doğrudan garanti etmez. Şimdi, yer değiştirme değerlerinin sayısında küçük bir bedel ödeyerek bunun mümkün olduğunu göstereceğiz.
Lemma 5b
H_ab bir (c,2)-evrensel sınıf olsun ve p_f ile p_g {0, . . . , ab − 1} kümesini ayrıştırsın. ab ≥ c n(n + 4ra)/2 olduğunu varsayalım. Herhangi bir S ∈ (U choose n) için, rastgele seçilen h ∈ H_ab ile elde edilen (p_f ∘ h, p_g ∘ h) çifti S için r-iyidir ve bu durumun olasılığı pozitiftir; yani
1 − c n(n + 4ra) / (2ab)
değerinden büyüktür.
Kanıt.
h ∈ H rastgele ve eşit olasılıkla seçildiğinde, S içindeki eleman çiftleri arasındaki beklenen çakışma sayısı ≤ (n choose 2) c/ab < c n^2 / (2ab) olur. Dolayısıyla bir çakışmanın meydana gelme olasılığı c n^2 / (2ab)’den küçüktür. Ayrıştırma fonksiyonlarının birebirliği kullanıldığında, aynı durum x → ((p_f ∘ h)(x), (p_g ∘ h)(x)) için de geçerlidir. {p_g ∘ h | h ∈ H_ab} sınıfı c-evrensel olduğundan, Lemma 5’in kanıtındaki argüman şu durumun
∑_{i, |B(p_g∘h,i)|>1} |B(p_g ∘ h, i)|^2 > n/r
2crn / b’den küçük bir olasılıkla gerçekleştiğini gösterir. Ayrıca
c n^2 / (2ab) + 2crn / b = c n(n + 4ra) / (2ab)
eşitliği sağlandığından, belirtilen r-iyilik olasılığı elde edilir.
{0, . . . , ab − 1} kümesinin ayrıştırılması, a veya b iki’nin kuvveti olduğunda verimli biçimde yapılabilir. Bu durumda p_f ve p_g uygun bitleri seçer. Daha genel olarak:
- p_f(u) = u div b, p_g(u) = u mod b
- p_f(u) = u mod a, p_g(u) = u div a
ifadeleri h fonksiyonunun aralığını ayrıştırmak için doğal seçimlerdir.
Giriş bölümündeki iddiaya geri dönersek, Dietzfelbinger [4] tarafından verilen (1,2)-evrensel sınıfı kullanıyoruz; bu sınıf, aralık boyutu iki’nin kuvveti olduğunda yalnızca bir çarpma, bir toplama ve bazı basit bit işlemleri gerektirir. a ve b değerlerini
ab ≥ (n(n + 4a) + ϵ)/2
koşulunu sağlayan iki’nin kuvvetleri olarak seçin; bu durumda p_f ve p_g kolayca hesaplanabilir. Ayrıca Bölüm 2.2’ye göre yer değiştirme fonksiyonunun karmaşıklığı düşük olabileceğinden, (birkaç daha ucuz işlem dışında) tek bir çarpma işleminin yeterli olduğu savunulabilir.
En çok uygulamaya sahip oldukları için aralığı O(n) olan mükemmel hash fonksiyonlarına odaklandık. Ancak gördüğümüz sınıfları aralığı a = ω(n) olan sınıflara genellemek oldukça kolaydır. Gerekli yer değiştirme değerlerinin sayısı genel olarak b = O(n^2 / a) olur (a ≥ n^2 olduğunda evrensel bir sınıfın kendi başına mükemmel olduğunu unutmayın). Şimdiye kadarki kuramdan farklar şunlardır:
- r-iyilik genelleştirilir ve ikinci gereksinim şu olur
∑_{i, |B(g,i)|>1} |B(g,i)|^2 ≤ a/r. - Yer değiştirme değerleri kümesinin boyutu en az a olmalıdır.
3.2 Daha Büyük Aralık
4 Sorgu Sayısı Açısından Optimalitenin Kanıtı
Bu bölüm, genel olarak bir mükemmel hash fonksiyonunun tanımına yapılan sorgu sayısının ikiden daha az olamayacağını kanıtlamaya hizmet eder. Elbette kelime uzunluğu w büyük olduğunda tek sorgu yeterlidir: Eğer
w ≥ ⌈log n⌉ + ⌈u/b⌉
ise tüm kümenin bir bitmap’i ve her kelimede rank bilgisi b kelime içine yerleştirilebilir ve tek sorgulu minimal mükemmel hashing kolaydır. Ayrıca bir mükemmel hash fonksiyonu w bit ile tanımlanabiliyorsa tek sorgu açıkça yeterlidir. Bu sınırlar optimuma oldukça yakındır.
Teorem 10
H = {h₁, . . . , h_k}, h_i : U → {0, . . . , a − 1} ve u ≥ 2a olacak şekilde (U choose n) için bir mükemmel hash fonksiyonları sınıfı olsun; n ≥ 2. Fonksiyonların w ≥ log u boyutunda b kelime kullanılarak tanımlanabildiğini ve tek bir kelime sorgusu ile değerlendirilebildiğini varsayalım. O hâlde
w ≥ (c n^2 / a) / (1 + ab/u − 1),
burada c > 0 sabittir.
Kanıt.
U_i ile, i’inci kelimenin sorgulandığı U alt kümesini gösterelim. B ⊆ {0, . . . , b − 1} kümesini, U_B = ⋃_{i∈B} U_i kümesinin boyutu en az 2a olacak şekilde seçeceğiz. Güvercin yuvası ilkesine göre B’nin boyutu ⌈2ab / u⌉ olacak şekilde seçilebilir. Kritik gözlem şudur: B tarafından belirlenen kelimeler, U_B’nin herhangi bir n-alt kümesi için bir mükemmel hash fonksiyonunu tanımlamak üzere yeterli bilgiyi içermelidir. [10, Theorem III.2.3.6]’ya göre böyle bir tanım en az
n(n − 1) / (4a ln 2) − 1
bit gerektirir; buradan belirtilen sınır elde edilir.
Sonuç 11
Teorem 10’daki durumda, eğer a = O(n) ise ya w = Ω(n) ya da b = Ω(u/n) kelime gereklidir.
5 Sonuç ve Açık Problemler
Yer değiştirmelerin, evrensel hash fonksiyonlarıyla birlikte, çok verimli (minimal) mükemmel hashing şemalarının temelini oluşturduğunu gördük. Değerlendirme verimliliği, düşünülebilecek en düşük sınıra oldukça yakındır; çünkü tanıma yapılan sorgu sayısı optimaldir ve yalnızca bir "pahalı" aritmetik işlem gerekir.
Bit cinsinden alan tüketimi, diğer değerlendirme açısından verimli şemalarla oldukça rekabetçi olmasına rağmen, teorik alt sınırdan [10, Theorem III.2.3.6] Θ(log n) çarpanı kadar uzaktadır. Giriş bölümünde belirtildiği gibi bazı deneyler, bu tür şemalarda alan tüketiminin yalnızca daha az yer değiştirme değeri kullanılarak optimuma oldukça yaklaştırılabileceğini göstermektedir.
Bu makaledeki sonuçların bu yönde genişletilmesi ilginç olacaktır: Düşük alan tüketimi en kötü durumda mı sağlanabilir, yoksa yalnızca ortalama durumda mı? Yer değiştirme değerlerinin sayısını azaltmak için hash fonksiyonlarının hangi rastgelelik özelliklerine ihtiyaç vardır? Bu tür soruların yanıtlanması, mükemmel hashing kuramı ile pratiğini daha da yakınlaştırmaya yardımcı olabilir.
Teşekkür:
Bu makaleyi yazmam konusunda beni teşvik eden danışmanım Peter Bro Miltersen’e teşekkür ederim. Ayrıca makalenin taslakları üzerine yararlı yorumlar yapan Martin Dietzfelbinger, Peter Frandsen ve Riko Jacob’a da teşekkür ederim.
Ek A — Yapılandırma Algoritması ve Değerlendirme Fonksiyonu
function Construct(S, b, ϵ)
n := |S|
if b < (2 + ϵ)(1 + ϵ)n then return 'Too few displacement values'
repeat
Pick f at random in a 1-universal class with range {0, . . . , n − 1}
Pick g at random in a 1-universal class with range {0, . . . , b − 1}
for i := 0 to b − 1 do
B[i] := {s ∈ S | g(s) = i}
Find permutation P such that
|B[P[i]]| ≥ |B[P[i + 1]]| for i = 0, . . . , b − 2
m := max{i | |B[P[i]]| > 1}
until (|B[P[0]]|² + ... + |B[P[m]]|² ≤ n/(1 + ϵ)) and (f is 1–1 on each B[i])
for i := 0 to m do
repeat
Pick d ∈ {0, . . . , n − 1} at random
until (T[(f(s) + d) mod n] = false for each s ∈ B[P[i]])
D[P[i]] := d
for each s ∈ B[P[i]] do
T[(f(s) + d) mod n] := true
Set E[1], . . . , E[k] to the k distinct values where T[E[i]] = false
for i := m + 1 to m + k do
Take (the unique) s ∈ B[P[i]]
D[P[i]] := (E[i − m] − f(s)) mod n
HZ_n yapılandırma algoritması ve değerlendirme fonksiyonu için sözde kod aşağıda verilmiştir. Parametre ϵ sıfırdan büyük olmalıdır; beklenen çalışma süresi ϵ ile ters orantılıdır. P permütasyonu bucket-sort kullanılarak doğrusal zamanda bulunabilir. Mod işleminin en küçük negatif olmayan kalanı hesapladığı varsayılmaktadır.
for i := 0 to n − 1 do
T[i] := false /* Dolu tablo girişlerini işaretler */
Kaynaklar
J. Lawrence Carter and Mark N. Wegman. Universal classes of hash functions. J. Comput. System Sci., 18(2):143–154, 1979. 9th Annual ACM Symposium on Theory of Computing (STOC ’77)’de sunulmuştur.
Zbigniew J. Czech, George Havas, and Bohdan S. Majewski. An optimal algorithm for generating minimal perfect hash functions. Information Processing Letters, 43(5):257–264, 1992.
Zbigniew J. Czech, George Havas, and Bohdan S. Majewski. Perfect hashing. Theoretical Computer Science, 182(1–2):1–143, 1997.
Martin Dietzfelbinger. Universal hashing and k-wise independent random variables via integer arithmetic without primes. In Proceedings of STACS ’96, pages 569–580. Springer-Verlag, 1996.
Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Automata, Languages and Programming (1990), pages 6–19.
Edward A. Fox, Qi Fan Chen, and Lenwood S. Heath. A faster algorithm for constructing minimal perfect hash functions. SIGIR Conference, pages 266–273, 1992.
Edward A. Fox, Lenwood S. Heath, Qi Fan Chen, and Amjad M. Daoud. Practical minimal perfect hash functions for large databases. Communications of the ACM, 35(1):105–121, 1992.
Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with O(1) worst case access time. J. ACM, 31(3):538–544, 1984.
George Havas and Bohdan S. Majewski. Graph-theoretic obstacles to perfect hashing. Proceedings of the 24th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, volume 98, pages 81–93, 1993.
Kurt Mehlhorn. Data Structures and Algorithms. 1: Sorting and Searching. Springer-Verlag, 1984.
Rasmus Pagh. Faster Deterministic Dictionaries. SODA 2000, pages 487–493.
Jeanette P. Schmidt and Alan Siegel. The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput., 19(5):775–786, 1990.
Robert Endre Tarjan and Andrew Chi-Chih Yao. Storing a sparse table. Communications of the ACM, 22(11):606–611, 1979.