Bir Mükemmel Hashleme Yöntemleri Ailesi

Bohdan S. Majewski*
Nicholas C. Wormald†
George Havas‡
Zbigniew J. Czech§

Department of Computer Science and Software Engineering, University of Newcastle, Callaghan, NSW 2308, Australia, email: bohdan@cs.newcastle.edu.au
†Department of Mathematics, University of Melbourne, Parkville, Victoria 3052, Australia, email: nick@maths.mu.oz.au
‡Department of Computer Science, The University of Queensland, Queensland 4072, Australia, email: havas@cs.uq.edu.au
§Institutes of Computer Science, Silesia University of Technology and Polish Academy of Sciences, Gliwice, Poland 44–100, email: zjc@star.iinf.gliwice.edu.pl

Özet

Minimal mükemmel hash fonksiyonları, statik kümelerden öğelerin bellek açısından verimli biçimde saklanması ve hızlı biçimde geri alınması için kullanılır. Sıra koruyan minimal mükemmel hash fonksiyonları üretmek amacıyla verimli ve pratik algoritmalardan oluşan sonsuz bir aile sunuyoruz. Ailenin neredeyse tüm üyelerinin uzay ve zaman açısından optimal olan sıra koruyan minimal mükemmel hash fonksiyonları oluşturduğunu gösteriyor ve en küçük sabitlere sahip olan üyeyi belirliyoruz.

Bu ailenin üyeleri iki adımda bir hash fonksiyonu üretir. İlk olarak, r-graph içine tanımlanan özel türde bir fonksiyon olasılıksal olarak hesaplanır. Daha sonra bu fonksiyon deterministik olarak minimal mükemmel bir hash fonksiyonuna dönüştürülür. İlk adımın doğrusal rastgele zaman kullandığına dair güçlü kuramsal kanıtlar sunuyoruz. İkinci adım doğrusal deterministik zamanda çalışır. Bu aile yalnızca kuramsal açıdan önemli değildir; aynı zamanda mükemmel hash fonksiyonları üretmek için bilinen en hızlı yöntemi de sunar.

Anahtar kelimeler: Veri yapıları, olasılıksal algoritmalar, algoritma analizi, hashleme, rastgele genelleştirilmiş graflar

1 Giriş

S anahtarlarından oluşan ve n eleman içeren bir küme düşünelim; burada S, şu evrenin bir alt kümesidir

U = {0, 1, ..., u − 1}.

S içindeki anahtarların ya tamsayılar ya da karakter dizgileri olduğunu varsayıyoruz. İkinci durumda anahtarlar ya Σ anahtarların kodlandığı alfabe olmak üzere tabanı |Σ| olan sayılar olarak ele alınabilir ya da Σ üzerinde tanımlı karakter dizileri olarak değerlendirilebilir. Kolaylık sağlamak için u değerinin asal olduğunu varsayıyoruz.

Bir hash fonksiyonu şu biçimde bir fonksiyondur

h : U → M

ve anahtar kümesi S’yi verilen bir tamsayı aralığı M içine eşler; örneğin [0, m − 1], m > 0. Hash fonksiyonu, verilen bir anahtar için o öğenin saklanması veya geri alınması amacıyla bir adres (yani M’den bir tamsayı) hesaplar. Öğelerin saklandığı depolama alanı hash tablosu olarak bilinir.

Bir mükemmel hash fonksiyonu, şu biçimde bir enjeksiyondur

h : S → M,

burada S ve M yukarıda tanımlandığı gibi kümelerdir ve m ≥ n koşulu sağlanır. Eğer m = n ise, h’nin bir minimal mükemmel hash fonksiyonu olduğunu söyleriz. Eğer S kümesinden herhangi iki anahtar xi ve xj için i < j olması

h(xi) < h(xj)

sonucunu veriyorsa, bu hash fonksiyonu sıra koruyandır.

Mükemmel hashleme, bilgisayar biliminin birçok alanında kullanılan temel bir veri yapısı olan sözlük (dictionary) yapısının en iyi gerçekleştirimlerinden birini sunar. Mükemmel hashleme üzerine genel bakışlar Gonnet & Baeza-Yates (1991); Lewis & Cook (1988); Havas & Majewski (1992) tarafından verilmiştir ve bazı yeni bağımsız sonuçlar Fox, Heath, Chen & Daoud (1992); Fox, Chen & Heath (1992) tarafından sunulmuştur.

Mükemmel veya minimal mükemmel hash fonksiyonları oluşturmak için farklı zaman karmaşıklıklarına sahip çeşitli algoritmalar önerilmiştir. Bunlar dört geniş kategoriye ayrılır:

sayı kuramına dayalı yöntemler
bölütleme teknikleri
arama uzayını küçültmeye dayalı algoritmalar
seyrek matris yerleştirmesine dayalı algoritmalar

Bu kategorilerin her birindeki algoritmalar, benzer fikirleri kullanarak fakat farklı yöntemlerle yaklaşarak mükemmel hash fonksiyonlarını bulma problemine ayrı çözümler sunar.

Son yıllarda olasılıksal yöntemler alanında önemli gelişmeler yaşanmıştır. Bir dizi güçlü teknik geliştirilmiştir; genel bir bakış için Gupta, Bhaskar & Smolka (1994) incelenebilir. Number Theory’den Veri Yapıları Kuramı’na kadar uzanan alanlarda yararlılığını kanıtlamış yöntemlerden biri rastgele aramadır.

Çoğu zaman düzenli bir yapıya sahip olmayan çok geniş bir arama uzayı S içinde belirli bir P özelliğine sahip bir elemanın bulunması gereken görevlerle karşılaşırız. Eğer P özelliği kolayca doğrulanabiliyorsa ve S kümesinde P özelliğini sağlayan elemanlar bol miktarda bulunuyorsa, rastgele arama istenen elemanı bulmanın verimli ve basit bir yoludur. Bu teknik, uzaydan rastgele bir eleman seçmeye ve bu elemanın P özelliğine sahip olup olmadığını test etmeye dayanır.

S kümesinden rastgele seçilen bir x elemanının P özelliğine sahip olma olasılığını p ile gösterelim:

p = Pr(x ∈ S has P) = |P| / |S|.

X, P özelliğine sahip bir x ∈ S bulunana kadar yapılan deneme sayısını sayan bir rastgele değişken olsun. X, şu dağılıma sahip geometrik dağılıma uyar

Pr(X = i) = (1 − p)^(i−1) p.

X’in olasılık dağılım fonksiyonu F_X(i) şu şekilde tanımlanır

F_X(i) = Σ_{j=1}^{i} Pr(X = j) = 1 − (1 − p)^i.

Rastgele arama algoritmasının gerçekleştirdiği beklenen deneme sayısını ifade eden X’in beklenen değeri

E[X] = 1 / p.

Rastgele arama algoritmasının i iterasyondan fazla çalışmama olasılığı F_X(i) ile verilir.

ε için, 0 < ε < 1 olmak üzere, rastgele arama algoritmasının en az 1 − ε olasılıkla i veya daha az iterasyonda sonlanmasını sağlayan en küçük i değeri

Q_X(ε) = min_i {F_X(i) ≥ 1 − ε} = ⌈ ln ε / ln(1 − p) ⌉.

Eğer p sabit bir değer ise rastgele arama ortalama O(1) deneme gerektirir ve yüksek olasılıkla (yani bazı pozitif k için olasılığı 1 − O(n^−k)’den büyük olacak şekilde) P özelliğine sahip bir x ∈ S bulmak için en fazla O(log n) deneme gerekir. Eğer p = 1 − O(n^−δ) ve δ > 0 ise, yüksek olasılıkla yalnızca bir deneme yeterlidir.

Hash tablosunda anahtarların keyfi dağılımına izin veren minimal mükemmel hash fonksiyonları üretmek için parametreleştirilmiş bir yöntem sunuyoruz. Yöntem olasılıksaldır ve iki adımdan ilkinin tamamlanması için rastgele aramayı kullanır. Bu yöntem r-graphs olarak adlandırılan genelleştirilmiş graflar kavramını kullanır; burada bir r-graph, her kenarı V tepe kümesinin tam olarak r elemanından oluşan bir alt kümesi olan bir graftır; r ≥ 1.

Hash fonksiyonu şu biçimdedir

h(x) = g(f1(x)) ⋄ g(f2(x)) ⋄ ... ⋄ g(fr(x)),

burada ikili işlemci ⋄, M × M’den M’ye bir eşlemedir; fi fonksiyonları U’yu

V = {0, 1, ..., ν − 1}

içine eşler (ν > 0 bir tamsayıdır) ve g fonksiyonu V’yi M içine eşler.

Üretilen fonksiyon minimal olacağı için |M| (= m) değerini n olarak seçiyoruz. Basitlik için ⋄ işlemini n modunda toplama olarak seçiyoruz. Aslında M ile birlikte bir grup oluşturan herhangi bir ikili işlemci ⋄ kullanılabilir. Örneğin exclusive-or seçilebilir; bu, hız açısından avantaj sağlar ve büyük n değerleri için taşmayı önler.

Ailenin her üyesinin, r ≥ 2 ve uygun parametre seçimiyle, S için O(n) beklenen zamanda minimal mükemmel hash fonksiyonu oluşturduğunu ve O(n log n) alan gerektirdiğini gösteriyoruz. Kuramsal türetim, algoritmalarımızda kullanılan grafların tekdüzeliği hakkında makul bir varsayıma dayanır. Burada sunulan bazı sonuçların kısa duyurusu Havas, Majewski, Wormald & Czech (1994) tarafından verilmiştir.

Minimal mükemmel hash fonksiyonu üretmek için önce n anahtarı μ = n kenara ve ν tepeye sahip bir r-graph içine eşleyen özel bir fonksiyon hesaplarız; burada ν (n ve r’ye bağlıdır) daha sonra belirlenir. Özel özellik şudur: elde edilen r-graph çevrimsiz olmalıdır. Çevrimsizliği olasılıksal olarak sağlarız.

Ardından deterministik biçimde bu fonksiyonu (anahtarlardan r-graph’a olan eşlemeyi) minimal mükemmel bir hash fonksiyonuna dönüştürürüz. Hash fonksiyonunu bulmanın beklenen zamanı

O(rμ + ν).

Bu yaklaşım r > 0 olan her durum için çalışır. r > 0 için r-graph ailesi sonsuz olduğundan minimal mükemmel hash fonksiyonları üretmek için sonsuz bir algoritma ailesi elde ederiz.

Aşağıdaki atama problemini ele alalım. Verilen bir r-graph için

G = (V, E), |E| = μ, |V| = ν,

burada her e ∈ E, V’nin r elemanlı bir alt kümesidir; şu fonksiyonu bulun

g : V → {0, 1, ..., μ − 1}

öyle ki

h : E → {0, 1, ..., μ − 1}

fonksiyonu

e = {v1, v2, ..., vr}

için

h(e) = (g(v1) + g(v2) + ... + g(vr)) mod μ

şeklinde tanımlandığında bir bijeksiyon olsun.

Başka bir deyişle, tepelere değerler atayarak her kenar için o kenarın tepelerine ait değerlerin toplamının, kenar sayısına göre mod alındığında, [0, μ − 1] aralığında benzersiz bir tamsayı olmasını sağlamaya çalışıyoruz.

Çevrimsiz r-graphs algoritmamızda önemli bir rol oynar. Ancak r-graphs’ların çevrimsizliği, özellikle r ≥ 3 için, birçok farklı şekilde tanımlanabildiğinden (Duke, 1985), kavramı bizim durumumuz için geçerli açık bir tanım vererek kesinleştiriyoruz.

Bir r-graph içinde çevrim, tüm tepeleri en az 2 dereceye sahip olan bir alt graf olarak tanımlanır. Buna göre, minimum derece 2 olan bir alt graf içermeyen r-graph’ı çevrimsiz olarak adlandırırız.

r-graphs’ların çevrimsizliği için eşdeğer bir tanım aşağıdaki gibidir.

Tanım 2.1

Bir r-graph, derece 1 olan tepeleri içeren kenarların art arda silinmesiyle elde edilen işlemler dizisi sonunda kenarsız bir graf elde ediliyorsa ve ancak o zaman çevrimsizdir.

2 Aile

Majewski (1992) ve Havas & Majewski (1993) tarafından gösterildiği gibi, bir r-graph’ın çevrimsiz olması atama probleminin çözümünün varlığı için yeterli (ancak gerekli olmayan) bir koşuldur.

Ne yazık ki tanımdan doğrudan türetilen çevrimsizlik testi, r > 1 olan r-graphs için O(μ²) zaman alabilir. Optimal zamanda çalışan bir çözüm şu biçimdedir (Havas, Majewski, Wormald & Czech, 1994).

Başlangıçta r-graph’ın tüm kenarlarını silinmemiş olarak işaretleyin. Daha sonra tüm tepeleri tarayın; her tepe yalnızca bir kez incelenir. Eğer bir tepe v’nin derecesi 1 ise, v ∈ e olacak şekilde e kenarını r-graph’tan kaldırın. e kenarı kaldırıldığında e içindeki diğer herhangi bir tepenin derecesinin artık 1 olup olmadığını kontrol edin. Eğer öyleyse, bu tepelerin her biri için o tepenin ait olduğu tek kenarı kaldırın. Başka silme işlemi mümkün olmayana kadar bu işlemi özyinelemeli olarak sürdürün.

Tüm tepeler tarandıktan sonra r-graph’ın kenar içerip içermediğini kontrol edin. Eğer içeriyorsa r-graph çevrimsizlik testini geçememiştir. Eğer içermiyorsa r-graph çevrimsizdir ve kenarların kaldırıldığı sıranın tersi, aradığımız sıralamadır. İkinci adım için G’nin kenarlarını uygun sırada düzenlemek amacıyla bir yığın kullanılabilir.

Teorem 2.2

Özyinelemeli çevrimsizlik testi O(rμ + ν) zamanda çalışır.

Kanıt. G = (V, E) biçimindeki bir r-graph düşünelim. Bu graf şu iki parçalı 2-graph ile gösterilsin

H = (V1 ∪ V2, E′)

öyle ki V1 ∩ V2 = ∅, burada V1 = V ve V2 = E ve

E′ = {{v, e} : v ∈ V, e ∈ E, v ∈ e}.

Bu gösterimde r-graph G’nin hem kenarları hem de tepeleri iki parçalı graf H’nin tepeleri hâline gelir. İki parçalı graf içindeki bir kenar, v ∈ V1 ve e ∈ V2 olan iki tepeyi ancak ve ancak r-graph içindeki v tepesi e kenarına aitse birbirine bağlar.

Çevrimsizlik testi sırasında V1 içindeki her tepe, derece 1 olan tepeleri arayan döngü tarafından en az bir kez test edilir. Bir kenar e (V2 içindeki bir tepe) silindiğinde, e içindeki diğer her tepe derecesinin artık 1 olup olmadığını görmek için test edilir. Bu işlem, H grafında {e, v} kenarı boyunca ilerlemeye karşılık gelir; burada v, G içinde e’ye ait bir tepedir. Testin sonucu ne olursa olsun bu kenarı bir daha kullanmayız.

Dolayısıyla V1 içindeki tepeler üzerinde gerçekleştirilen test sayısı en fazla

Σ_{v ∈ V1} dg(v).

V2 içindeki tepelere yalnızca bir kez eriştiğimizden (silindikleri zaman) ve burada bahsedilen tüm işlemler sabit zamanda gerçekleştiğinden, tüm süreç en fazla

|V1| + |V2| + Σ_{v ∈ V1} dg(v) = ν + μ(r + 1)

adet sabit zamanlı adım alır.

Genelleştirilmiş atama problemine çözüm elde etmek için şu şekilde ilerleriz. Her kenarla

h(e) ∈ {0, 1, ..., μ − 1}

kümesinden benzersiz bir sayı ilişkilendirin. Kenarları, çevrimsizlik testinde kaldırıldıkları sıranın tersine göre ele alın ve o kenardaki henüz atanmamış tepelere değerler verin.

Bir kenar ele alındığında, o kenara özgü ve henüz değer verilmemiş bir (veya daha fazla) tepe bulunur. e kenarı için atanmamış tepeler kümesi

{v1, v2, ..., vj}

olsun.

Bu kenar için

g(v2) = ... = g(vj) = 0

olarak atayın ve

g(v1) = (h(e) − Σ_{i=2}^{r} g(vi)) mod μ

değerini belirleyin.

Doğruluğu göstermek için, g fonksiyonunun değerlerinin her tepe için tam olarak bir kez hesaplandığını ve her kenar işlendiğinde en az bir atanmamış tepe bulunduğunu göstermek yeterlidir. G çevrimsiz olduğunda ve kenarlar çevrimsizlik testinin ürettiği sıranın tersine göre işlendiğinde bu özellik sağlanır.

Tam bir algoritma iki adımdan oluşur: eşleme ve atama.

Eşleme adımında giriş kümesi şu çevrimsiz r-graph içine eşlenir

G = (V, E)

burada

V = {0, 1, ..., ν − 1}

E = {{f1(x), f2(x), ..., fr(x)} : x ∈ S},

fi : U → V.

Çevrimsiz bir eşleme rastgele arama kullanılarak bulunur. Daha sonra atama adımı yürütülür.

Minimal mükemmel hash fonksiyonu üretimi şu şekilde atama problemine indirgenir. Her kenar

e = {v1, v2, ..., vr} ∈ E

benzersiz biçimde bir anahtara x karşılık geldiğinden (fi(x) = vi, 1 ≤ i ≤ r olacak şekilde),

h(e) = i − 1

atanır; burada x, S kümesinin i’inci anahtarıdır ve böylece sıra koruma özelliği sağlanır. Daha sonra V kümesindeki her v için g fonksiyonunun değerleri atama adımıyla hesaplanır. Böylece h fonksiyonu S için sıra koruyan minimal mükemmel hash fonksiyonu olur.

Algoritmanın tanımını tamamlamak için fi eşleme fonksiyonlarını tanımlamamız gerekir.

Giriş kümesindeki anahtarların tamsayı olduğu durumla başlayalım. İdeal olarak fi fonksiyonlarının herhangi bir x ∈ S anahtarını rastgele biçimde [0, ν − 1] aralığına eşlemesi gerekir. İdeal anlamda rastgele bir fonksiyon gerçekleştiren verimli bir algoritma yoktur; ancak sınırlı rastgelelik çoğu zaman tam rastgelelik kadar etkilidir (Carter & Wegman, 1979; Schmidt & Siegel, 1990).

Uygun bir çözüm Carter & Wegman (1977) tarafından başlatılan ve universal hashing olarak adlandırılan alandan gelir. Evrensel hash fonksiyonları sınıfı H, genellikle iyi kalitede hash fonksiyonlarından oluşan ve içinden rastgele bir tanesinin kolayca seçilebildiği bir koleksiyondur.

Carter & Wegman (1979), sabit dereceli polinomların kullanılmasını önermiştir; Dietzfelbinger & Meyer auf der Heide (1990) ise gerçek rastgele fonksiyonların birçok özelliğine sahip evrensel hash fonksiyonları sınıfı önermiştir. Başka bir sınıf Siegel (1989) tarafından önerilmiştir. Son iki sınıf O(n^ε) ek alan gerektirir; burada 0 < ε < 1.

Son olarak Dietzfelbinger, Gil, Matias & Pippenger (1992), d ≥ 3 dereceli polinomların yüksek olasılıkla iyi performans gösterdiğini kanıtlamıştır. Bu sınıfın bir avantajı, her fonksiyonun yalnızca O(d log u) bit alan gerektirmesi sayesinde kompakt gösterim sağlamasıdır.

Deneylerimiz, 3 dereceli polinomların veya Dietzfelbinger & Meyer auf der Heide (1990) tarafından tanımlanan sınıfın en güvenilir seçimler olduğunu göstermektedir. Hash fonksiyonunun hızlı değerlendirilmesinin kritik olduğu uygulamalarda, beklenenden daha uzun üretim süresi riskine rağmen, 1 veya 2 dereceli polinomlar kullanılabilir.

Karakter anahtarları daha doğal biçimde karakter dizileri olarak ele alınır. Bu nedenle karakter anahtarları için özel olarak tasarlanmış bir evrensel karma fonksiyonları sınıfı olan Cν’yü tanımlarız. (Bu sınıf Fox, Heath, Chen & Daoud (1992) dâhil olmak üzere başkaları tarafından da kullanılmıştır.)

Bir anahtar x’in uzunluğunu |x| ile ve i’inci karakterini x[i] ile gösteririz. Bu sınıfın bir üyesi olan bir fonksiyon

f : Σ* → {0, 1, ..., ν − 1}

şu şekilde tanımlanır

f(x) = ( Σ_{i=1}^{|x|} T(i, x[i]) ) mod ν.

Burada T, her karakter ve bir anahtar içindeki karakterin her konumu için ν modunda rastgele tamsayılardan oluşan bir tablodur. Sınıfın bir üyesinin seçimi, eşleme tablosu T’nin (rastgele) seçilmesiyle yapılır. Bu sınıfın performansı yaklaşık 8’den fazla sembole sahip alfabeler için tatmin edicidir.

Cν sınıfı, karakter anahtarlarını sonlu bir Σ alfabesinden gelen karakter dizileri olarak en doğal biçimde ele almamıza olanak verir. Ancak herhangi bir sabit maksimum anahtar uzunluğu L için toplam anahtar sayısının

∑_{i=1}^{L} |Σ|^i ∼ |Σ|^L

anahtarı aşamayacağını hatırlamamız gerekir. Dolayısıyla ya L sabit olarak ele alınamaz ve L ≥ log_{|Σ|} n olmalıdır ya da sabit bir L için anahtar sayısı üzerinde bir üst sınır vardır. İlk durumda, kesin konuşmak gerekirse, bir anahtarı karakter karakter işlemek sabit olmayan zaman alır. Bununla birlikte pratikte, bir karakter anahtarını ikili dize olarak ele almaktansa karakter karakter yaklaşımını kullanmak çoğu zaman daha hızlı ve daha kullanışlıdır. Diğer karma şemaları (Sager, 1985; Pearson, 1990; Fox, Heath, Chen & Daoud, 1992) maksimum anahtar uzunluğunun sınırlı olduğunu varsayarak bu yaklaşımı kullanır. Bu, RAM modelinin (Aho, Hopcroft & Ullman, 1974, ss. 5–14) kötüye kullanımıdır; ancak pratik bir kötüye kullanımdır. Bunun pratikte işe yarayan bir kolaylık olduğunu akılda tutarak bu varsayımı yapıyoruz. Karakter anahtarları için tamsayı anahtar yaklaşımımız kullanılarak bu varsayımdan kaçınılabilir ve iddialarımız için teorik doğrulama sağlanabilir. Pratikte ise karakter anahtarları için özel olarak tasarlanmış şemalar daha üstün performans gösterir.

Bu bölümde algoritmamızın uygulamasının ilgi çekici iki yönünü açıklarız. Çevrimsizlik testini en uygun zamanda gerçekleştirmemizi sağlayan bir grafik gösterimini ana hatlarıyla sunarız. Ayrıca, iki tepe noktası aynı olmayacak şekilde r adet tepe noktasından oluşan rastgele bir kümenin nasıl üretileceğini de gösteririz. Önce ilkinden başlıyoruz.

Ebert (1987) tarafından önerilen kenar yönelimli grafik gösteriminin bir değişikliğini kullanıyoruz. Ebert’in grafik gösterimi yönlü grafikler içindir ve kenarların yönü önemli bir rol oynar. Bir grafikteki tüm tepe noktalarına komşu kenarların listeleri iki dizide saklanır: FIRST ve NEXT. FIRST[v] elemanı, v tepe noktasına komşu kenarların listesinin giriş noktasını tanımlar; NEXT[FIRST[v]], NEXT[NEXT[FIRST[v]]] vb. ise v’yi içeren sonraki kenarları tanımlar. Liste, 0 ile gösterilen özel bir boş kenarla sona erer. Uç noktaları v₁ ve v₂ olan herhangi bir e kenarı verildiğinde, e’yi iki listeye de kaydedebileceğimiz ancak bu listelerin birbirine bağlanmayacağı bir mekanizmaya ihtiyaç duyarız. Yön kavramını tanıtarak ve e’yi bir listede −|e|, diğerinde +|e| olarak saklayarak iki listede yinelenen kayıtlar oluşması sorununu önleriz.

r-graflar durumunda daha gelişmiş bir mekanizmaya ihtiyaç duyarız. İşaretler kullanıldığında yalnızca 2 seçenek vardır, oysa her e kenarı r (genellikle 2’den büyük) farklı listede bulunur. Bir tamsayının işaretinin bilgisayar sözcüğünde ayrılmış fazladan bir bit olduğunu gözlemleyip bu kavramı ⌈log₂(r)⌉ ek bit ayırarak genişleterek, Ebert’in 2-graflar için elde ettiği etkinin aynısını elde ederiz. Bu ek bitleri sözcüğün en az anlamlı kısmında ayırmayı tercih ederiz. Daha sonra gösterim kolaylığı için

e × 2^{⌈log₂(r)⌉} + i

ifadesini e ⊕ i ile gösteririz.

Kenarların hızlı silinmesini kolaylaştırmak için PREV adlı bir dizi daha ekleriz. Bir e kenarı için PREV[e ⊕ i] (i = 1, …, r için) e ⊕ i kenarından önce gelen kenarı saklar. Dolayısıyla eğer NEXT[e ⊕ i] = b ⊕ j ise PREV[b ⊕ j] = e ⊕ i olur. NEXT[e ⊕ i] = 0 olan e kenarları için PREV içinde e ⊕ i’ye eşit bir giriş yoktur. FIRST[v] = e ⊕ i olan tüm e kenarları için PREV[e ⊕ i] = 0 olur.

3 Uygulama

procedure insert(v1, v2, . . . , vr)
    G.µ := G.µ + 1;
    for i ∈ [1, 2, .. , r] do
        NODE[G.µ][i] := vi;
        if FIRST[vi] ≠ 0 then
            PREV[FIRST[vi]] := G.µ ⊕ i;
        end if;
        NEXT[G.µ ⊕ i] := FIRST[vi];
        PREV[G.µ ⊕ i] := 0;
        FIRST[vi] := G.µ ⊕ i;
    end for;
end insert;

procedure delete(e)
    for i ∈ [1, 2, .. , r] do
        if PREV[e ⊕ i] = 0 then {initial edge}
            FIRST[vi] := NEXT[e ⊕ i];
        else
            {not initial}
            NEXT[PREV[e ⊕ i]] := NEXT[e ⊕ i];
        end if;
        if NEXT[e ⊕ i] ≠ 0 then {not at the end}
            PREV[NEXT[e ⊕ i]] := PREV[e ⊕ i];
        end if;
    end for;
end delete;

Şekil 2: Kenar silme

Tam gösterim için ve ayrıca bir kenar verildiğinde tepe noktalarının elde edilmesini kolaylaştırmak amacıyla her e için r uç noktasını NODE[e][1], …, NODE[e][r] içinde saklarız.

Bu ortamda bir grafiğin gösterimini oluşturmak, FIRST[v ∈ V] := 0 başlatması yapılıp ardından insert yordamının µ kez çalıştırılmasıyla gerçekleştirilir. Bir v tepe noktasının derecesinin 1 olup olmadığını test etmek, şu koşulun doğrulanmasıyla yapılır:

FIRST[v] ≠ 0 ∧ NEXT[FIRST[v]] = 0.

Bir kenarın kaldırılması O(r) adet sabit zamanlı işlem gerektirir; bu durum delete yordamında (Şekil 2) gösterilmiştir. Bu ve birkaç başka basit işlem, çevrimsizlik testini O(ν + rµ) zamanda gerçekleştirmemizi sağlar.

Açıklığa kavuşturduğumuz ikinci konu, bir rastgele sayı üretecine tam olarak r çağrı yaparak [0, ν − 1] aralığında v₁, v₂, …, v_r sayılarının v_i ≠ v_j (i ≠ j için) olacak biçimde nasıl oluşturulacağıdır. Açıkça görülür ki yalnızca 0 ile ν − 1 arasında r sayı üretmek iki ya da daha fazla sayının eşit olmasına yol açabilir; bu istenmeyen bir durumdur, dolayısıyla uygun bir alternatif gerekir. r = 2 ve r = 3 için çalışan çözümler sunarız. Daha sonra belirtildiği gibi bunlar en yararlı iki durumdur ve pratik amaçların tümü için yeterlidir. Floyd tarafından geliştirilen bir algoritma (Bentley, 1987) genel r için kullanılabilir.

Aşağıda f_i(x) fonksiyonunun i = 1, 2, …, r için 0 ile ν − i arasında rastgele bir sayı döndürdüğünü varsayıyoruz. r = 2 için bir kenarın uç noktalarını üretmek amacıyla aşağıdaki yöntemi kullanırız. Bu yöntem 0 ile ν − 1 arasındaki herhangi iki farklı sayıyı eşit olasılıkla üretir.

r = 3 için aşağıdaki algoritmayı kullanırız:

v1 := f1(x);
v2 := (v1 + f2(x) + 1) mod ν;

v1 := f1(x);
v2 := v1 + f2(x) + 1;
v3 := v1 + f3(x) + 1;
if v3 ≥ v2 then
    v3 := v3 + 1;
end if;
v2 := v2 mod ν;
v3 := v3 mod ν;

İkinci tepe noktası birinci tepe noktası dışında herhangi bir yere rastgele yerleştirilir; üçüncü tepe noktası ise birinci veya ikinci tepe noktası dışında herhangi bir yere rastgele yerleştirilir. Bu çözüm, herhangi bir değer üçlüsünün seçilmesi için eşit olasılığı korur. f_i fonksiyonları sabit zamanda hesaplanabildiği sürece bir kenarın tüm tepe noktalarını üretmek için gereken süre O(r) olur.

Bu bölümde algoritmamızın beklenen zaman karmaşıklığının O(rµ + ν) olduğuna dair güçlü teorik kanıt sunuyoruz; burada µ = n’dir. r ≥ 2 için ν = O(µ) olur ve dolayısıyla yöntem O(n) zamanda sonlanır.

Algoritmanın ikinci adımı, yukarıda açıklanan atama işlemi, O(rµ + ν) zamanda çalışır. Şimdi eşleme adımının her yinelemesinin O(rµ + ν) zaman aldığını ve ν’nün, çevrimsiz bir eşleme üretme olasılığı sıfırdan farklı bir sabite yaklaşacak şekilde seçilebileceğini gösteriyoruz. Bölüm 1’de sunulan argümana göre bu durumda beklenen yineleme sayısı O(1) olur.

Eşleme adımının her yinelemesinde şu işlemler gerçekleştirilir:

Evrensel karma fonksiyonlarının bir sınıfından r adet karma fonksiyonunun seçilmesi;
Bir kümedeki her anahtar için yardımcı fonksiyon değerlerinin hesaplanması;
Üretilen G grafiğinin çevrimsiz olup olmadığının test edilmesi.

Tanımlanan sınıflardan herhangi biri için (i) işlemi en fazla O(µ + ν) zaman alır. (ii) ve (iii) işlemleri sırasıyla O(rµ) ve O(rµ + ν) zaman gerektirir. Dolayısıyla tek bir yinelemenin karmaşıklığı O(rµ + ν) olur.

Çevrimsiz bir r-graf üretme olasılığının sıfırdan farklı olması için çok seyrek graflar kullanırız. ν = cµ olacak şekilde, c > 1 için seçim yaparız. µ sonsuza giderken ilişkili olasılık p’nin sıfırdan farklı bir sabit olması için her r > 0 için c değerini tahmin eden üç sonuç sunarız. r ≥ 3 için p = 1 olur.

Teorem 4.1

ν = cµ tepe noktasına ve µ kenarına sahip rastgele bir 1-grafın çevrimsiz olma olasılığı, ancak ve ancak c = Ω(µ) olduğunda sıfırdan farklı bir sabittir.

İspat. Bu sonuç doluluk probleminin çözümünden elde edilir (Feller, 1968). Sınırlı rastgelelik durumunda bunu kanıtlamak için Fredman, Komlós & Szemerédi (1984, Corollary 2) veya Dietzfelbinger, Gil, Matias & Pippenger (1992, Fact 3.2) kullanılabilir.

1-grafların kullanımı verimli değildir. Karma fonksiyonunu oluşturmak için O(n²) alan ve zaman gerektirir. Bu durum Czech, Havas & Majewski (1992) tarafından ayrıntılı biçimde açıklanmıştır; algoritma için bir örnek ve kod da içerir.

4 Karmaşıklık Analizi

4.1 Durum 1: 1-graflar

Teorem 4.2 G, ν tepe noktası ve µ kenarı olan rastgele bir graf olsun. Eğer ν = cµ ve c > 2 ise, µ → ∞ için G’nin çevrimsiz olma olasılığı

p = e^{1/c} ((c − 2)/c)

olur (Erdős & Rényi, 1960).

Graflarımız birden fazla kenara sahip olabilir ancak döngü içermez. Bu nedenle eşleme adımında üretilen grafiğin çevrimsiz olma olasılığı, döngü bulunmaması olasılığı ile çoklu kenar bulunmaması olasılığının çarpımına eşittir. j’inci kenarın benzersiz olma olasılığı

( (ν choose 2) − j + 1 ) / (ν choose 2)

dir.

Dolayısıyla tüm µ kenarın benzersiz olma olasılığı

∏_{j=0}^{µ−1} (( (ν choose 2) − j ) / (ν choose 2))^{µ}

∼ exp(−1/c² + o(1)) olur (Palmer, 1985, s. 129).

Bu olasılıkların çarpılması teoremi kanıtlar.

Sınırlı rastgelelik durumunda, çoklu kenar bulunmama olasılığının sıfırdan farklı bir sabite yaklaştığını ve sınırsız rastgelelik durumunda elde edilen sonuçtan yalnızca çok az farklı olduğunu göstermek için Fredman, Komlós & Szemerédi (1984, Corollary 4) kullanılabilir. Daha uzun çevrimler için ise düzgünlük varsayımına güvenmek gerekir.

Dolayısıyla c = 2 + ε ise algoritma Θ(n) rastgele zamanda minimal perfect hash fonksiyonu oluşturur. c değeri 2.09 kadar küçük olduğunda bile rastgele bir grafın çevrimsiz olma olasılığı p > 1/3 olur. Buna bağlı olarak böyle bir c için eşleme adımındaki beklenen yineleme sayısı E(X) ≤ 3 olur. Algoritmanın j yinelemeden fazla çalıştırılması olasılığı F_X(j) ≤ 1 − (2/3)^j olur ve 0.999’dan büyük olasılıkla algoritma Q_X(0.001) = 18 yinelemeden fazla çalışmaz.

Pittel, Spencer & Wormald (1996) tarafından 2-graflar üzerine yapılan son teorik çalışmalar, r-grafların çevrimsiz olma eğilimi gösterdiği ν ile µ oranını belirlememizi sağlar. Aşağıdaki ifade, ν > c_r µ olduğunda rastgele bir r-grafın yüksek olasılıkla çevrimsiz olmasını sağlayan en küçük c_r değerini karakterize eder.

İddia 4.3

Rastgele bir r-grafta (r ≥ 3) minimum derecesi 2 olan bir altgrafın ortaya çıkma eşiği

c_r = r / γ

şeklindedir; burada

γ = min_{x > 0} x / (1 − e^{−x})^{r−1}.

Gerekçe. Pittel, Spencer & Wormald (1996) tarafından verilen argüman esas olarak minimum derecesi en az k olan altgraflara sahip graflar (yani 2-graflar) üzerine odaklanır. Burada, minimum derecesi en az 2 olan altgraflara sahip genel r-graflar için uygulanacak şekilde uyarlanmış kısa bir özet veriyoruz.

H rastgele seçilmiş bir r-graf olsun. V₀ = V(H) (H’nin tepe noktası kümesi) olarak tanımlayalım ve j ≥ 0 için V_{j+1}’i, H_j içinde derecesi en az 2 olan V_j tepe noktalarının kümesi olarak tanımlayalım. Burada H_j, H’nin V_j üzerine kısıtlanmış hâlidir. Başka bir deyişle, derecesi 2’den küçük olan tepe noktalarını soyarak H_{j+1} grafını H_j’den elde ederiz. Bu süreç sonunda

V_{j+1} = V_j = V_∞

olacak şekilde bazı j için durur. V_∞ ≠ ∅ ise ve ancak o zaman H’nin minimum derecesi en az 2 olan bir altgrafı vardır; çünkü V_∞, H’nin minimum derecesi en az 2 olan en büyük altgrafının tepe noktası kümesi olacaktır.

H’nin her kenarı bağımsız olarak

γ (r − 1)! / ν^{r−1}

olasılığıyla seçilerek elde edildiğini varsayalım; burada γ sabittir. Şu tanımları yapalım:

p_{i+1} = (1 − e^{−γ p_i})^{r−1}
q_{i+1} = (1 − e^{−γ p_i})^{r}

Pittel, Spencer ve Wormald’ın argümanlarına benzer şekilde, j sabitken ν → ∞ için |V_j| ∼ q_j ν neredeyse kesin olarak elde edilir. Dolayısıyla eğer lim_{j→∞} q_j = 0 ise, her ε > 0 için yeterince büyük j değerlerinde |V_j| < ε ν neredeyse kesin olarak elde edilir. Ayrı bir argüman bu durumda minimum derecesi 2 olan bir altgrafın neredeyse kesin olarak bulunmadığını gösterir. Daha yüksek kenar olasılıklarında ise lim_{j→∞} q_j ≠ 0 olur ve bu durumda minimum derecesi 2 olan bir altgrafın neredeyse kesin olarak var olduğu sonucu çıkar.

Bu iddiaların eşik için verilen değeri nasıl ortaya koyduğunu görmek için, sınır durumda p_i = p_{i+1} = p olduğunu düşünelim; burada

p = (1 − e^{−γ p})^{r−1}.

x = γp olsun. O hâlde

γ = x / (1 − e^{−x})^{r−1}.

Dolayısıyla x / (1 − e^{−x})^{r−1} ifadesinin en küçük pozitif değeri, lim_{j→∞} q_j ≠ 0 olması için gereken en küçük γ değerini verir. Bu da iddia edilen eşiği sağlar.

Kritik c_r için minimum derecesi 2 olan bir altgrafın neredeyse kesin olarak bulunmadığı sonucuna vardığımızdan, µ kenara ve en az c_r µ tepe noktasına sahip rastgele bir r-grafın yüksek olasılıkla çevrimsiz olduğu sonucunu çıkarırız. Bu sonuç, Havas, Majewski, Wormald & Czech (1994) tarafından yapılan ön analiz ve gözlemlerle iyi uyuşur. Orada anahtar sayısı arttıkça r ≥ 3 için çevrimsiz bir r-graf üretme olasılığının n’ye göre polinomsal hızda 1’e yaklaştığı gözlemlenmiştir. Bu durum r ≥ 3 durumunu r = 2 durumundan ayırır; çünkü 2-graflar için eşleme adımının çevrimsiz bir graf üretmesi olasılığı yalnızca sıfırdan farklı bir sabittir, ancak 1’den küçüktür.

r ∈ {3, 4, 5} için x(1 − e^{−x})^{1−r} grafikleri Şekil 3’te verilmiştir. Aşağıdaki fonksiyonu en aza indiren x_r* > 0 noktası için kesin formül bulunabilir:

f(x, r) = x(1 − e^{−x})^{1−r}.

f(x, r) fonksiyonunun birinci türevini hesapladığımızda

df(x, r)/dx = (1 − e^{−x})^{−r}(((1 − r)x − 1)e^{−x} + 1)

elde edilir.

İlk terim (1 − e^{−x})^{−r}, x > 0 için hiçbir zaman 0 olmadığından tamamen göz ardı edilebilir. Böylece şu denklem kalır:

e^{x} = 1 + (r − 1)x.

Bu denklemi analitik olarak çözmek için Lambert’in W fonksiyonunu kullanırız; bu fonksiyon

W(z)e^{W(z)} = z

özelliğini sağlar (Corless, Gonnet, Hare & Jeffrey, 1993). Denklemi çözdüğümüzde

x_r* = −W( −1/(r − 1) e^{−1/(r−1)} ) − 1/(r − 1)

elde edilir.

Gerçek z için −1/e ≤ z ≤ 0 aralığında (ki bu r ≥ 2 için uygundur) W(z) fonksiyonunun iki gerçek dalı vardır: W₀(z) ve W_{−1}(z). −1 ≤ W₀(z) koşulunu sağlayan ana dal için W₀(ze^{z}) = z geçerlidir. Bu dalın çözüm olarak x_r* = 0 verdiği görülür. W_{−1}(z) ≤ −1 koşulunu sağlayan diğer dal ise sıfırdan farklı alternatif bir çözüm sağlar. Önemsiz (sıfır) çözümle ilgilenmediğimiz için

x_r* = −W_{−1}( −1/(r − 1) e^{−1/(r−1)} ) − 1/(r − 1)

sonucunu elde ederiz.

Küçük r değerleri için (r = 3, 4, 5) aşağıdaki noktalar elde edilir (tüm yaklaşık değerler Maple™ V, Release 2 kullanılarak hesaplanmıştır):

γ₃ = x₃* / (1 − e^{−x₃*})² ≈ 2.45541
γ₄ = x₄* / (1 − e^{−x₄*})³ ≈ 3.08912
γ₅ = x₅* / (1 − e^{−x₅*})⁴ ≈ 3.50890

Yukarıdaki noktalar bize aşağıdaki eşik değerlerini verir:

c₃ ≈ 1.22179
c₄ ≈ 1.29487
c₅ ≈ 1.42495

Bu değerler, Havas, Majewski, Wormald & Czech (1994) tarafından rapor edilen deneysel sonuçlarla yakından örtüşmektedir; burada bulunan sabitler şunlardı:

c₃ = 1.23
c₄ = 1.29
c₅ = 1.41

2 ≤ r ≤ 22 için r-graflarının teorik eşik noktaları Şekil 4’te gösterilmektedir.

r ≥ 5 için, Corless, Gonnet, Hare & Jeffrey (1993) tarafından geliştirilen yaklaşımı kullanarak x_r* değerinin asimptotik davranışını şu şekilde karakterize edebiliriz:

x_r* = 2 ln(r)^2 − 1/(r − 1) + O(1/r²).

Tanımlanan yöntemler, daha fazla sayıda bilinmeyene sahip n adet doğrusal olarak bağımsız tamsayı kongruensinden oluşan bir sistemi çözmenin özel durumlarını temsil eder. Bu bilinmeyenler g dizisinin elemanlarıdır. Kongruens kümesini olasılıksal olarak (O(n)) zamanda oluştururuz. Kongruenslerin tutarlı olmasını ve ayrıca öyle bir sıralarının bulunmasını isteriz ki, i − 1 kongruensi bilinmeyenlere değer atayarak çözmek, i. kongruenste en az bir atanmemiş bilinmeyenin kalmasını sağlasın. Kongruensleri eşleme adımımızda bulur ve böyle bir çözüm sırasını bağımsızlık testimizde belirleriz.

En az n bilinmeyen içeren uygun bir kongruens kümesini üretmenin, muhtemelen deterministik olan başka yolları da olabileceği düşünülebilir. Böyle bir yöntemin bellek gereksinimlerinin verilen yöntemden daha küçük olması mümkün olabilir. Ancak herhangi bir alan tasarrufu yalnızca sabit bir katsayı kadar olabilir; çünkü sıralamayı koruyan minimal mükemmel hash fonksiyonları için Ω(n log n + log log u) alan gereklidir. Bu durum Fox, Chen, Daoud & Heath (1991) ile Havas & Majewski (1992) tarafından gayriresmî olarak gösterilmiştir. Ayrıca çözümün (yani g dizisi için, ortaya çıkan fonksiyonun minimal ve mükemmel olmasını sağlayan değerlerin) daha sonra doğrusal zamanda bulunup bulunamayacağı henüz görülmeyi beklemektedir.

Şekil 4: r ∈ {2, 3, …, 22} için rastgele r-graflarının eşik noktaları

6 Sonuçlar

Minimal mükemmel hash fonksiyonları üretmek için yeni bir algoritma ailesi geliştirilmiştir. Bu ailenin üyelerinin zaman karmaşıklığının O(rμ + ν) olduğu gösterilmiştir. r > 1 için bu, anahtar sayısına göre doğrusaldır ve bu da optimaldir. Oluşturulan hash fonksiyonlarının alan karmaşıklığı c n log n + O(r) log ν bittir (veya ν bir makine kelimesine sığdığı sürece c n + O(r) kelime). Bu da optimaldir. r = 3 için minimum alan gereklidir ve c ≈ 1.23’tür.

Yeterince büyük sayıda anahtar için r = 3 aynı zamanda ailenin en hızlı üyesini sağlar. Oluşturulan hash fonksiyonunun anahtarların girişte keyfi biçimde düzenlenmesine izin verdiğine dikkat edin; bu bazı uygulamalarda yararlı olabilir. Oluşturulan fonksiyon hızlı bir şekilde hesaplanabilir (en hızlı değerlendirilen fonksiyon r = 2 ile elde edilir).

Teorik değerlendirmelerde kullanılan modelin yeterli olduğu kanıtlanmış ve oldukça keskin tahminler verebilmiş bulunuyoruz. Bu teorik tahminler, Havas, Majewski, Wormald & Czech (1994) tarafından bildirilen deneysel sonuçlarla çok iyi uyum göstermektedir. Orada belirtildiği gibi, yeni algoritmanın zaman gereksinimleri çok düşüktür; hatta çok büyük veri kümeleri için bile.

Teşekkür

İlk üç yazar kısmen Australian Research Council tarafından desteklenmiştir.

Kaynaklar

Aho, A.V., Hopcroft, J.E., and Ullman, J.D. (1974) The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, Reading, Mass.

Bentley, J. (1987) Programming Pearls: A sample of brilliance. Communications of the ACM, 30(9), 754–757.

Carter, J.L., and Wegman, M.N. (1977) Universal Classes of Hash Functions. 9th Annual ACM Symposium on Theory of Computing – STOC'77, 106–112.

Carter, J.L., and Wegman, M.N. (1979) New classes and applications of hash functions. 20th Annual Symposium on Foundations of Computer Science – FOCS'79, 175–182.

Corless, R.M., Gonnet, G.H., Hare, D.E.G., and Jeffrey, D.J. (1993) On Lambert’s W Function. Research Report CS-93-03, Department of Computer Science, University of Waterloo, Canada.

Czech, Z.J., Havas, G., and Majewski, B.S. (1992) An Optimal Algorithm for Generating Minimal Perfect Hash Functions. Information Processing Letters, 43(5), 257–264.

Dietzfelbinger, M., Gil, J., Matias, Y., and Pippenger, N. (1992) Polynomial hash functions are reliable. 19th International Colloquium on Automata, Languages and Programming – ICALP'92, 235–246. Vienna, Austria.

Dietzfelbinger, M., and Meyer auf der Heide, F. (1990) A New Universal Class of Hash Functions, and Dynamic Hashing in Real Time. 17th International Colloquium on Automata, Languages and Programming – ICALP'90, 6–19. Warwick University, England.

Duke, R. (1985) Types of cycles in hypergraphs. Annals of Discrete Mathematics, 27, 399–418.

Ebert, J. (1987) A Versatile Data Structure for Edge-oriented Graph Algorithms. Communications of the ACM, 30(6), 513–519.

Erdős, P., and Rényi, A. (1960) On the Evolution of Random Graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5, 17–61.

Feller, W. (1968) An Introduction to Probability Theory and Its Applications (3rd edition). John Wiley & Sons, New York, London, Sydney.

Fox, E.A., Chen, Q.F., Daoud, A.M., and Heath, L.S. (1991) Order Preserving Minimal Perfect Hash Functions and Information Retrieval. ACM Transactions on Information Systems, 9(3), 281–308.

Fox, E.A., Chen, Q.F., and Heath, L.S. (1992) A Faster Algorithm for Constructing Minimal Perfect Hash Functions. 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval – SIGIR'92, 266–273. Copenhagen, Denmark.

Fox, E.A., Heath, L.S., Chen, Q.F., and Daoud, A.M. (1992) Practical Minimal Perfect Hash Functions for Large Databases. Communications of the ACM, 35(1), 105–121.

Fredman, M.L., Komlós, J., and Szemerédi, E. (1984) Storing a Sparse Table with O(1) Worst Case Access Time. Journal of the ACM, 31(3), 538–544.

Gonnet, G.H., and Baeza-Yates, R. (1991) Handbook of Algorithms and Data Structures. Addison-Wesley, Reading, Mass.

Gupta, R., Bhaskar, S., and Smolka, S.A. (1994) On Randomization in Sequential and Distributed Algorithms. ACM Computing Surveys, 26(1), 7–86.

Havas, G., and Majewski, B.S. (1992) Optimal Algorithms for Minimal Perfect Hashing. Research Report 234, Department of Computer Science, The University of Queensland.

Havas, G., and Majewski, B.S. (1993) Graph Theoretic Obstacles to Perfect Hashing. Congressus Numerantium, 98, 81–93.

Havas, G., Majewski, B.S., Wormald, N.C., and Czech, Z.J. (1994) Graphs, Hypergraphs and Hashing. 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'93), Lecture Notes in Computer Science 790, (Utrecht, 1993), 153–165. Springer-Verlag, Berlin.

Lewis, T.G., and Cook, C.R. (1988) Hashing for Dynamic and Static Internal Tables. Computer, 21, 45–56.

Majewski, B.S. (1992) Minimal Perfect Hash Functions. PhD thesis, Department of Computer Science, The University of Queensland.

Palmer, E.M. (1985) Graphical Evolution: An Introduction to the Theory of Random Graphs. John Wiley & Sons, New York.

Pearson, P.K. (1990) Fast Hashing of Variable-Length Text Strings. Communications of the ACM, 33(6), 677–680.

Pittel, B., Spencer, J., and Wormald, N.C. (1996) Sudden emergence of a giant k-core in a random graph. Journal of Combinatorial Theory, Series B, 67, 111–151.

Sager, T.J. (1985) A Polynomial Time Generator for Minimal Perfect Hash Functions. Communications of the ACM, 28(5), 523–532.

Schmidt, J.P., and Siegel, A. (1990) The Analysis of Closed Hashing Under Limited Randomness. 22nd Annual ACM Symposium on Theory of Computing – STOC'90, 224–234. Baltimore, MD.

Siegel, A. (1989) On Universal Classes of Fast High Performance Hash Functions, Their Time-Space Trade-off, and Their Applications. 30th Annual Symposium on Foundations of Computer Science – FOCS'89, 20–25.