Graflar, HiperGraflar ve Hashing

George Havas*
Bohdan S. Majewski†
Nicholas C. Wormald‡

Minimal mükemmel hash fonksiyonları, statik kümelerdeki öğelerin bellek açısından verimli biçimde saklanması ve hızlı biçimde geri alınması için kullanılır. Anahtarlar için keyfi bir sıralamanın belirlenmesine izin veren minimal mükemmel hash fonksiyonları üretmek amacıyla verimli ve pratik algoritmalardan oluşan sonsuz bir aile sunuyoruz. Bu ailenin neredeyse tüm üyelerinin alan ve zaman açısından optimal olduğunu gösteriyor ve en küçük sabitlere sahip olanı belirliyoruz.

Ailenin üyeleri iki adımda bir minimal mükemmel hash fonksiyonu üretir. Önce r–graf içine özel bir tür fonksiyon olasılıksal olarak hesaplanır. Daha sonra bu fonksiyon deterministik olarak rafine edilerek minimal mükemmel hash fonksiyonuna dönüştürülür. İlk adımın doğrusal rastgele zaman kullandığına dair güçlü pratik ve teorik kanıtlar sunuyoruz. İkinci adım doğrusal deterministik zamanda çalışır. Bu aile yalnızca teorik 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, hashing, genelleştirilmiş rastgele graflar

W kümesinin m anahtar içerdiğini ve W'nin bir evren olan U = {0, . . . , u−1} kümesinin altkümesi olduğunu düşünelim. Basitlik açısından W içindeki anahtarların ya tamsayı ya da karakter dizileri olduğunu varsayıyoruz. İkinci durumda anahtarlar ya |Σ| tabanında sayılar olarak ele alınabilir (burada Σ anahtarların kodlandığı alfabedir) ya da Σ üzerindeki karakter dizileri olarak değerlendirilebilir. Kolaylık açısından u'nun asal olduğunu varsayıyoruz.

Bir hash fonksiyonu h : W → I, anahtarlar kümesi W'yi verilen bir tamsayı aralığı I'ye eşleyen bir fonksiyondur; örneğin [0, k−1], burada k ≥ m. Hash fonksiyonu, verilen bir anahtar için, o öğenin saklanması veya geri alınması amacıyla bir adres (yani I içinden bir tamsayı) hesaplar. Öğeleri saklamak için kullanılan depolama alanı hash tablosu olarak adlandırılır.

Aynı adresin hesaplandığı anahtarlara eşanlamlılar (synonyms) denir. Eşanlamlıların varlığı nedeniyle iki anahtarın aynı adrese eşlendiği çakışma (collision) adı verilen bir durum ortaya çıkabilir. Çakışmaları çözmek için çeşitli yöntemler bilinmektedir. Bir mükemmel hash fonksiyonu, W ve I yukarıda tanımlandığı gibi kümeler olmak üzere h : W → I biçiminde bir injeksiyondur ve k ≥ m koşulunu sağlar. Eğer k = m ise, h'nin bir minimal mükemmel hash fonksiyonu olduğunu söyleriz.

Tanımın da ima ettiği gibi, mükemmel bir hash fonksiyonu W kümesindeki her anahtarı hash tablosunda benzersiz bir adrese dönüştürür. Çakışma meydana gelmediği için her öğe tabloda tek bir erişimle bulunabilir.

Minimal mükemmel hash fonksiyonları; programlama dillerindeki ayrılmış kelimeler, işletim sistemlerindeki komut adları, doğal dillerde sık kullanılan kelimeler vb. gibi statik bir kümeden öğelerin bellek açısından verimli biçimde saklanması ve hızlı erişimi için kullanılır. Mükemmel hashing hakkında genel bir bakış [GBY91, §3.3.16] içinde verilmiştir, alan [LC88, HM92] çalışmalarında incelenmiştir ve bazı yeni bağımsız gelişmeler [FCDH91, FHCD92] içinde yer almaktadır.

Mükemmel veya minimal mükemmel hash fonksiyonları kurmak için farklı zaman karmaşıklıklarına sahip çeşitli başka algoritmalar da sunulmuştur. Bunlar dört geniş kategoriye ayrılır:

1. Sayı kuramına dayalı yöntemler.
   Bu çözümler, sayı kuramındaki sonuçlara dayanan yöntemler kullanarak az sayıda sayısal parametrenin belirlenmesini içerir. Bunlar arasında [Spr77, Jae81, Cha84, CL86, CC88, Win90b] bulunmaktadır.

2. Segmentasyon kullanan mükemmel hash fonksiyonları.
   Anahtarlar başlangıçta sıradan bir birinci aşama hash fonksiyonu ile daha küçük kümelere dağıtılır ve kovalar (bucket) içinde tutulur. Bir kovadaki tüm anahtarlar için bir mükemmel hash fonksiyonu hesaplanır. Bu kategoriye giren algoritmalar [FKS84, SvEB84, JvEB86, SS90b, DM90, DGMP92, CHK85, DHJS83, YD85, Win90a]'dır.

3. Arama uzayını sınırlamaya dayalı algoritmalar.
   Bu yöntemler genellikle olası tüm fonksiyonlar uzayında arama yapmak ve bir mükemmel hash fonksiyonu bulmak için bir tür geri izleme (backtracking) prosedürü kullanır. Arama uzayını sınırlamak ve dolayısıyla aramayı hızlandırmak için arama başlamadan önce anahtarlara bir sıralama sezgisi uygulanır. Bu kategoriye ait çözümler arasında [Cic80, CO82, CBK85, Sag85, HK86, BT89, GS89, FHCD92, FCH92, CM92] yer alır.

4. Seyrek matris paketlemeye dayalı algoritmalar.
   Bu çözümlerin arkasındaki temel fikir, m anahtarı m × m boyutunda bir matrise düzgün biçimde eşlemektir. Daha sonra bir matris paketleme algoritması kullanılarak [Meh84, s. 108–118] bu iki boyutlu dizi doğrusal alana sıkıştırılır. Bu yaklaşım [TY79], [BT90] ve [CW91] çalışmalarında benimsenmiştir. Daha kompakt bir hash fonksiyonuna yol açan bu yaklaşımın bir değişikliği [CCJ91] içinde sunulmuştur.

Her kategorideki algoritmalar, benzer fikirleri kullanarak fakat farklı yöntemlerle yaklaşarak ayrı çözümler sunar. [FHCD92, FCH92, CHM92, HM92] çalışmalarında doğrusal alan ve zaman kullanan algoritmaların tanımlanmasıyla önemli ilerlemeler sağlanmıştır.

Genelleştirilmiş rastgele graflara dayanan ve aşağıdaki biçimde sıra koruyan minimal mükemmel hash fonksiyonları bulmaya yönelik ilişkili bir algoritma ailesi sunuyoruz:

h(e) = g(v₁) ⋄ g(v₂) ⋄ ... ⋄ g(vᵣ)

burada ⋄ ikili bir işlemdir. Basitlik açısından ⋄ işlemini m modunda toplama olarak seçiyoruz. (Alternatif olarak exclusive-or da seçilebilir; bu durum hız açısından avantaj sağlayabilir ve büyük m değerleri için taşmayı önler.)

Ailenin her üyesinin, parametrelerin uygun seçimiyle, W için bir minimal mükemmel hash fonksiyonunu O(m) beklenen zamanda kurduğunu ve O(m log m) alan gerektirdiğini gösteriyoruz. Kuramsal türetme, algoritmalarımızda kullanılan grafların düzgünlüğü hakkında makul bir varsayıma dayanır. Bu algoritmalar hem verimli hem de pratiktir.

Bu makale boyunca log(n) ifadesi log₂(n) anlamına gelir, ln(n) ifadesi logₑ(n) anlamına gelir ve yᵢ, y'nin düşen faktöriyelini gösterir:

yᵢ = y(y − 1) ... (y − i + 1).

r–graf olarak adlandırılan genelleştirilmiş bir graf, her kenarın V kümesinin tam olarak r eleman içeren bir altkümesi olduğu bir graftır; burada r ≥ 1.

2. Graflar ve Hashing

Grafları (örtük biçimde) kullanan ilk yöntem Fredman, Komlós ve Szemerédi tarafından yayımlanmıştır [FKS84]. Yazarlar algoritmalarını graf kuramı terimleriyle ifade etmemiş olsalar da bunu yapmak kolaydır.

Buna göre ilk adımlarını m anahtarın m birincil düğüme eşlenmesi olarak düşünebiliriz. Aynı birincil düğüme eşlenmiş anahtar gruplarının her biri için ikinci bir eşleme yapılır ve gruptaki her anahtar benzersiz bir düğüme gönderilir. Sonuç, yıldız biçimli ağaçların birleşiminden oluşan bir graftır.

Fredman, Komlós ve Szemerédi ortaya çıkan grafı verimli biçimde kodlayan bir yapı sunar ve düğüm sayısının — ki bu yapı boyutunu belirler — 11m'i aşmadığını gösterir. m adet birincil düğümün ikinci eşleme için parametreleri de saklaması gerektiğinden yapının toplam boyutu 13m olur. (Fredman, Komlós ve Szemerédi kodlamanın boyutunu bir miktar azaltmaya izin veren karmaşık bir iyileştirmeden de bahseder.)

Bu şemada meydana getirilen graf yıldızların birleşimidir. Bu tür graflar çok yaygın değildir; bu nedenle düğüm sayısının kenar sayısından (anahtarlara karşılık gelen) çok daha büyük olması gerekir. Bu durum yöntemin pratikliğini azaltır ve istenenden fazla alan gerektirir.

Bizim tekniklerimiz anahtarların herhangi bir çevrimsiz grafa eşlenmesine dayanır. Bu yaklaşım iki avantaj sağlar: çok daha küçük sabitler ve hash tablosunda anahtarların keyfi düzenlenmesine izin veren mükemmel hash fonksiyonları üretme yeteneği. Başlıca veri yapılarımız için alan gereksinimi 1.23m kadar düşük olabilir.

3. Aile

Bir kenar için

e = {v₁, v₂, . . . , vᵣ} ∈ E

şunu tanımlarız

h(e) = ( g(v₁) + g(v₂) + ... + g(vᵣ) ) mod m.

Key Centre for Software Technology, Department of Computer Science, University of Queensland, Queensland 4072, Australia. Email: havas@cs.uq.oz.au
†Key Centre for Software Technology, Department of Computer Science, University of Queensland, Queensland 4072, Australia. Email: bohdan@cs.uq.oz.au
‡Department of Mathematics, University of Melbourne, Parkville, Victoria 3052, Australia. Email: nick@maths.mu.oz.au
§Institutes of Computer Science, Silesia University of Technology and Polish Academy of Sciences, 44–100 Gliwice, Poland. Email: zjc@gleto2.gliwice.edu.pl

Bir minimal mükemmel hash fonksiyonu üretmek için önce m anahtardan m kenar ve n düğüm içeren bir r-grafa özel bir tür fonksiyon hesaplarız; burada n, m ve r'ye bağlı olarak Bölüm 5'te belirlenir. Bu fonksiyonun özel özelliği, ortaya çıkan r-grafın kenarlarının bağımsız olması gerekliliğidir; bu kavramı daha sonra tanımlayacağız. Kenar bağımsızlığını olasılıksal olarak sağlarız. Daha sonra bu fonksiyonu (anahtarlardan bir r-grafa olan fonksiyonu) deterministik biçimde rafine ederek minimal mükemmel hash fonksiyonuna dönüştürürüz. Hash fonksiyonunu bulmak için beklenen süre O(rm + n)'dir.

Bu tür bir yaklaşım herhangi bir r > 0 için uygundur. r > 0 için r-graflar ailesi sonsuz olduğundan, minimal mükemmel hash fonksiyonları üretmek için sonsuz sayıda algoritmadan oluşan bir aile elde ederiz.

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

G = (V, E), |E| = m, |V| = n,

burada her e ∈ E, V'nin r elemanlı bir altkümesidir; şu fonksiyonu bulun:

g : V → [0, m − 1]

öyle ki

h : E → [0, m − 1]

fonksiyonu (düğüm değerlerinin m modunda toplamı olarak tanımlanan) bir bijeksiyon olsun.

Başka bir deyişle, düğümlere değerler atayarak her kenar için düğümlerine ait değerlerin toplamının, kenar sayısına göre mod alındığında, [0, m − 1] aralığında benzersiz bir tamsayı olmasını sağlamak istiyoruz.

Eğer keyfi graflar dikkate alınırsa bu problemin her zaman bir çözümü yoktur. Ancak graf G bir kenar bağımsızlığı ölçütünü sağlıyorsa, her düğüm için değer bulmak amacıyla basit bir prosedür kullanılabilir.

Kenar bağımsızlığı ölçütünü şu şekilde tanımlarız.

Tanım. Bir r-graf G = (V, E) içindeki kenarlar bağımsızdır ancak ve ancak derece 1 olan düğümleri içeren kenarların tekrarlı biçimde silinmesi sonucunda kenar içermeyen bir graf elde ediliyorsa.

Bu tanımın, r-grafın minimum derecesi 2 olan bir altgraf içermemesi koşuluna eşdeğer olduğunu gözlemleyin. [Duk85, s. 407]'de tartışılan bu tür altgraflar, 2-graflardaki çevrimlerin doğal bir genellemesidir.

Atama problemini çözmek için şu şekilde ilerleriz. Her kenara herhangi bir sırada h(e) ∈ [0, m − 1] aralığında benzersiz bir sayı atayın. Kenarları, bağımsızlık testindeki silme sırasının tersine olacak biçimde ele alın ve o kenardaki henüz değer atanmamış her düğüme değer verin.

Tanımın da ima ettiği gibi, her kenarın (ele alındığı anda) kendisine özgü ve henüz değer atanmamış bir veya daha fazla düğümü olacaktır. Kenar e için atanmamış düğümler kümesi şu olsun:

{v1, v2, ..., vj}

Kenar e için şu atamayı yapın:

• g(v1) = 0
• g(v2) = 0
• ...
• g(vj−1) = 0

ve

g(vj) = ( h(e) − Σ_{v ∈ e, v ≠ vj} g(v) ) mod m

olarak belirleyin.

Yöntemin doğruluğunu göstermek için, g fonksiyonunun değerinin her düğüm için tam olarak bir kez hesaplandığını ve her kenar için ele alındığı anda en az bir atanmamış düğüm bulunduğunu göstermek yeterlidir. Bu özellik, G grafının kenarları bağımsız olduğunda ve kenarlar bağımsızlık testinin belirlediği sıranın tersinde işlendiğinde açıkça sağlanır.

Ne yazık ki tanımdan doğrudan elde edilen bağımsızlık testi yeterince hızlı değildir. r > 1 olan r-graflar için O(m²) zaman gerektiren örnekler bulmak kolaydır. Bu nedenle r > 0 için herhangi bir r-grafın kenarlarını test etmek ve düzenlemek amacıyla daha iyi bir yöntem bulmamız gerekir.

Bir çözüm aşağıdaki biçimdedir.

Başlangıçta r-grafın tüm kenarlarını kaldırılmamış olarak işaretleyin. Ardından tüm düğümleri tarayın; her düğüm yalnızca bir kez taranır. Eğer bir düğüm v derece 1'e sahipse (yani yalnızca bir kenara aitse) v'yi içeren kenar e'yi r-graftan kaldırın.

Kenar e kaldırılır kaldırılmaz, diğer düğümlerinden herhangi birinin derecesinin artık 1 olup olmadığını kontrol edin. Eğer öyleyse, bu tür her düğüm için o düğümün ait olduğu tek kenarı kaldırın. Daha fazla silme mümkün olmayana kadar bunu özyineli olarak tekrarlayın.

Tüm düğümler tarandıktan sonra r-grafın kenar içerip içermediğini kontrol edin. Eğer içeriyorsa r-graf bağımsızlık testinde başarısız olmuştur. Eğer içermiyorsa kenarlar bağımsızdır ve kaldırılma sırasının tersine olan sıra aradığımız sıradır.

Bu yöntem çalıştırma süresi O(rm + n) olacak şekilde uygulanabilir. G grafının kenarlarını uygun sırada düzenlemek için bir yığın (stack) kullanılabilir.

Bu atama probleminin çözümü, minimal mükemmel hash fonksiyonları üretmeye yönelik algoritmalarımızın ikinci bölümünü oluşturur.

Minimal Mükemmel Hash Fonksiyonu Üretimi

Artık minimal mükemmel hash fonksiyonu üretmek için bir algoritma sunmaya hazırız. Algoritma iki adımdan oluşur: eşleme (mapping) ve atama (assignment).

Eşleme adımında giriş kümesi bir r-grafa eşlenir:

G = (V, E)

burada

• V = {0, ..., n − 1}
• E = { {f1(w), f2(w), ..., fr(w)} : w ∈ W }
• fi : U → {0, ..., n − 1}

Graf G kenar bağımsızlığı testini geçene kadar bu adım tekrarlanır. Bu sağlandıktan sonra atama adımı yürütülür.

Minimal mükemmel hash fonksiyonu üretme işlemi şu şekilde atama problemine indirgenir.

Her kenar

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

benzersiz biçimde bir anahtara w karşılık gelir ve

fi(w) = vi, 1 ≤ i ≤ r

olur. Bu nedenle istenen fonksiyonu bulmak oldukça basittir. Şu şekilde belirleriz:

h(e = {f1(w), f2(w), ..., fr(w)}) = i − 1

eğer w, W kümesinin i-inci kelimesiyse; böylece sıra koruma özelliği elde edilir.

Daha sonra V içindeki her v için g fonksiyonunun değerleri atama adımıyla (yani G için atama problemini çözen adımda) hesaplanır. Böylece h fonksiyonu W için sıra koruyan minimal mükemmel hash fonksiyonu olur.

Eşleme Fonksiyonları

Algoritmanın tanımını tamamlamak için fi eşleme fonksiyonlarını tanımlamamız gerekir. İdeal olarak fi fonksiyonları herhangi bir w ∈ W anahtarını [0, n − 1] aralığına rastgele eşlemelidir.

Tam rastgelelik verimli biçimde hesaplanabilir değildir. Ancak sınırlı rastgelelik çoğu zaman tam rastgelelik kadar iyidir [CW79a, CW79b, KU86, SS89, SS90a]. Uygun bir çözüm Carter ve Wegman tarafından başlatılan ve evrensel hashing (universal hashing) olarak adlandırılan alandan gelir.

Evrensel hash fonksiyonları sınıfı H, genel olarak iyi hash fonksiyonlarından oluşan ve içinden kolayca rastgele bir tanesinin seçilebildiği bir koleksiyondur.

Bir sınıf, herhangi bir üyesi k veya daha az anahtarı birbirinden bağımsız ve rastgele eşliyorsa k-evrensel olarak adlandırılır.

Carter ve Wegman [CW79a], hash fonksiyonları olarak polinomların kullanılmasını önermiştir. Derecesi d olan polinomların (d + 1)-evrensel hash fonksiyonları sınıfı oluşturduğunu göstermişlerdir.

Dietzfelbinger ve Mayer auf der Heide başka bir evrensel hash fonksiyonları sınıfı önermiştir [DM90]. Sabit derece d'li polinomlara ve boyutu m^δ olan rastgele sayı tablolarına dayanan bu sınıf (0 < δ < 1), (d + 1)-evrenseldir ancak gerçekten rastgele fonksiyonların birçok özelliğini paylaşır.

Siegel [Sie89] tarafından başka bir sınıf önerilmiştir, ancak bu sınıf oldukça fazla alan gerektirir.

Son olarak 1992 yılında Dietzfelbinger, Gil, Matias ve Pippenger [DGMP92], derecesi d ≥ 3 olan polinomların güvenilir olduğunu, yani yüksek olasılıkla iyi performans gösterdiklerini kanıtlamıştır. Bu sınıfın bir avantajı, fonksiyonların kompakt bir şekilde temsil edilmesidir; çünkü her biri yalnızca O(d log u) bitlik alan gerektirir.

Yukarıdaki sınıfların herhangi biri amaçlarımız için kullanılabilir. Deneysel sonuçlar, derecesi 3 olan polinomların veya Dietzfelbinger ve Mayer auf der Heide [DM90] tarafından tanımlanan sınıfın en iyi seçenekler olduğunu göstermektedir.

Karakter Anahtarlarının Hashlenmesi

Yukarıda önerilen sınıflar tamsayı anahtarları için oldukça iyi performans gösterir. Ancak karakter anahtarları doğası gereği karakter dizileri olarak ele alınmaya daha uygundur. Bu nedenle karakter anahtarları için özel olarak tasarlanmış bir evrensel hash fonksiyonları sınıfı olan Cₙ sınıfını tanımlıyoruz.

Bu sınıf Fox, Heath, Chen ve Daoud [FHCD92] dahil olmak üzere başkaları tarafından da kullanılmıştır.

Şöyle tanımlayalım:

• |w| anahtar w'nin uzunluğunu göstersin
• w[i] anahtarın i'inci karakterini göstersin

Bu sınıfın bir elemanı şu biçimde bir fonksiyondur:

fi : Σ* → {0, ..., n − 1}

ve şu şekilde tanımlanır:

fi(w) = ( Σ_{j=1}^{|w|} Ti(j, w[j]) ) mod n

Burada Ti, bir kelimedeki her karakter ve her konum için mod n altında rastgele tamsayılardan oluşan bir tablodur.

Sınıfın bir elemanını seçmek, eşleme tablosu Ti'yi rastgele seçmekle gerçekleştirilir.

Yukarıda tanımlanan sınıf, karakter anahtarlarını sonlu bir alfabe Σ'dan gelen karakter dizileri olarak en doğal biçimde ele almamıza olanak tanır.

Ancak bu yaklaşımın hoş olmayan bir kuramsal sonucu vardır. Sabit bir maksimum anahtar uzunluğu L için, toplam anahtar sayısı şu değeri aşamaz:

Σ_{i=1}^{L} |Σ|^i = |Σ|(|Σ|^L − 1) / (|Σ| − 1) ≈ |Σ|^L

Dolayısıyla şu iki durumdan biri geçerlidir:

• L sabit olarak ele alınamaz, ve L ≥ log_|Σ| m = Ω(log m), veya
• sabit bir L için anahtar sayısı üzerinde bir üst sınır vardır.

İlk durumda, teknik olarak konuşmak gerekirse, bir anahtarı karakter karakter işlemek sabit zamanlı değildir. Buna rağmen pratikte, bir karakter anahtarını ikili bir dize olarak ele almaktansa karakter karakter yaklaşımını kullanmak çoğu zaman daha hızlı ve daha kullanışlıdır.

Diğer hashleme şemaları da bu yaklaşımı kullanır ve maksimum anahtar uzunluğunun sınırlı olduğunu varsayar (örneğin [Sag85, HK86, Pea90, FHCD92]). Bu durum teknik olarak RAM modelinin [AHU74, ss. 5–14] kötüye kullanımıdır, ancak tamamen pratik bir yaklaşımdır.

Uniform maliyet ölçüsüne sahip RAM modelinde, sayısal bir anahtar üzerindeki her işlemin sabit zaman aldığı varsayılır; bu da bir karakter anahtarını karakter karakter sabit zamanda işleyebilmeye karşılık gelir.

Biz de bu varsayımı yapıyoruz ve bunun pratikte işe yarayan bir kolaylık olduğunu akılda tutuyoruz. Bu varsayımdan kaçınmak, bu bölümde karakter anahtarları için daha önce önerilen yaklaşım kullanılarak mümkündür. Bu yaklaşım, yaptığımız iddialar için kuramsal bir doğrulama sağlar; ancak pratikte karakter anahtarları için özel olarak tasarlanan şemalar daha üstün performans gösterir.

4. Keyfi Anahtar Düzenlemelerinin Bazı Avantajları

Geleneksel hash fonksiyonlarının aksine, yöntemimiz anahtarların hash tablosunda istenilen herhangi bir sırada düzenlenmesine olanak tanır.

Ayrıca, mükemmel atama problemini şu şekilde değiştirebiliriz: kardinal sayılara giden herhangi bir önceden tanımlı h fonksiyonu için (bir birebir eşleme olması gerekmez) doğrusal zamanda uygun bir g fonksiyonu bulabiliriz.

Bu fikir, tamsayılara, rasyonel sayılara veya karakter dizilerine giden fonksiyonlara kolayca genişletilebilir. Dolayısıyla çeşitli türlerde ayrık fonksiyonların değerlendirilmesi için etkili bir yöntem sağlayabilir.

Bir örnek karakter anahtarları için bir sözlük yapısıdır.

Standart bir uygulamada hash değeri, hashlenmiş dizelerin başlangıcını gösteren işaretçilere sahip bir dizideki bir indekstir. Bu da, hash fonksiyonu için gereken alana ek olarak m adet işaretçiye ihtiyaç duyduğumuz anlamına gelir.

Keyfi sıralamaya izin veren mükemmel bir hash fonksiyonu ile her değerin doğrudan ilgili dizenin başlangıcını göstermesini sağlayabilir ve böylece işaretçiler için gereken alanı ortadan kaldırabiliriz.

Başka bir örnek, anahtarların ayrık sınıflar oluşturduğu durumlarda ortaya çıkar. Her anahtar ile birlikte ait olduğu sınıfın adını saklamak yerine, belirli bir sınıfa ait tüm anahtarlara aynı hash değerini atarız.

Hashleme şemamız ayrıca veri elemanlarından doğrudan hesaplanamayan bir tam sıralamanın uygulanmasını da kolaylaştırır.

Bunlar, keyfi hash değeri seçimine izin veren hashleme yaklaşımının faydalı olabileceği birkaç örnektir.

5. Karmaşıklık Analizi

Bu bölümde algoritmanın beklenen zaman karmaşıklığının O(rm + n) olduğuna dair güçlü kuramsal kanıtlar sunuyoruz. r > 1 için n, O(m) mertebesindedir ve uygun şekilde seçilen n ile yöntem O(m) zamanda çalışır.

Algoritmanın ikinci adımı olan ve yukarıda açıklanan atama işlemi O(rm + n) zamanda çalışır.

Şimdi eşleme adımının her yinelemesinin O(rm + n) zaman aldığını ve n'i uygun biçimde seçerek beklenen yineleme sayısının m arttıkça bir sabitle sınırlı kalmasını sağlayabileceğimizi gösteriyoruz.

Bunun için grafiklerimizdeki kenarların birbirinden bağımsız olarak rastgele ortaya çıktığını varsayıyoruz. Buna uniformluk varsayımı diyoruz; çünkü bu varsayım tüm grafiklerin oluşma olasılığının eşit olduğu anlamına gelir.

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

1. Evrensel hash fonksiyonları sınıfından r adet hash fonksiyonunun seçilmesi.
2. Kümedeki her kelime için yardımcı fonksiyon değerlerinin hesaplanması.
3. Üretilen grafik G'nin kenarlarının bağımsız olup olmadığının test edilmesi.

İşlem (i) en fazla O(m + n) zaman alır. Cₙ sınıfı için zaman, maksimum kelime uzunluğu ile alfabe büyüklüğünün çarpımı ve r ile orantılıdır; sabit bir alfabe için bu O(r) olarak kabul edilebilir.

İşlemler (ii) ve (iii) sırasıyla O(rm) ve O(rm + n) zaman gerektirir. Dolayısıyla tek bir yinelemenin karmaşıklığı O(rm + n) olur.

p, eşleme adımının m bağımsız kenarlı ve n düğümlü bir r-graf üretme olasılığı olsun. Bu durumda beklenen yineleme sayısı:

1 / p

Bağımsız kenarlara sahip bir r-graf üretme olasılığını yüksek tutmak için çok seyrek grafikler kullanırız ve

n = c m

şeklinde seçim yaparız; burada c sabit bir değerdir.

5.1 Durum 1: 1-graflar

Teorem 2. n = cm düğümlü ve m kenarlı rastgele bir 1-grafın bağımsız kenarlara sahip olma olasılığı ancak ve ancak

c = Ω(m)

olduğunda sıfırdan farklı bir sabittir.

İspat. Sonuç doluluk probleminin çözümünden elde edilir (bkz. [Fel68]). Sınırlı rastgelelik durumunda sonucu kanıtlamak için [FKS84, Corollary 2] veya [DGMP92, Fact 3.2] kullanılabilir.

1-graflar için çözüm kabul edilebilir değildir; bunun başlıca nedeni alan gereksinimleridir. Ayrıca hash fonksiyonunu kurmak için O(m²) zaman gerektirir.

5.3 Durum 3: r > 2 için r-graflar

Teorem 3. G, tekrarlarla birlikte m rastgele kenar seçilerek elde edilen, n düğümlü ve m kenarlı rastgele bir grafik olsun. Eğer n = cm ve c > 2 ise, G'nin bağımsız kenarlara sahip olma olasılığı m → ∞ iken bir sabite yaklaşır.

İspat. 2-graflar için kenar bağımsızlığı koşulu döngüsüzlük ile eşdeğerdir. Erdős ve Rényi'nin iyi bilinen sonucuna göre [ER60], rastgele bir grafiğin döngü içermeme olasılığı düğüm sayısı arttıkça bir sabite yaklaşır.

Grafiklerimiz çoklu kenarlar içerebilir ancak döngü (loop) içermez. Eşleme adımında oluşturulan grafiğin döngüsüz olma olasılığı, çoklu kenar bulunmama olasılığı ile çoklu kenar olmadığı koşulu altında döngü bulunmama olasılığının çarpımına eşittir.

Tüm m kenarının benzersiz olma olasılığı yaklaşık olarak

exp(−1/c² + o(1))

şeklindedir.

Olasılıkların çarpılması sonucu verir.

Sınırlı rastgelelik durumunda, çoklu kenar bulunmama olasılığının sıfırdan farklı bir sabite yaklaştığını göstermek için [FKS84, Corollary 4] kullanılabilir ve sonuç sınırsız rastgelelik durumundan yalnızca küçük bir fark gösterir. Daha uzun döngüler için uniformluk varsayımına dayanmak gerekir.

Yukarıdaki teoremin bir sonucu olarak, eğer (c = 2 + \epsilon) ise algoritma minimal mükemmel hash fonksiyonunu rastgele (\Theta(m)) zamanda oluşturur. 2-graflar için döngü tespitini hızlandırabiliriz. Bunun bir yöntemi küme birleşimi (set union) algoritması kullanmaktır [TVL84].

Kenar bağımsızlığı, r–grafın minimum derecesi en az 2 olan bir altgraf içermemesi koşuluna eşdeğerdir. (r > 2) için analiz, (r \le 2) durumuna göre çok daha karmaşıktır. Burada yalnızca şu sonucu gösteriyoruz: yalnızca (r)'ye bağlı bir sabit olan (c_{inv}) vardır ve eğer (m \le c_{inv} n) ise, minimum derecesi en az 2 olan ve (i) kenarlı kenar-minimal altgrafların beklenen sayısı (E(Y_i)), (m) sonsuza giderken tüm (i \le m) için 0'a yaklaşır. Olası en küçük (c \le 1/c_{inv}) değeri deneysel olarak belirlenir.

Teorem 4

Herhangi bir r–graf için yalnızca (r)'ye bağlı bir sabit (c_{inv}) vardır; eğer (m \le c_{inv} n) ise rastgele bir r–grafın bağımsız kenarlara sahip olma olasılığı 1'e yaklaşır.

İspatın ana hatları. Burada da uniformluk varsayımı kullanılır. Yukarıdaki teoremi kanıtlamak için n düğümlü ve m kenarlı rastgele bir r–grafta minimum derecesi en az 2 olan altgrafların sayısını tahmin etmemiz gerekir. Bu sayının şu şekilde gösterilebileceği ortaya konabilir.

Kenar-minimal altgraflarda herhangi bir kenarın kaldırılması altgraf içindeki en az bir düğümün derecesini 1'e düşürmelidir; buradan i kenarlı böyle bir altgrafın en az i/2 düğüme sahip olması gerektiğini çıkarırız. Farklı yaklaşım tekniklerinden yararlanarak her bir r için yalnızca r'ye bağlı bir sabit (c_{inv}) bulunduğunu ve eğer (m \le c_{inv} n) ise kenar-minimal altgrafların beklenen sayısının 0'a yaklaştığını gösterebiliriz.

6. Deneysel Sonuçlar

Belirli bir iyileştirme yapılmadan, (r \in {2, 3, 4, 5}) için dört algoritma C dilinde gerçekleştirildi. Tüm deneyler SunOS™ işletim sistemi altında çalışan bir Sun SPARC station 2 üzerinde yürütüldü.

(r \in {2, 3}) ve karakter anahtarları için sonuçlar Tablo 1'de özetlenmiştir. reps, mapping, assgn ve total değerleri sırasıyla eşleme adımındaki ortalama yineleme sayısını, eşleme adımı süresini, atama adımı süresini ve algoritmanın toplam süresini gösterir. Tüm süreler saniye cinsindendir.

Tablo 1: Deneysel Sonuçlar

r = 2, c = 2.1 | r = 3, c = 1.23

Tamsayı anahtarları ve (r = 3) için sonuçlar Tablo 2'de verilmiştir. Eşleme fonksiyonları (f_i), (1 \le i \le 3), (H_n^3) sınıfından seçilmiştir ve anahtarlar şu evrenden alınmıştır:

(U = {0, \ldots, 2^{31} - 2}.)

Tablodaki her satır 200 deneyin ortalamasını temsil eder. Derecesi 3 olan üç polinomu hesaplamanın, (C_n) sınıfından üç fonksiyon değerlendirmeye göre yaklaşık iki kat daha fazla zaman aldığını gözlemleyin. Benzer şekilde, karakter anahtarlarında olduğu gibi, (m > 64000) için yineleme sayısı 1'de sabitlenmiştir. Dolayısıyla yeterince büyük (m) değerleri için ortalama davranış aynı zamanda en kötü durum davranışını da temsil eder.

(r \in {3, 4, 5}) için deneysel olarak (c_r) sabitleri belirlenmiştir; eğer (n = c_r m) ise eşleme adımındaki beklenen yineleme sayısı m'in azalmayan bir fonksiyonu olur. Bu değerler şunlardır:

• (c_3 = 1.23)
• (c_4 = 1.29)
• (c_5 = 1.41)

Bu sabitler için ve m arttıkça, eşleme adımındaki gözlenen ortalama yineleme sayısı 1'e yaklaşmıştır. Dolayısıyla anahtar sayısı arttıkça (r = 3), (r = 2)'ye göre daha iyi performans gösterir; çünkü (r = 3) için eşleme adımındaki beklenen yineleme sayısı azalırken, (r = 2) için bu sayı sabit kalır.

Deneysel sonuçlar kuramsal değerlendirmeleri tamamen desteklemektedir. Ayrıca yeni algoritmanın zaman gereksinimleri oldukça düşüktür. Aynı şekilde eşleme, atama ve toplam süreler m ile yaklaşık doğrusal biçimde artmaktadır.

Tablo 2: Tamsayı Anahtarları için Deneysel Sonuçlar

Sunulan yöntem, daha fazla sayıda bilinmeyen içeren m adet doğrusal bağımsız tamsayı kongruensinden oluşan bir kümenin çözümünün özel bir durumudur. Bu bilinmeyenler, g dizisinin elemanlarıdır. Kongruens kümesini olasılıksal olarak O(m) zamanda oluştururuz. Kongruenslerin tutarlı olmasını ve öyle bir sıralama bulunmasını isteriz ki, ilk i−1 kongruensin çözülmesi sırasında bilinmeyenlere değer atanırken i'inci kongruenste en az bir bilinmeyen henüz atanmış olmasın.

Kongruensleri eşleme adımında belirler ve böyle bir çözüm sırasını bağımsızlık testinde buluruz. En az m bilinmeyen içeren uygun bir kongruens kümesi üretmenin başka yolları da bulunabilir; bunlar muhtemelen deterministik olabilir. Böyle bir yöntemin bellek gereksinimlerinin verilen yönteme göre daha küçük olması da mümkündür. Ancak herhangi bir alan tasarrufu yalnızca sabit bir çarpan düzeyinde olabilir; çünkü sıralamayı koruyan minimal mükemmel hash fonksiyonları için O(m log m) alan gereklidir (bkz. [HM92]). Ayrıca elde edilen fonksiyonun minimal ve mükemmel olması için gerekli olan (g dizisi için uygun değerlerin bulunması) çözümün doğrusal zamanda elde edilip edilemeyeceği henüz belirsizdir.

Teşekkür

Birinci ve üçüncü yazarlar kısmen Australian Research Council tarafından desteklenmiştir.

Kaynaklar

[AHU74] A.V. Aho, J.E. Hopcroft ve J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Co., Reading, Mass., 1974.

[BT89] M.D. Brain ve A.L. Tharp. Büyük kelime kümeleri için neredeyse mükemmel hashleme. Software—Practice and Experience, 19:967–978, 1989.

[BT90] M.D. Brain ve A.L. Tharp. Seyrek matris paketleme kullanarak mükemmel hashleme. Information Systems, 15(3):281–290, 1990.

[CBK85] N. Cercone, J. Boates ve M. Krause. Mükemmel hash fonksiyonlarını bulmak için etkileşimli bir sistem. IEEE Software, 2(6):38–53, 1985.

[CC88] C.C. Chang ve C.H. Chang. Tek parametreli sıralı minimal mükemmel karma şeması. Information Processing Letters, 27(2):79–83, Şubat 1988.

[CCJ91] C.C. Chang, C.Y. Chen ve J.K. Jan. Makineden bağımsız mükemmel karma tasarımı üzerine. The Computer Journal, 34(5):469–474, 1991.

[Cha84] C.C. Chang. Sıralı minimal mükemmel karma şemasının incelenmesi. Communications of the ACM, 27(4):384–387, Nisan 1984.

[CHK85] G.V. Cormack, R.N.S. Horspool ve M. Kaiserwerth. Pratik mükemmel karma. The Computer Journal, 28(1):54–55, Şubat 1985.

[CHM92] Z.J. Czech, G. Havas ve B.S. Majewski. Minimal mükemmel karma fonksiyonları üretmek için en uygun algoritma. Information Processing Letters, 43(5):257–264, Ekim 1992.

[Cic80] R.J. Cichelli. Minimal mükemmel karma fonksiyonlarının basit biçimde oluşturulması. Communications of the ACM, 23(1):17–19, Ocak 1980.

[CL86] C.C. Chang ve R.C.T. Lee. Harf yönelimli minimal mükemmel karma şeması. The Computer Journal, 29(3):277–281, Haziran 1986.

[CM92] Z.J. Czech ve B.S. Majewski. (O(m^2)) zamanda minimal mükemmel bir karma fonksiyonunun üretilmesi. Archiwum Informatyki, 4:3–20, 1992.

[CO82] C.R. Cook ve R.R. Oldehoeft. Harf yönelimli minimal mükemmel karma fonksiyonu. SIGPLAN Notices, 17(9):18–27, Eylül 1982.

[CW77] J.L. Carter ve M.N. Wegman. Evrensel karma fonksiyonu sınıfları. 9th Annual ACM Symposium on Theory of Computing (STOC’77) içinde, sayfa 106–112, 1977.

[CW79a] J.L. Carter ve M.N. Wegman. Karma fonksiyonlarının yeni sınıfları ve uygulamaları. 20th Annual Symposium on Foundations of Computer Science (FOCS’79) içinde, sayfa 175–182, 1979.

[CW79b] J.L. Carter ve M.N. Wegman. Evrensel karma fonksiyonu sınıfları. Journal of Computer and System Sciences, 18(2):143–154, 1979.

[CW91] C.-C. Chang ve T.-C. Wu. Seyrek tablo sıkıştırmasına dayanan harf yönelimli mükemmel karma şeması. Software—Practice and Experience, 21(1):35–49, Ocak 1991.

[DGMP92] M. Dietzfelbinger, J. Gil, Y. Matias ve N. Pippenger. Polinom karma fonksiyonları güvenilirdir. 19th International Colloquium on Automata, Languages and Programming (ICALP’92) içinde, LNCS 623, sayfa 235–246, Viyana, Avusturya, Temmuz 1992.

[DHJS83] M.W. Du, T.M. Hsieh, K.F. Jea ve D.W. Shieh. Yeni bir mükemmel karma şemasının incelenmesi. IEEE Transactions on Software Engineering, SE–9(3):305–313, Mart 1983.

[DM90] M. Dietzfelbinger ve F. Meyer auf der Heide. Yeni bir evrensel karma fonksiyonu sınıfı ve gerçek zamanlı dinamik karma. 17th International Colloquium on Automata, Languages and Programming (ICALP’90) içinde, LNCS 443, sayfa 6–19, Warwick University, İngiltere, Temmuz 1990.

[Duk85] R. Duke. Hiperçizgelerde çevrim türleri. Annals of Discrete Mathematics, 27:399–418, 1985.

[ER60] P. Erdős ve A. Rényi. Rastgele çizgelerin evrimi üzerine. Publ. Math. Inst. Hung. Acad. Sci., 5:17–61, 1960.

[FCDH91] E. Fox, Q.F. Chen, A. Daoud ve L. Heath. Sıra koruyan minimal mükemmel karma fonksiyonları ve bilgi erişimi. ACM Transactions on Information Systems, 9(2):281–308, Temmuz 1991.

[FCH92] E. Fox, Q.F. Chen ve L. Heath. Minimal mükemmel karma fonksiyonları oluşturmak için LEND ve daha hızlı algoritmalar. Teknik Rapor TR-92-2, Virginia Polytechnic Institute and State University, Şubat 1992.

[Fel68] W. Feller. Olasılık Kuramına ve Uygulamalarına Giriş. John Wiley & Sons, üçüncü baskı, 1968.

[FHCD92] E.A. Fox, L.S. Heath, Q. Chen ve A.M. Daoud. Büyük veritabanları için pratik minimal mükemmel karma fonksiyonları. Communications of the ACM, 35(1):105–121, Ocak 1992.

[FKS84] M.L. Fredman, J. Komlós ve E. Szemerédi. (O(1)) en kötü durum erişim zamanına sahip seyrek bir tablonun saklanması. Journal of the ACM, 31(3):538–544, Temmuz 1984.

[GBY91] G.H. Gonnet ve R. Baeza-Yates. Algoritmalar ve Veri Yapıları El Kitabı. Addison-Wesley, 1991.

[GS89] M. Gori ve G. Soda. Cichelli’nin mükemmel karma yaklaşımına cebirsel bir yaklaşım. BIT, 29(1):209–214, 1989.

[HK86] G. Haggard ve K. Karplus. Minimal mükemmel karma fonksiyonlarının bulunması. ACM SIGCSE Bulletin, 18:191–193, 1986.

[HM92] G. Havas ve B.S. Majewski. Minimal mükemmel karma için en uygun algoritmalar. Teknik Rapor 234, The University of Queensland, Temmuz 1992.

[Jae81] G. Jaeschke. Karşılıklı karma: minimal mükemmel karma fonksiyonları üretme yöntemi. Communications of the ACM, 24(12):829–833, Aralık 1981.

[JvEB86] C.T.M. Jacobs ve P. van Emde Boas. Tablolar üzerine iki sonuç. Information Processing Letters, 22:43–48, 1986.

[KU86] A. Karlin ve E. Upfal. Paralel karma — paylaşılan belleğin verimli bir gerçekleştirilmesi. 18th Annual ACM Symposium on Theory of Computing (STOC’86) içinde, sayfa 160–168, Mayıs 1986.

[LC88] T.G. Lewis ve C.R. Cook. Dinamik ve statik iç tablolar için karma. Computer, 21:45–56, 1988.

[Meh84] K. Mehlhorn. Veri Yapıları ve Algoritmalar 1: Sıralama ve Arama. Springer-Verlag, 1984.

[Mey90] F. Meyer auf der Heide. Dinamik karma stratejileri. 15th Symposium on Mathematical Foundations of Computer Science (MFCS’90) içinde, sayfa 76–87, Ağustos 1990.

[MWCH92] B.S. Majewski, N.C. Wormald, Z.J. Czech ve G. Havas. Minimal mükemmel karma fonksiyonları üreten bir üreteç ailesi. Teknik Rapor 16, DIMACS, Rutgers University, Nisan 1992.

[Pea90] P.K. Pearson. Değişken uzunluklu metin dizgilerinin hızlı karmalanması. Communications of the ACM, 33(6):677–680, Haziran 1990.

[Sag85] T.J. Sager. Minimal mükemmel karma fonksiyonları için polinom zamanlı bir üreteç. Communications of the ACM, 28(5):523–532, Mayıs 1985.

[Sie89] A. Siegel. Hızlı ve yüksek performanslı karma fonksiyonlarının evrensel sınıfları, bunların zaman-uzay değiş tokuşu ve uygulamaları üzerine. 30th Annual Symposium on Foundations of Computer Science (FOCS’89) içinde, sayfa 20–25, Ekim 1989.

[Spr77] R. Sprugnoli. Mükemmel karma fonksiyonları: statik kümeler için tek yoklama ile erişim yöntemi. Communications of the ACM, 20(11):841–850, Kasım 1977.

[SS89] J.P. Schmidt ve A. Siegel. Kapalı karma için evrensellik ve performansın bazı yönleri üzerine. 21st Annual ACM Symposium on Theory of Computing (STOC’89) içinde, sayfa 355–366, Mayıs 1989.

[SS90a] J.P. Schmidt ve A. Siegel. Sınırlı rastgelelik altında kapalı karmanın analizi. 22nd Annual ACM Symposium on Theory of Computing (STOC’90) içinde, sayfa 224–234, Mayıs 1990.

[SS90b] J.P. Schmidt ve A. Siegel. Kör k-sonda karma fonksiyonlarının uzamsal karmaşıklığı. SIAM Journal on Computing, 19(5):775–786, Ekim 1990.

[SvEB84] C. Slot ve P. van Emde Boas. Bant ile çekirdek bellek karşılaştırması üzerine: uzay açısından verimli karma fonksiyonlarının uzay değişmezliğine uygulanması. 16th Annual ACM Symposium on Theory of Computing (STOC’84) içinde, sayfa 391–400, Mayıs 1984.

[TVL84] R.E. Tarjan ve J. Van Leeuwen. Küme birleştirme algoritmalarının en kötü durum analizi. Journal of the ACM, 31(2):245–281, Nisan 1984.

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

[Win90a] V.G. Winters. Büyük veri kümeleri için minimal mükemmel karma. International Conference on Computing and Information (ICCI’90) içinde, sayfa 275–284, Niagara Falls, Kanada, Mayıs 1990.

[Win90b] V.G. Winters. Polinom zamanda minimal mükemmel karma. BIT, 30(2):235–244, 1990.

[YD85] W.P. Yang ve M.W. Du. Eşleme fonksiyonları kümesinden mükemmel karma fonksiyonları oluşturmak için geri izleme yöntemi. BIT, 25(1):148–164, 1985.