Bölüm 14: Hash Tabloları

14.1Hash fikri

Bir öğrenci işleri programı düşünelim. Program, öğrenci numarası verilince o öğrencinin kaydını bulmalıdır. Kayıtlar her gün binlerce kez sorgulanır, arada yeni öğrenciler eklenir, mezunlar silinir. Bu iş için hangi veri yapısı seçilmelidir? Kesim bu soruya bilinen yapıların maliyetiyle başlar ve hash tablosunun neden farklı olduğunu gösterir.

14.1.1Arama maliyetini sabite indirmek

Kayıtlar sırasız bir dizide tutulursa ekleme çok ucuzdur: yeni kayıt dizinin sonuna yazılır. Arama ise pahalıdır. Aranan numara dizinin herhangi bir yerinde olabilir ya da hiç olmayabilir. Bu yüzden en kötü durumda n kaydın hepsine bakılır. Silme de aramayla başladığı için O(n)'dir. Dizi numaraya göre sıralı tutulursa arama ikili aramayla O(lg n)'e iner. Bu kez ekleme ve silme pahalanır: sıra bozulmasın diye yeni kaydın yerinden sonraki bütün kayıtlar bir göz kaydırılır. Dengeli bir arama ağacı üç işlemi de O(lg n)'de yapar ve kayıtları sıralı gezmeyi de sağlar. Tablo 14.1 dört yapıyı karşılaştırır.

İlk üç yapının ortak bir sınırı vardır: hepsi anahtarları karşılaştırarak arar. Her karşılaştırma iki sonuç verir, “küçük” ya da “büyük”. n olası konum arasından birini seçmek için en az lg n tane iki sonuçlu karar gerekir. Karşılaştırmaya dayalı bir yapı bu yüzden O(lg n)'in altına inemez. Hash tablosu bu sınırı karşılaştırmayı bırakarak aşar. Anahtardan konum doğrudan hesaplanır: konum = h(anahtar). Hesap birkaç aritmetik işlemdir ve n'ye bağlı değildir.

Kazancın bir bedeli vardır. Hash tablosu öğeleri anahtar sırasıyla tutmaz; konumlar hesabın sonucuna göre dağılır. Bu yüzden bazı sorgular hash tablosunda ucuz değildir. “Bütün kayıtları numara sırasıyla yaz”, “en küçük numarayı bul” ya da “numarası 1000 ile 2000 arasındaki kayıtları listele” bunlardandır. Bu sorgular için bütün tabloyu taramak, gerekirse ayrıca sıralamak gerekir. İkinci bedel en kötü durumdur. Bütün anahtarlar aynı konuma düşerse tablo uzun bir listeye döner ve arama O(n) olur. Ortalama durumun sabit kalması, iyi bir hash fonksiyonuna ve tablonun yeterince boş tutulmasına bağlıdır. Notun geri kalanı bu iki koşulu inceler.

14.1.2Doğrudan adresleme

Hash fikrinin en yalın biçimi, anahtarın kendisini dizi indisi olarak kullanmaktır. Anahtarlar 0 ile 9 arasında birer tamsayıysa on gözlü bir dizi yeterlidir: k anahtarlı kayıt T[k] gözüne yazılır. Arama için T[k]'ye bakmak yeter; döngü yoktur, karşılaştırma yoktur.

Şekil 14.1 bu düzeni gösterir. Evren on anahtardan oluşur, kullanılan anahtarlar ise yalnız 2, 3, 5 ve 8'dir. Her kayıt kendi numarasının gözündedir; öteki altı göz boştur.

Sunumdaki C kodu her gözü küçük bir yapıyla gösterir. var alanı gözün dolu olup olmadığını, ad alanı kaydın verisini tutar.

typedef struct { int var; char ad[16]; } kayit;
kayit T[10];               /* anahtar = indis */

kayit *da_ara(int k) {
  return T[k].var ? &T[k] : NULL;
}

Kod kısadır ama her satırı bir karar taşır. İlk satır kayit adlı yapı tipini tanımlar. Yapıda iki alan vardır: int tipinde var ve 16 karakterlik ad dizisi. typedef sayesinde tip adı her seferinde struct yazmadan kullanılır. İkinci satır on gözlü T dizisini global olarak tanımlar. C'de global değişkenler program başlarken sıfırla doldurulur. Bu yüzden başlangıçta bütün gözlerin var alanı 0'dır, yani tablo boştur. Ayrıca bir başlatma döngüsü yazmak gerekmez.

da_ara fonksiyonu k anahtarını alır ve T[k].var alanına bakar. Alan sıfırdan farklıysa göz doludur ve fonksiyon o gözün adresini, &T[k]'yi döndürür. Alan sıfırsa kayıt yoktur ve NULL döner. Koşul ifadesi (? :) bu iki durumu tek satırda yazar. Fonksiyonun kaydın kopyasını değil adresini döndürmesi bilinçli bir seçimdir. Çağıran taraf kaydı bu adres üzerinden okuyabilir ya da değiştirebilir. Bulunamama durumu da NULL ile açıkça bildirilir. Ekleme ve silme de aynı biçimde birer satırdır: ekleme T[k].var = 1 yapıp veriyi yazar, silme T[k].var = 0 yapar. Üç işlem de O(1)'dir.

Test programında 2, 3, 5 ve 8 numaralı gözler Ali, Can, Ece ve Naz adlarıyla dolduruldu. da_ara bu dört anahtar için ilgili adları, öteki altı anahtar için NULL döndürdü. Aynı makinede sizeof(kayit) 20 bayt çıktı (4 baytlık int ve 16 baytlık dizi), on gözlük dizi ise 200 bayt yer kapladı.

Kodda bir varsayım gizlidir: k her zaman 0 ile 9 arasındadır. Bu aralığın dışındaki bir k, dizinin sınırı dışındaki belleği okur. C bu hatayı yakalamaz; sonuç tanımsız davranıştır. Gerçek bir programda fonksiyonun başına if (k < 0 || k >= 10) return NULL; gibi bir denetim eklenmelidir.

Doğrudan adreslemenin sorunu evrenin büyüklüğüdür. Öğrenci numarası dokuz haneliyse |U| = 10⁹'dur. 20 baytlık kayıtlarla bu tablo 20 gigabayt tutar. Üniversitede ise belki 20 000 öğrenci vardır: tablonun yalnız on binde ikisi dolu olur, gerisi boş durur. Anahtar bir dizgi olduğunda, örneğin bir değişken adı ya da bir e-posta adresi olduğunda, evren pratikte sonsuzdur. Bu durumda doğrudan adresleme hiç kurulamaz.

Çözüm, anahtarı küçük bir aralığa indiren bir fonksiyondur. Tablonun boyutu kullanılan anahtar sayısına göre seçilir, örneğin m = 40 000 göz. Her anahtar bu fonksiyonla 0 ile m − 1 arasındaki bir indise çevrilir. Bu fonksiyona hash fonksiyonu denir.

14.1.3Hash fonksiyonu ve temel terimler

“Hash” sözcüğü İngilizcede kıymak, doğramak anlamına gelir. Fonksiyon anahtarı parçalara ayırıp karıştırır ve küçük bir sayı üretir. Türkçe kaynaklarda “karma fonksiyonu” ve “özetleme” karşılıkları da görülür. Bu ders, sözlükteki gibi “hash” sözcüğünü kullanır.

Hash fonksiyonu |U| değeri m indise eşler ve m, |U|'dan çok küçüktür. Bu yüzden bazı farklı anahtarlar aynı indise düşmek zorundadır. Buna güvercin yuvası ilkesi denir: on bir güvercin on yuvaya girerse en az bir yuvada iki güvercin bulunur. Şekil 14.2 dört isim anahtarını altı kovaya eşleyen bir fonksiyonu gösterir. Ali ile Ece'nin ev adresi aynıdır, 3.

Tablo 14.2 terimleri bir arada verir. “Eş anlamlı” adı dilbilimden gelir: iki sözcük farklı yazılıp aynı anlamı taşıdığı gibi, iki anahtar da farklı olup aynı adrese çıkar. Yük faktörü tablonun ne kadar dolu olduğunu ölçer. α = 0,5 tablonun yarısının dolu olduğunu söyler. Bazı çakışma çözümlerinde bir kovada birden çok öğe tutulabilir ve α 1'i aşabilir.

m < |U| olduğu sürece çakışma kaçınılmazdır. Bu durumda hash tablosu tasarımı iki soruya iner. Birincisi, iyi bir h nasıl seçilir: anahtarlar kovalara olabildiğince eşit dağılmalı, çakışma az olmalıdır. İkincisi, çakışma olduğunda ne yapılır: aynı adrese düşen ikinci öğe nereye konur ve aranırken nasıl bulunur? Hash fonksiyonları ilk sorunun, açık adresleme ve zincirleme ikinci sorunun cevabıdır.

14.1.4Sözlük soyut veri tipi

Hash tablosu bir gerçeklemedir. Gerçeklediği soyut veri tipi ise sözlüktür. Soyut veri tipi, bir yapının değerlerini ve işlemlerini, bu işlemlerin nasıl yazıldığından bağımsız olarak tanımlar. Sözlük, gündelik sözlüğe benzer: bir sözcük (anahtar) verilir, karşılığı (değer) bulunur.

typedef struct { int anahtar; /* + değer */ } oge;

bool hash_ekle(oge x);      /* varsa günceller */
oge *hash_ara(int anahtar); /* yoksa NULL      */
bool hash_sil(int anahtar); /* yoksa false     */

Sunumdaki arayüz üç işlemi C bildirimleriyle verir. oge yapısı anahtarı tutar; yorumdaki “+ değer” ifadesi, gerçek bir uygulamada yapıya başka alanların da ekleneceğini söyler. hash_ekle bir öğeyi alır ve işlemin başarılı olup olmadığını bool olarak döndürür. Anahtar zaten varsa yeni öğe eklenmez; var olanın değeri güncellenir. Böylece “her anahtar en çok bir kez” kuralı korunur. hash_ara öğenin adresini döndürür; anahtar yoksa NULL verir. hash_sil anahtarı bulup silerse true, bulamazsa false döndürür. bool, true ve false C99 ile gelen <stdbool.h> başlığındadır; bu başlık eklenmeden kod derlenmez.

Sözlük çok yerde karşımıza çıkar. Derleyici, kaynak koddaki her değişken adını bir sembol tablosunda tutar: ad anahtardır, tipi ve bellekteki yeri değerdir. Horowitz'in ders kitabı hash tablolarını bu örnekle açar. Derleyici her satırda birçok ad arar; aramanın sabit zamanda bitmesi derlemeyi hızlandırır. Web tarayıcılarının önbellekleri adresi anahtar, sayfayı değer olarak tutar. Bir listede tekrar eden öğeleri bulmak için her öğe bir kümeye eklenir; eklenmeden önce kümede aranır. Küme, değeri olmayan bir sözlüktür.

Python'daki dict, Java'daki HashMap ve C++'taki unordered_map birer hash tablosudur. C'nin standart kitaplığında ise hazır bir hash tablosu yoktur. POSIX standardı hsearch adlı sınırlı bir yordam verir: aynı anda tek bir tablo kurulabilir ve tablodan öğe silinemez. Bu yüzden C programcısı hash tablosunu kendisi yazmayı bilmelidir. Notun kalan kesimleri tam olarak bunu yapar.

14.2Hash fonksiyonları

Hash tablosunun hızı, anahtarların kovalara ne kadar eşit dağıldığına bağlıdır. Bütün anahtarları aynı kovaya atan bir fonksiyon da geçerli bir fonksiyondur, ama tabloyu tek bir uzun listeye çevirir. Bu kesim önce iyi bir fonksiyondan beklenenleri sıralar, sonra tamsayı ve dizgi anahtarlar için yaygın yöntemleri hesaplar.

14.2.1İyi bir hash fonksiyonunun özellikleri

İyi bir hash fonksiyonunda dört özellik aranır.

• Hızlı olmalıdır. Fonksiyon her aramada, eklemede ve silmede çalışır. Hesap birkaç aritmetik işlemle bitmelidir. Anahtar bir dizgiyse her karakter en çok bir kez işlenmeli, yani maliyet anahtar uzunluğuyla doğrusal olmalıdır.
• Düzgün dağıtmalıdır. Anahtarlar m kovaya olabildiğince eşit sayıda düşmelidir. Kuramsal analizler bunu bir varsayım olarak kabul eder: her anahtar, öteki anahtarlardan bağımsız olarak m kovanın her birine 1/m olasılıkla düşer. Bu varsayıma basit düzgün hash (simple uniform hashing) varsayımı denir.
• Anahtarın bütün bitlerini kullanmalıdır. Gerçek veriler genellikle örüntülüdür. Fiyatlar 5 ya da 0 ile biter, bellek adresleri 8'in katıdır, öğrenci numaraları aynı yıl kodlarıyla başlar. Yalnız son basamağa ya da son birkaç bite bakan bir fonksiyon, bu örüntüleri kovalara taşır ve anahtarları birkaç kovada kümeler.
• Deterministik olmalıdır. Aynı anahtar her çağrıda aynı kovaya gitmelidir. Aksi hâlde bir kez eklenen öğe sonra bulunamaz. Rastgelelik ancak fonksiyon seçilirken kullanılabilir: program başlarken bir fonksiyon ailesinden rastgele biri seçilir ve program boyunca o kullanılır.

Düzgün dağılım, anahtar kümesi bilinmeden garanti edilemez. Her sabit hash fonksiyonu için, hepsi aynı kovaya düşen bir anahtar kümesi bulunabilir. Yöntemlerin amacı, gerçek hayatta görülen örüntülü verilerde iyi davranmaktır.

14.2.2Bölme yöntemi

En basit ve en yaygın yöntem, anahtarı tablo boyutuna bölüp kalanı almaktır.

unsigned h_bolme(unsigned k, unsigned m) { return k % m; }

Fonksiyon tek bir % işlemidir. Parametrelerin unsigned seçilmesi önemlidir; nedeni bu alt kesimin sonunda verilir. Yöntemin bütün inceliği m'nin seçimindedir. Tablo 14.3 sekiz anahtarı iki farklı tablo boyutuyla dağıtır.

m = 10 iken k mod 10, k'nin son ondalık basamağıdır. Fonksiyon öteki basamakları hiç görmez. 10, 20, …, 60 anahtarlarının hepsi 0 ile biter ve hepsi 0. kovaya düşer; 17 ile 27 de 7. kovada çakışır. Sekiz anahtar yalnız iki kovaya dağılmıştır. m = 11 iken aynı sekiz anahtar altı farklı kovaya gider. Hâlâ iki çakışma vardır (50 ile 17 kova 6'da, 60 ile 27 kova 5'te), ama 10'un katları artık art arda kovalara yayılır. Bunun nedeni, 11'in 10 ile ortak böleninin olmamasıdır: 10j mod 11, j = 1, …, 10 için on farklı değer alır.

Aynı sorun 2'nin kuvvetlerinde daha da belirgindir. m = 2^p ise k mod 2^p, k'nin ikili gösterimindeki en düşük p bittir. Bilgisayardaki veriler ikili sayılarla tutulduğu için son bitlerdeki örüntüler çok yaygındır. 8 baytlık yapıların adresleri her zaman 8'in katıdır, yani son üç biti 000'dır. Bu adresler m = 16'lık bir tabloda yalnız 0 ve 8 numaralı kovalara düşer. Bu yüzden şu kural önerilir (CLRS): m olarak, 2'nin bir kuvvetine yakın olmayan bir asal sayı seçilmelidir. Örneğin yaklaşık 2000 anahtar için 701 iyi bir seçimdir: asaldır ve 512 ile 1024'ten uzaktır. Bu tabloda kova başına ortalama üç anahtar düşer.

Bölme yönteminin C'de bir tuzağı daha vardır. C'de % işlecinin sonucu, bölünenle aynı işareti taşır: -7 % 11 ifadesi 4 değil −7'dir. Anahtar int tipindeyse ve negatif olabiliyorsa k % m negatif bir indis verir. Dizinin başından önceki bellek okunur ya da üzerine yazılır. Çare iki yoldan biridir. Ya anahtar baştan unsigned tutulur (sunumdaki h_bolme bunu yapar) ya da kalan pozitif yapılır:

unsigned h_guvenli(int k, int m) {
  int r = k % m;            /* -m < r < m */
  if (r < 0) r += m;        /* ((k % m) + m) % m ile aynı */
  return (unsigned)r;
}

Test programında -7 % 11 gerçekten −7 verdi; h_guvenli(-7, 11) ise 4, h_guvenli(-22, 11) 0 döndürdü. Kalan −m ile m arasında olduğu için bir kez m eklemek onu 0 ile m − 1 arasına taşır. Sunumdaki ((k % m) + m) % m ifadesi aynı işi dallanmadan yapar.

Maliyet. Bölme yöntemi tek bir tamsayı bölmesidir: O(1). Bölme, toplama ve çarpmaya göre işlemcide daha yavaş bir işlemdir; yine de anahtar başına bir kez yapıldığı için tablonun maliyetini değiştirmez.

14.2.3Çarpma yöntemi

Bölme yöntemi iyi bir m ister. Çarpma yöntemi bu bağımlılığı azaltır: karıştırma işini m değil, sabit bir çarpan yapar.

Hesap iki adımdır. Önce k, A ile çarpılır ve sonucun tam kısmı atılır. Geriye 0 ile 1 arasında bir kesir kalır. Sonra bu kesir m ile çarpılır ve aşağı yuvarlanır; sonuç 0 ile m − 1 arasında bir tamsayıdır. Kesir kısmı, k'nin bütün basamaklarından etkilenir. Bu yüzden m'nin seçimi kritik değildir ve m = 2^p rahatlıkla seçilebilir. Knuth, A için altın oranın kesir kısmını önerir: A ≈ (√5 − 1)/2 = 0,6180339887… Bu değer, ardışık anahtarları kesir aralığına çok düzgün yayar.

Örnek (CLRS). k = 123456, p = 14, yani m = 2¹⁴ = 16384 alalım. Kayan noktalı hesap şöyledir:

k · A = 123456 · 0,6180339887 = 76300,0041151…
k · A mod 1 = 0,0041151…
m · 0,0041151… = 16384 · 0,0041151… = 67,42…
h(k) = ⌊67,42…⌋ = 67

Bilgisayarda kayan noktalı sayılar yuvarlama hatası taşır ve yavaştır. Bu yüzden yöntem genellikle tamsayılarla yazılır. Sözcük uzunluğu w = 32 bit olsun ve s = ⌊A · 2³²⌋ = 2654435769 alınsın. k · s çarpımının alt 32 biti, k · A'nın kesir kısmının 2³² katıdır. Bu 32 bitin en üstteki p biti, kesir kısmının 2^p katının tam kısmıdır. Tam olarak aranan değer budur.

/* w = 32 bit, m = 2^p; s = A * 2^32 */
uint32_t h_carpma(uint32_t k, int p) {
  const uint32_t s = 2654435769u;
  return (uint32_t)(k * s) >> (32 - p);
}

Kod üç satırdır. uint32_t, <stdint.h> başlığındaki tam 32 bitlik işaretsiz tamsayı tipidir. k * s çarpımı iki uint32_t arasında yapılır ve sonuç 32 bite sığmazsa taşar. İşaretsiz tamsayılarda taşma C'de tanımlıdır: sonuç 2³²'ye göre kalandır, yani üstteki bitler atılır. Atılan kısım çarpımın tam kısmına, kalan 32 bit kesir kısmına karşılık gelir. Son olarak >> (32 - p) kaydırması alt 32 − p biti atar ve üstteki p biti bırakır.

Örnek üzerinde: 123456 · 2654435769 = 327 706 022 297 664'tür. Bu sayının 2³²'ye göre kalanı 17 612 864'tür. 18 bit sağa kaydırmak 2¹⁸ = 262 144'e bölüp tam kısmı almaktır: 17 612 864 / 262 144 = 67,19…, sonuç 67. Test programı hem tamsayı sürümünden hem kayan noktalı sürümden 67 aldı. İki sürümün kesirleri küçük farklar gösterir (67,42 ve 67,19), çünkü s, A · 2³²'nin yuvarlanmış hâlidir; tam kısımları ise aynıdır.

Kodun bir sınırı vardır: p 1 ile 32 arasında olmalıdır. p = 0 verilirse kaydırma miktarı 32 olur ve 32 bitlik bir sayıyı 32 bit kaydırmak C'de tanımsız davranıştır. m = 1'lik bir tablo zaten anlamsız olduğu için bu durum pratikte sorun çıkarmaz, ama fonksiyonun sözleşmesine yazılmalıdır. Maliyet: bir çarpma ve bir kaydırma, O(1). Çarpma bölmeden hızlı olduğu için yöntem hız açısından da avantajlıdır.

14.2.4Katlama ve orta-kare

Anahtar bir işlemci sözcüğüne sığmayacak kadar uzunsa, örneğin 14 haneli bir kimlik numarasıysa, önce kısaltılmalıdır. Katlama yöntemi bunu yapar.

Horowitz'in örneğinde anahtar x = 12320324111220'dir. Üç haneli parçalar P₁ = 123, P₂ = 203, P₃ = 241, P₄ = 112 ve P₅ = 20'dir; son parça iki hanelidir. Şekil 14.3 iki toplamı gösterir.

Kaydırmalı katlamada toplam 123 + 203 + 241 + 112 + 20 = 699'dur. Sınırda katlamada anahtar bir kâğıt şerit gibi parça sınırlarından zikzak katlanır. Katlanınca her ikinci parça ters yüzüyle üste gelir ve rakamları tersten okunur. Toplam 123 + 302 + 241 + 211 + 20 = 897'dir. Sonuç tablo boyutundan büyükse ayrıca mod m alınır; örneğin m = 11 için iki değer de 6 verir. Aşağıdaki fonksiyon iki türü bir bayrakla hesaplar. Anahtar bir rakam dizgisi olarak verilir, çünkü 14 haneli bir sayı 32 bitlik bir tamsayıya sığmaz.

/* x: rakam dizgisi; parçalar r haneli, soldan sağa */
unsigned katlama(const char *x, int r, bool sinirda) {
  unsigned toplam = 0;
  int n = (int)strlen(x);
  for (int bas = 0, sira = 0; bas < n; bas += r, sira++) {
    int son = bas + r < n ? bas + r : n;   /* parça: [bas, son) */
    unsigned parca = 0;
    if (sinirda && sira % 2 == 1)          /* çift sıradaki parça ters */
      for (int j = son - 1; j >= bas; j--) parca = parca * 10 + (unsigned)(x[j] - '0');
    else
      for (int j = bas; j < son; j++) parca = parca * 10 + (unsigned)(x[j] - '0');
    toplam += parca;
  }
  return toplam;
}

Dış döngü bas değişkenini her turda r artırır ve parçaları sırayla dolaşır; sira parçanın 0 tabanlı sırasıdır. son, parçanın bittiği yerin bir sonrasıdır; son parça kısa kalabileceği için bas + r ile n'nin küçüğü alınır. İç döngüler parçanın rakamlarını sayıya çevirir: her rakam için parca = parca * 10 + rakam. x[j] - '0' ifadesi bir rakam karakterini sayı değerine çevirir; '7' - '0' 7'dir. Sınırda katlamada tek sıradaki parçalar (ikinci, dördüncü, …) sağdan sola okunur. Test programında fonksiyon 699 ve 897 değerlerini verdi. Anahtarın her rakamı bir kez işlendiği için maliyet anahtar uzunluğuyla doğrusaldır.

Orta-kare (mid-square) yöntemi anahtarın karesini alır ve sonucun ortasındaki r biti indis olarak kullanır; tablo boyutu m = 2^r seçilir. Neden orta? Bir sayının karesinin en düşük bitleri yalnız sayının en düşük bitlerine bağlıdır; en yüksek bitleri de büyük ölçüde sayının büyüklüğüne bağlıdır. Ortadaki bitler ise çarpımda k'nin hemen bütün bitlerinin katkısıyla oluşur. Ondalık bir örnekle fikir kolay görülür: k = 1234 için k² = 1522756'dır. Yedi basamağın ortadaki üçü 227'dir; m = 1000'lik bir tabloda ev adresi 227 olur. 1234'ün herhangi bir basamağı değişse bu üç basamak da değişir.

14.2.5Dizgi anahtarlar: polinom hash'i

Pratikte anahtarların çoğu dizgidir: değişken adları, kullanıcı adları, sözcükler. Dizgiyi bir tamsayıya çevirmenin akla gelen ilk yolu, karakter kodlarını toplamaktır.

unsigned toplama_hash(const char *s, unsigned m) {  /* kötü örnek */
  unsigned h = 0;
  for (; *s != '\0'; s++)
    h += (unsigned char)*s;
  return h % m;
}

Bu fonksiyon kötüdür. Toplama sırayı unutur: “abc” ve “cba” aynı harflerden oluşur, toplamları 97 + 98 + 99 = 294 olur ve ikisi de aynı kovaya düşer. Bir dizginin harflerinin yer değiştirmesiyle elde edilen dizgilere anagram denir; toplama hash'i bütün anagramları çakıştırır. İkinci sorun aralığın darlığıdır. 8 harfli küçük harf dizgilerinin toplamı en çok 8 · 122 = 976'dır. Tablo 10 000 kovalı olsa bile anahtarlar ilk bin kovaya sıkışır.

Çözüm, her karakterin konumunu da hesaba katmaktır. n karakterli c₀ c₁ … c_n−1 dizgisi, 31 tabanında bir sayı gibi okunur:

h = c₀ · 31ⁿ⁻¹ + c₁ · 31ⁿ⁻² + … + c_n−2 · 31 + c_n−1

Bu ifade bir polinomdur. Doğrudan hesaplansaydı her terim için ayrı bir üs alınırdı. Horner kuralı polinomu iç içe yazar: h = (…((c₀ · 31 + c₁) · 31 + c₂) · 31 + …) + c_n−1. Böylece her karakterde bir çarpma ve bir toplama yeter. Sunumdaki iki fonksiyon bu kuralı kullanır.

unsigned dizgi_hash(const char *s, unsigned m) {
  unsigned h = 0;
  for (; *s != '\0'; s++)
    h = (h * 31 + (unsigned char)*s) % m;
  return h;
}

dizgi_hash, h'yi 0'dan başlatır. Döngü, s işaretçisini dizginin karakterleri üzerinde ilerletir ve '\0' sonlandırıcısında durur. Her adımda h, 31 ile çarpılıp yeni karakterin kodu eklenir ve sonucun mod m'si alınır. (unsigned char)*s dönüşümü önemlidir: char birçok derleyicide işaretlidir ve “ç”, “ğ” gibi ASCII dışı baytlar negatif değer taşır. Dönüşüm, karakteri 0–255 arasında bir sayı olarak okur.

Her adımda mod almanın iki yararı vardır. Birincisi, h her zaman m'den küçük kalır ve çarpım taşmaz (yeter ki 31 · m + 255 bir unsigned'a sığsın). İkincisi, sonuç değişmez: modüler aritmetikte (a · 31 + c) mod m, ((a mod m) · 31 + c) mod m'ye eşittir. Ara adımlarda mod almak, en sonda bir kez almakla aynı sonucu verir.

unsigned long djb2(const char *s) {  /* Bernstein */
  unsigned long h = 5381;
  int c;
  while ((c = (unsigned char)*s++) != 0)
    h = h * 33 + c;
  return h;       /* sonra: h % m */
}

İkinci fonksiyon, Dan Bernstein'ın yaygın kullanılan djb2 hash'idir. 5381 başlangıç değeriyle başlar ve her karakterde h · 33 + c hesaplar. Ara adımlarda mod almaz; unsigned long taşınca sonuç kendiliğinden 2^w'ye göre kalan olur (w, tipin bit sayısıdır). İşaretsiz taşma C'de tanımlı olduğu için bu güvenlidir. Tablo indisi için çağıran taraf sonucun mod m'sini alır. Döngü koşulundaki (c = (unsigned char)*s++) != 0 ifadesi üç iş yapar: karakteri okur, işaretçiyi ilerletir ve karakterin sıfır olup olmadığına bakar. Windows'ta unsigned long 32 bit, Linux'ta 64 bittir; bu yüzden djb2 aynı dizgi için iki sistemde farklı sayılar verebilir. Test makinesinde (Windows) djb2("kedi") 2090432258 çıktı.

Tablo 14.4 üç fonksiyonu anagramlar üzerinde karşılaştırır. Polinom hash'i “abc” ile “cba”yı ayırır, çünkü “a” birinde 31² ile, ötekinde 1 ile çarpılır.

31 sayısının seçimi rastgele değildir. Taban tek sayı olmalıdır: çift bir taban, taşma sırasında en düşük bitlere sıfır doldurur ve ilk karakterlerin etkisi kaybolur. Taban ayrıca alfabedeki harf sayısından büyük olmalıdır ki farklı dizgiler aynı “sayıyı” vermesin. Java'nın String.hashCode yöntemi de 31 kullanır. 31 ile çarpmanın ayrıca ucuz bir karşılığı vardır: 31 · h = 32 · h − h, yani bir kaydırma ve bir çıkarma.

Maliyet. Üç dizgi fonksiyonu da her karakteri bir kez işler. L karakterli bir anahtar için zaman O(L), bellek O(1)'dir. Hash tablosunun “O(1)” maliyeti, dizgi anahtarlarda aslında “O(L)” demektir. Anahtar uzunluğu tablo boyutundan bağımsız olduğu için bu sabit sayılır.

14.2.6Kod izleme: dizgi_hash("kedi", 11)

“kedi” dizgisinin karakter kodları ASCII tablosunda k = 107, e = 101, d = 100 ve i = 105'tir. Tablo 11 kovalıdır. Tablo 14.5 döngünün her turunu gösterir.

İlk turda h sıfır olduğu için çarpımın etkisi yoktur ve h, 107'nin 11'e göre kalanı olur: 107 = 9 · 11 + 8. İkinci turda eski değer 31 ile çarpılır, “e”nin kodu eklenir: 349 = 31 · 11 + 8. Üçüncü ve dördüncü turlar 7 ve 3 verir. Beşinci denetimde *s sonlandırıcı karakterdir, döngü biter ve fonksiyon 3 döndürür. “kedi” anahtarının ev adresi 3'tür.

Sonucu bir de ara adımlarda mod almadan denetleyelim. Tam polinom 107 · 31³ + 101 · 31² + 100 · 31 + 105 = 3 187 637 + 97 061 + 3 100 + 105 = 3 287 903'tür ve 3 287 903 mod 11 = 3'tür. İki hesap aynı sonucu verir; ara adımlarda mod almanın sonucu değiştirmediği burada sayılarla da görülür. Dört karakterli dizgi için döngü dört kez döner ve beşinci denetimde biter: maliyet dizgi uzunluğuyla doğrusaldır.

14.3Açık adresleme

İyi bir hash fonksiyonu çakışmayı azaltır ama ortadan kaldıramaz. Bu kesim önce çakışmanın ne kadar erken başladığını gösterir, sonra çakışan öğeyi tablonun içinde başka bir yuvaya yerleştiren yöntemleri inceler.

14.3.1Çakışma kaçınılmazdır

Tablo büyük ve anahtar sayısı azsa çakışmanın nadir olacağı düşünülebilir. Olasılık hesabı bu sezgiyi yanlışlar. Ünlü doğum günü paradoksu şunu söyler: 23 kişilik bir sınıfta iki kişinin doğum gününün aynı gün olma olasılığı yaklaşık %50,7'dir. Hesap tümleyenden yapılır. 23 kişinin hepsinin farklı günlerde doğmuş olma olasılığı

(365/365) · (364/365) · (363/365) · … · (343/365) ≈ 0,4927

olur. Birinci kişi herhangi bir günde doğabilir; ikinci kişinin ondan farklı günde doğma olasılığı 364/365'tir; üçüncü kişi ilk ikisinden farklı olmalıdır, ve bu böyle sürer. En az bir çakışma olasılığı 1 − 0,4927 ≈ 0,507'dir.

Bunu hash tablosuna çevirelim: m = 365 yuvalı bir tabloya, her biri rastgele bir yuvaya düşen 23 anahtar eklenir. Tablonun yalnız %6'sı doludur, ama en az bir çakışma olasılığı yarıdan fazladır. Anahtar sayısı 57'ye çıkınca bu olasılık %99'u geçer. Genel kural şudur: m yuvalı bir tabloda ilk çakışma, yaklaşık √m anahtardan sonra beklenir. Bir milyon yuvalı tabloda bu sayı birkaç bindir. Çakışma bu yüzden istisnai bir durum olarak değil, olağan bir durum olarak ele alınmalıdır.

Çakışmanın iki temel çözüm yolu vardır. Şekil 14.5 ikisini aynı anahtarlar üzerinde gösterir.

Açık adreslemede her öğe bir yuva kapladığı için n ≤ m, yani α ≤ 1'dir. Tablo dolunca yeni öğe eklenemez. Zincirlemede (chaining) ise her kova bir bağlı listenin başıdır; aynı kovaya düşen öğeler o listeye eklenir. Liste istendiği kadar uzayabildiği için α > 1 olabilir. Zincirleme, kendi kesiminde ayrıntılı ele alınır. Bu kesimin kalanı açık adreslemenin üç yoklama kuralını inceler: doğrusal yoklama, karesel yoklama ve çift hash. Örneklerin hepsi aynı tabloyu kullanır: m = 11, h(k) = k mod 11 ve sırayla eklenen 22, 1, 13, 11, 24, 33 anahtarları. Bu anahtarların ev adresleri 0, 1, 2, 0, 2, 0'dır: 11 ve 33, 22 ile; 24 de 13 ile çakışır.

14.3.2Doğrusal yoklama

Kural, sinemada yer arayan birine benzer: numaralı koltuk doluysa yanındakine oturulur. Altı anahtarın eklenişi şöyle ilerler.

1. 22'nin ev adresi 22 mod 11 = 0'dır. Yuva 0 boştur; 22 oraya yazılır. Bir yoklama.
2. 1'in ev adresi 1, 13'ün ev adresi 2'dir. İkisi de boş yuvaya düşer; birer yoklama.
3. 11'in ev adresi 0'dır ve 22 ile doludur. Sıradaki yuva 1 (dolu, 1), sonra yuva 2 (dolu, 13), sonra yuva 3'e bakılır. Yuva 3 boştur. Yoklama dizisi 0, 1, 2, 3; dört yoklama.
4. 24'ün ev adresi 2'dir ve 13 ile doludur. Yuva 3'te artık 11 vardır. Yuva 4 boştur. Yoklama dizisi 2, 3, 4; üç yoklama.
5. 33'ün ev adresi 0'dır. Yuva 0'dan 4'e kadar hepsi doludur; yuva 5 boştur. Yoklama dizisi 0, 1, 2, 3, 4, 5; altı yoklama.

Son durumda tablonun ilk altı yuvası dolu bir blok oluşturur (Şekil 14.6). Ev adresi bu bloğun içindeki herhangi bir yuvaya düşen yeni anahtar, bloğun sonuna kadar yürür ve oraya yerleşir; blok bir yuva daha büyür. Blok büyüdükçe ona düşme olasılığı da artar: 6 yuvalık bir blok, 11 olası ev adresinin altısını kapsar. Büyük bloklar daha da büyür.

Birincil kümelenme yalnız eş anlamlıları etkilemez. Örnekte 24'ün ev adresi 2'dir ve 22 ya da 11 ile hiçbir ilgisi yoktur. Yine de 11 yüzünden bir yuva fazla yürümüştür. Farklı ev adresli anahtarlar aynı bloğu paylaşır ve birbirini yavaşlatır. Tablo dolmaya yaklaştıkça bloklar birleşir ve ortalama yoklama sayısı hızla büyür. Bu artışın sayısal değeri yük faktörü kesiminde verilir.

14.3.3C gerçeklemesi: yuva durumu ve ekleme

Açık adreslemede bir yuvanın yalnız “dolu” ya da “boş” olması yetmez. Silme işleminin doğru çalışması için üçüncü bir durum gerekir. Bu durumun neden gerektiği silme kesiminde ayrıntılı gösterilir; burada yalnız tanımı verilir.

#define M 11
typedef enum { BOS, DOLU, SILINDI } durum_t;
typedef struct {
  int anahtar;          /* anahtar >= 0 varsayılır */
  durum_t durum;
} yuva;
yuva tablo[M];          /* global: hepsi 0 = BOS */

#define M 11 tablo boyutunu bir makro sabit olarak tanımlar. Önişlemci, kodun her yerindeki M'yi derlemeden önce 11 ile değiştirir. enum üç sabit tanımlar: BOS = 0, DOLU = 1 ve SILINDI = 2. Değerler belirtilmezse C, ilk sabite 0 verir ve her birini bir artırır. durum_t bu sayıların tip adıdır; kodda 0 yerine BOS yazmak okunurluğu artırır.

yuva yapısının iki alanı vardır: anahtar ve durum. Yorumdaki varsayım (anahtar ≥ 0) bölme yönteminin negatif kalan sorununu bu kod için ortadan kaldırır. tablo dizisi globaldir ve program başlarken sıfırla dolar. BOS sıfıra eşit olduğu için bütün yuvalar başlangıçta boştur. enum sabitlerinin sırası bu yüzden önemlidir: BOS ilk sırada yazılmasaydı tablo başlangıçta boş sayılmazdı.

Bellekte tablo, 11 yapının art arda dizildiği tek bir bloktur. Test makinesinde her yuva 8 bayttır (4 baytlık int ve 4 baytlık enum), tablo 88 bayt yer kaplar. İşaretçi yoktur, malloc yoktur. Bu, açık adreslemenin önemli bir üstünlüğüdür ve tasarım karşılaştırmasında tekrar ele alınır.

int ekle(int k) {
  int i = k % M;                 /* ev adresi */
  for (int d = 0; d < M; d++, i = (i + 1) % M) {
    if (tablo[i].durum != DOLU) {  /* BOS/SILINDI */
      tablo[i].anahtar = k;
      tablo[i].durum = DOLU;
      return i;
    }
  }
  return -1;                     /* tablo dolu */
}

ekle fonksiyonu satır satır şöyle çalışır.

• Satır 2: i, anahtarın ev adresidir. İlk yoklama burada yapılacaktır.
• Satır 3: for döngüsü iki değişken yönetir. d deneme sayacıdır ve 0'dan M − 1'e kadar gider. i bakılan yuvadır ve her turun sonunda bir artırılıp mod M alınır; 10'dan sonra 0'a döner. Virgül işleci iki güncellemeyi tek ifadede yapar.
• Satır 4–8: Yuva DOLU değilse, yani BOS ya da SILINDI ise, anahtar oraya yazılır, durum DOLU yapılır ve yuvanın indisi döndürülür.
• Satır 10: Döngü M denemenin hepsinde dolu yuva bulduysa tablo doludur; fonksiyon −1 döndürür.

Deneme sayısının M ile sınırlanması önemlidir. Doğrusal yoklamanın dizisi M adımda bütün yuvaları bir kez dolaşır. Sınır olmasaydı dolu bir tabloda döngü sonsuza kadar dönerdi. Test programında 0, 11, 22, …, 110 anahtarlarıyla doldurulan tabloya 5 eklenmek istendi; ekle 11 denemeden sonra −1 döndürdü.

Fonksiyonun bilinen bir eksiği vardır: anahtarın tabloda zaten olup olmadığına bakmaz. Aynı anahtar ikinci kez eklenirse yoklama dizisindeki ilk boş yuvaya ikinci bir kopya yazılır. Sözlüğün “her anahtar bir kez” kuralı bu kodda çağıranın sorumluluğundadır. SILINDI yuvalar işin içine girince sorun daha da incelir; çözümü silme kesimindeki ekle_tekil fonksiyonudur.

Maliyet. Ekleme, yoklama sayısı kadar sürer. En iyi durumda ev adresi boştur: Θ(1). En kötü durumda bütün tablo dolaşılır: O(m). Ortalama durum yük faktörüne bağlıdır; α sabit tutulduğu sürece O(1)'dir. Ek bellek kullanılmaz.

14.3.4Kod izleme: ekle(33)

Tabloda 22, 1, 13, 11 ve 24 vardır; yuva 0–4 dolu bir bloktur. Tablo 14.6 ekle(33) çağrısını izler.

Döngü altı tur döner; her turda yapılan iş aynıdır: durum alanına bakmak ve i'yi ilerletmek. Altıncı yoklamada boş yuva bulunur. 33, ev adresinden beş yuva uzağa düşmüştür. Bunun nedeni 33'ün kendi eş anlamlıları değil, bloğun tamamıdır. 0–4 yuvalarındaki beş anahtardan yalnız ikisinin (22 ve 11) ev adresi 33'ünkiyle aynıdır.

14.3.5Arama ve kod izleme

Arama, eklemenin izlediği yoklama dizisini aynen izler. Anahtar tabloda varsa bu dizinin bir yerindedir. Peki aramanın ne zaman “yok” diyeceği nasıl bilinir? Ekleme, yoklama dizisinde rastladığı ilk boş yuvaya yazar. Öyleyse aranan anahtar tabloda olsaydı, dizideki ilk BOS yuvadan önce bulunurdu. BOS bir yuvaya rastlayan arama durabilir.

int ara(int k) {
  int i = k % M;
  for (int d = 0; d < M; d++, i = (i + 1) % M) {
    if (tablo[i].durum == BOS) return -1;
    if (tablo[i].durum == DOLU &&
        tablo[i].anahtar == k) return i;
  }
  return -1;
}
bool sil(int k) {
  int i = ara(k);
  if (i < 0) return false;
  tablo[i].durum = SILINDI;   /* silindi işareti */
  return true;
}

Bu kod parçasında iki fonksiyon vardır; burada ara anlatılır, sil silme kesiminin konusudur. ara, ekle ile aynı döngü iskeletini kullanır. Her yuvada iki soru sorar. Yuva BOS ise arama biter ve −1 döner. Yuva DOLU ve anahtarı k ise aranan bulunmuştur; indis döner. Öteki durumlarda, yani yuva başka bir anahtarla dolu ya da SILINDI ise, arama bir sonraki yuvaya geçer. İkinci if'teki tablo[i].durum == DOLU koşulu gereklidir. SILINDI bir yuvanın anahtar alanında eski anahtar hâlâ durur; bu koşul olmasaydı silinmiş bir anahtar bulunmuş sayılırdı. Döngü M denemede bitip hiç BOS yuvaya rastlamazsa tablo doludur ve anahtar yoktur; fonksiyon yine −1 döner.

Tablo 14.7 iki aramayı izler. Tabloda 22, 1, 13, 11, 24 ve 33 vardır (yuva 0–5).

ara(24) ev adresi 2'den başlar. Yuva 2'de 13 vardır; durum DOLU ama anahtar farklıdır, devam edilir. Yuva 3'te 11 vardır, yine devam. Yuva 4'te 24 bulunur ve 4 döner. Üç yoklama, 24 eklenirken yapılan üç yoklamayla aynıdır. Bu bir rastlantı değildir: başarılı bir arama, anahtarın eklenirken izlediği yolu yeniden yürür.

ara(44) daha uzundur. 44'ün ev adresi 0'dır ve 0–5 bloğunun hepsi başka anahtarlarla doludur. Yuva 6 BOS'tur: 44 tabloda olsaydı en geç buraya yazılırdı, demek ki yoktur. Başarısız arama yedi yoklama sürmüştür. Başarısız aramalar genellikle başarılı aramalardan uzundur, çünkü her zaman bir boş yuvaya kadar yürür. Tabloda olmayan ve ev adresi 6–10 arasına düşen bir anahtarın araması ise tek yoklamada biter. Test programında ara(5) böyle bir aramaydı ve hemen −1 döndü.

Maliyet. Başarılı arama, anahtarın eklenirken yaptığı yoklama sayısı kadar sürer. Başarısız arama, ev adresinden ilk boş yuvaya kadar olan uzaklık kadar sürer. İkisi de en kötü durumda O(m), α sabitken ortalama O(1)'dir.

14.3.6Karesel yoklama

Birincil kümelenmenin nedeni, yoklama dizisinin bitişik yuvalardan geçmesidir. Karesel yoklama, ev adresinden giderek büyüyen adımlarla uzaklaşır.

Aynı altı anahtar karesel yoklamayla şöyle yerleşir. 22, 1 ve 13 yine ev adreslerine düşer. 11'in yoklama dizisi 0, 0 + 1 = 1, 0 + 4 = 4'tür: yuva 0 ve 1 doludur, yuva 4 boştur. 24'ün dizisi 2, 2 + 1 = 3'tür ve yuva 3 boş olduğu için iki yoklamada yerleşir. 33'ün dizisi 0, 1, 4, 9'dur: yuva 0, 1 ve 4 doludur, 33 yuva 9'a yazılır. 33 için doğrusal yoklamada altı yoklama gerekmişti; karesel yoklamada dört yeter.

Son tablo 22, 1, 13, 24, 11 (yuva 0–4) ve 33'tür (yuva 9). Karesel yoklama birincil kümelenmeyi giderir: 24 artık 11'in arkasında beklemez, kendi dizisinde boş bulduğu ilk yere yerleşir. Ama ev adresi aynı olan anahtarlar hâlâ aynı diziyi izler. 22, 11 ve 33'ün üçü de 0, 1, 4, 9, … dizisinde ilerler ve birbirinin önünü keser. Bu daha hafif kümelenmeye ikincil kümelenme (secondary clustering) denir.

Karesel yoklamanın bir sakıncası, yoklama dizisinin bütün yuvaları dolaşmamasıdır. m = 11 ve ev adresi 0 için i = 0, 1, …, 10 denemeleri sırasıyla 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1 yuvalarına bakar. Dizide yalnız altı farklı yuva vardır: 0, 1, 3, 4, 5, 9. Yuva 2, 6, 7, 8 ve 10 hiç yoklanmaz. Tabloda boş yer olduğu hâlde ekleme başarısız olabilir. Şu sonuç bu sorunun sınırını çizer.

Kanıt. 0 ≤ i < j < ⌈m/2⌉ olan iki denemenin aynı yuvaya baktığını varsayalım. O zaman h + i² ≡ h + j² (mod m), yani m, j² − i² = (j − i)(j + i) çarpımını böler. m asal olduğu için çarpanlardan birini bölmelidir. Ama 0 < j − i < m ve 0 < j + i < m'dir (ikisi de m/2'den küçük iki sayının toplamıdır). Bu yüzden iki çarpan da m'nin katı olamaz. Çelişki: ilk ⌈m/2⌉ deneme farklı yuvalara bakar. Tabloda m/2'den az dolu yuva varsa bu farklı yuvalardan en az biri boştur. ∎

m = 11 için ⌈11/2⌉ = 6'dır ve gerçekten ilk altı deneme 0, 1, 4, 9, 5, 3 gibi farklı yuvalara bakar. Teoremin pratik sonucu basittir: karesel yoklama kullanan bir tablo asal boyutlu seçilir ve yarıdan fazla doldurulmaz.

14.3.7Çift hash

İkincil kümelenmenin nedeni, yoklama dizisinin yalnız ev adresine bağlı olmasıdır. Çift hash, adım boyunu da anahtardan hesaplar.

Örnekte h₁(k) = k mod 11 ve h₂(k) = 1 + (k mod 10) seçilmiştir. Adım boyları 11 için 2, 24 için 5, 33 için 4'tür. 22, 1 ve 13 ev adreslerine düşer. 11'in dizisi 0, 2, 4'tür: yuva 0 ve 2 doludur, 11 yuva 4'e yazılır. 24'ün dizisi 2, 7'dir; yuva 7 boştur. 33'ün dizisi 0, 4, 8'dir: yuva 0'da 22, yuva 4'te 11 vardır; 33 yuva 8'e yazılır. 33 için üç yoklama yetmiştir.

Burada 22, 11 ve 33'ün ev adresi aynıdır ama adım boyları farklıdır (sırasıyla 3, 2 ve 4). Üçü farklı yoklama dizileri izler ve birbirinin yolunu kesme olasılıkları azalır. Doğrusal ve karesel yoklamada yoklama dizisi yalnız ev adresine bağlıdır; m farklı ev adresi m farklı dizi verir. Çift hashte dizi, ev adresi ile adım boyunun çiftine bağlıdır. Bu çiftlerin sayısı m'nin karesi mertebesindedir.

h₂ iki koşulu sağlamalıdır. Birincisi, hiçbir zaman 0 olmamalıdır. h₂(k) = 0 olsaydı bütün denemeler ev adresine bakardı ve yoklama hiç ilerlemezdi. h₂'nin başındaki “1 +” bu yüzdendir. İkincisi, h₂(k) ile m aralarında asal olmalıdır. Örneğin m = 10 ve adım boyu 6 olsaydı, yuva 5'ten başlayan dizi 5, 1, 7, 3, 9, 5, … diye dönerdi; on yuvanın yalnız beşi yoklanırdı. m asal seçilirse 1 ile m − 1 arasındaki her adım boyu m ile aralarında asaldır ve koşul kendiliğinden sağlanır. Örnekteki m = 11 asaldır; h₂ 1 ile 10 arasında değer aldığı için her dizi 11 yuvanın hepsini dolaşır.

14.3.8Üç yoklamanın karşılaştırması

Üç yöntem tek bir fonksiyonla yazılabilir. Aşağıdaki kod, i. denemenin yuvasını yönteme göre hesaplayan yokla fonksiyonunu ve onu kullanan genel bir ekleme fonksiyonunu verir. tablo, yuva ve M tanımları açık adreslemedeki tanımlarla aynıdır.

typedef enum { DOGRUSAL, KARESEL, CIFT } yontem_t;

int yokla(int k, int i, yontem_t y) {   /* i. denemenin yuvası */
  int h1 = k % M;
  switch (y) {
    case DOGRUSAL: return (h1 + i) % M;
    case KARESEL:  return (h1 + i * i) % M;
    default:       return (h1 + i * (1 + k % 10)) % M;  /* h2 */
  }
}

int ekle_y(int k, yontem_t y) {
  for (int d = 0; d < M; d++) {
    int i = yokla(k, d, y);
    if (tablo[i].durum != DOLU) {
      tablo[i].anahtar = k;
      tablo[i].durum = DOLU;
      return i;
    }
  }
  return -1;
}

yontem_t üç yöntemi adlandırır. switch deyimi yönteme göre formüllerden birini seçer. Çift hash dalında adım boyu 1 + k % 10'dur. Bu kod m'yi değil 10'u kullandığı için yalnız örnekteki tabloya uygundur. Genel bir tabloda h₂, örneğin 1 + (k mod (m − 2)) gibi m'ye bağlı seçilir. ekle_y, ekle'nin aynısıdır; tek farkı yuvayı i = (i + 1) % M yerine yokla ile bulmasıdır. Karesel yoklamada i * i çarpımı, i < M olduğu sürece taşmaz. Test programı altı anahtarı üç yöntemle ayrı ayrı ekledi; sonuçlar Tablo 14.8 ile birebir aynıdır.

Bu tablolara bakınca çift hashin her zaman seçilmesi gerektiği düşünülebilir. Gerçek bilgisayarlarda durum daha karışıktır. İşlemci belleği tek tek bayt olarak değil, 64 baytlık bloklar hâlinde önbelleğe getirir. Doğrusal yoklamada ardışık yuvalar aynı bloktadır: ilk yoklama bloğu getirince sonraki birkaç yoklama neredeyse bedavaya yapılır. Çift hashin sıçramaları ise her yoklamada başka bir bloğa düşer. Bu yüzden doğrusal yoklama önbellek dostudur ve α küçükken (örneğin 0,5'in altında) çok hızlıdır. α büyüdükçe kümelenme yüzünden yoklama sayısı hızla arttığı için çift hash öne geçer. Seçim, tablonun ne kadar dolu tutulacağına bağlıdır.

14.4Zincirleme

Açık adreslemede çakışan öğe başka bir yuvaya gider ve başka anahtarların yerini işgal eder. Zincirleme bunun tersini yapar: çakışan öğe kendi kovasında kalır. Bir kovada birden çok öğe tutulabilmesi için her kova bir bağlı listenin başı olur.

14.4.1Kova başına bir bağlı liste

#define MZ 5
typedef struct dugum {
  int anahtar;
  struct dugum *sonraki;
} dugum;
dugum *kova[MZ];           /* hepsi NULL */

Tanımlar bağlı listenin alışılmış düğümüdür. struct dugum'ün iki alanı vardır: anahtar ve bir sonraki düğümün adresi. Yapı kendi tipinde bir işaretçi taşır ve bu işaretçi typedef bitmeden yazılır. Bu yüzden yapıya hem etiket adı (struct dugum) hem tip adı (dugum) verilmiştir. kova dizisi beş işaretçiden oluşur. Global olduğu için program başlarken bütün işaretçiler NULL'dır: beş kova da boş listedir.

Bellekteki görünüm açık adreslemeden farklıdır. kova dizisinin kendisi küçük ve bitişiktir: beş işaretçi, 64 bitlik bir makinede 40 bayt. Düğümler ise malloc ile tek tek alınır ve heap'in rastgele yerlerine dağılır. Test makinesinde sizeof(dugum) 16 bayt çıktı: 4 baytlık anahtar, işaretçinin 8 baytlık sınıra hizalanması için 4 baytlık boşluk ve 8 baytlık işaretçi. Her öğe için tutulan 4 baytlık anahtara 12 baytlık ek yük eklenir. malloc'un her blok için ayrıca tuttuğu yönetim bilgisi de bu hesaba dahil değildir.

bool zincir_ekle(int k) {
  int i = k % MZ;
  dugum *yeni = malloc(sizeof *yeni);
  if (yeni == NULL) return false;  /* bellek yok */
  yeni->anahtar = k;
  yeni->sonraki = kova[i];         /* başa ekle */
  kova[i] = yeni;
  return true;
}

• Satır 2: i, anahtarın kovasıdır.
• Satır 3: Yeni düğüm için bellek alınır. sizeof *yeni, yeni'nin gösterdiği tipin boyutudur, yani sizeof(dugum). Bu yazım, tip adı değişse bile doğru kalır. malloc, <stdlib.h> başlığındadır.
• Satır 4: malloc bellek bulamazsa NULL döndürür. Bu denetim atlanırsa sonraki satır NULL adresine yazmaya çalışır ve program çöker. Fonksiyon false döndürerek hatayı çağırana bildirir.
• Satır 5–7: Düğüm listenin başına eklenir. Önce yeni düğümün sonraki alanı eski başı gösterir, sonra kova yeni düğümü gösterir. Sıra önemlidir: önce kova[i] = yeni yapılsaydı eski liste kaybolurdu.

Başa ekleme, liste ne kadar uzun olursa olsun iki işaretçi ataması sürer: O(1). Listenin sonuna eklemek için bütün liste yürünmesi gerekirdi. Zincirdeki sıranın bir anlamı olmadığı için başa eklemek en ucuz seçimdir. Yalnız bu fonksiyon da aynı anahtarın ikinci kez eklenmesini engellemez. Tekrar istenmiyorsa eklemeden önce zincir_ara çağrılmalıdır; o zaman ekleme maliyeti arama maliyetine eşit olur.

14.4.2Kod izleme: zincir_ekle

Tablo beş kovalıdır, h(k) = k mod 5'tir. Başlangıçta kova 0'da 10, kova 4'te 4 vardır. Sırayla 12, 7 ve 22 eklenir; üçünün de kovası 2'dir. Tablo 14.10 her çağrıyı izler.

İlk çağrıda kova 2 boştur. Yeni düğümün sonraki alanına eski baş, yani NULL yazılır ve kova yeni düğümü gösterir. Boş bir listeye ekleme ayrı bir durum gerektirmez; aynı iki atama doğru sonucu verir. İkinci ve üçüncü çağrılarda yeni düğüm her seferinde eski başın önüne girer. Üç ekleme sonunda zincir 22 → 7 → 12 olur: son eklenen başta durur. Her çağrı bir malloc yapmıştır.

14.4.3Kod izleme: zincir_ara

dugum *zincir_ara(int k) {
  dugum *p = kova[k % MZ];
  while (p != NULL && p->anahtar != k)
    p = p->sonraki;
  return p;                 /* NULL: yok */
}

Arama, kovanın listesini baştan yürür. p listenin başından başlar. while koşulu iki şey sorar: liste bitti mi, aranan bulundu mu? İkisi de değilse p bir sonraki düğüme geçer. Koşulun sırası önemlidir. && işleci kısa devre yapar: p != NULL yanlışsa ikinci koşul hiç hesaplanmaz. Sıra ters yazılsaydı liste sonunda NULL->anahtar okunur ve program çökerdi. Döngü bitince p ya bulunan düğümü ya da NULL'ı gösterir; fonksiyon ikisini de olduğu gibi döndürür.

12, zincirin sonundadır; çünkü ilk eklenen odur. Arama üç düğüme bakar. 17'nin kovası da 2'dir (17 mod 5 = 2). Zincirin üç düğümü de 17'den farklıdır ve p sonunda NULL olur. Başarısız arama, zincirin tamamını yürümek zorundadır. Kova 1 ya da 3'e düşen bir anahtarın başarısız araması ise hiç düğüme bakmadan biter: liste boştur.

Maliyet. Arama, ev adresinin hesabı ile zincirde gezilen düğüm sayısının toplamı kadar sürer. Basit düzgün hash varsayımı altında her zincirin beklenen uzunluğu α = n/m'dir. Başarısız arama bütün zinciri yürüdüğü için ortalama α düğüme bakar; hash hesabıyla birlikte Θ(1 + α). Başarılı arama, aranan düğüme kadar yürür. Aranan öğe eklendikten sonra aynı kovaya eklenenler onun önündedir ve bunların beklenen sayısı yaklaşık α/2'dir. Bu yüzden başarılı arama ortalama 1 + α/2 düğüme bakar. İki durumda da α sabit tutulursa maliyet O(1)'dir. En kötü durumda bütün anahtarlar aynı kovaya düşer ve arama O(n) olur.

14.4.4Kod izleme: zincir_sil

Tek bağlı listeden düğüm silmek için silinecek düğümün öncülü bilinmelidir. Öncülün sonraki alanı, silinen düğümü atlayıp ondan sonrakini gösterecek biçimde değiştirilir. Bu yüzden silme yordamı iki işaretçiyle yürür.

bool zincir_sil(int k) {
  int i = k % MZ;
  dugum *p = kova[i], *onceki = NULL;
  while (p != NULL && p->anahtar != k) {
    onceki = p;
    p = p->sonraki;
  }
  if (p == NULL) return false;           /* yok */
  if (onceki == NULL) kova[i] = p->sonraki;
  else onceki->sonraki = p->sonraki;
  free(p);
  return true;
}

• Satır 3: p bakılan düğümdür, onceki onun öncülüdür. Listenin başındaki düğümün öncülü yoktur; onceki bu yüzden NULL ile başlar.
• Satır 4–7: Arama döngüsü zincir_ara'nınkiyle aynıdır. Tek farkı, p ilerlemeden önce eski değerinin onceki'ye yazılmasıdır.
• Satır 8: p NULL ise anahtar yoktur ve false döner.
• Satır 9–10: Düğüm zincirden çıkarılır. onceki NULL ise silinen düğüm listenin başıdır; kova bir sonraki düğümü gösterecek biçimde güncellenir. Değilse öncülün sonraki alanı p'nin ardılını gösterir.
• Satır 11: Düğümün belleği free ile geri verilir.

Tablo 14.12 zincir_sil(7) çağrısını izler; 7 zincirin ortasındadır.

4. adımdan sonra 7'nin düğümüne zincirden hiçbir işaretçi ulaşmaz. Bu anda free çağrılmasaydı düğüm bellekte kalır ama bir daha hiç kullanılamazdı: bellek sızıntısı. free(p)'den sonra ise p hâlâ eski adresi tutar. Bu adres artık programa ait değildir; p bir sarkan işaretçidir. p->anahtar okumak ya da p->sonraki'yi izlemek tanımsız davranıştır. Fonksiyon free'den hemen sonra döndüğü için bu tehlike burada doğmaz. Test programında silinen 7 için ikinci bir zincir_sil(7) çağrısı false döndürdü. Baştaki 22'nin silinmesi de denendi: onceki NULL kaldı, kova[2] 12'nin düğümünü gösterdi.

Zincirlemede silme, açık adreslemedeki gibi bir işaret gerektirmez. Düğüm listeden gerçekten çıkarılır ve başka hiçbir anahtarın arama yolu değişmez. Her anahtar yalnız kendi kovasının listesinde aranır; silinen düğüm başka bir kovanın aramasını kesemez. Maliyet: silme, aramayla aynı yolu yürür ve bulduktan sonra sabit iş yapar. Ortalama O(1 + α), en kötü O(n).

14.4.5Tablonun bütün belleğini geri vermek

Zincirli tablonun düğümleri malloc ile alındığı için program bitmeden ya da tablo artık gerekmediğinde hepsi geri verilmelidir. Sunumda bu yordam yoktur; aşağıdaki kod onu tamamlar.

void zincir_bosalt(void) {
  for (int i = 0; i < MZ; i++) {
    dugum *p = kova[i];
    while (p != NULL) {
      dugum *sonra = p->sonraki;  /* free'den önce sakla */
      free(p);
      p = sonra;
    }
    kova[i] = NULL;
  }
}

Dış döngü kovaları, iç döngü her kovanın zincirini dolaşır. Kodun tek inceliği sonra değişkenidir. free(p)'den sonra p->sonraki okunamaz, çünkü düğümün belleği artık programa ait değildir. Bu yüzden sonraki düğümün adresi free'den önce saklanır. Kova sonunda NULL yapılır ve tablo yeniden kullanılabilir hâle gelir. Maliyet O(n + m)'dir: her düğüm bir kez, her kova bir kez ele alınır.

Bellek sızıntısı, Windows'ta AddressSanitizer kullanılamadığı için sayaçlı bir malloc/free sarmalayıcısıyla denetlendi. Sarmalayıcı her başarılı ayırmada bir sayacı, her free'de ötekini artırır. Test programı 10, 4, 12, 7 ve 22'yi ekledi, 7 ve 22'yi sildi, sonra zincir_bosalt çağırdı. Sayaçlar 5 ayırma ve 5 bırakma gösterdi: sızıntı yoktur.

14.5Silme, yük faktörü ve yeniden boyutlandırma

Açık adreslemede ekleme ve arama kurulmuştu; silme ise ertelenmişti. Silmenin neden ayrı bir kesim gerektirdiği ilk örnekte görülür. Kesimin ikinci yarısı tablonun ne kadar dolu tutulması gerektiğini ve eşik aşılınca tablonun nasıl büyütüleceğini ele alır.

14.5.1Açık adreslemede silme tuzağı

Doğrusal yoklamalı tabloda 22, 1, 13, 11, 24 ve 33 vardır. 13 silinecektir. Akla gelen ilk çözüm, 13'ün yuvasını, yani yuva 2'yi BOS yapmaktır. Ardından ara(24) çağrılsın. 24'ün ev adresi 2'dir; 24, eklendiği sırada yuva 2 ve 3 dolu olduğu için yuva 4'e yerleşmişti. Arama ev adresine bakar, yuva 2'yi BOS bulur ve hemen −1 döndürür. Oysa 24 tablodadır.

Sorunun kaynağı, aramanın durma kuralıdır. Arama, “anahtar olsaydı ilk BOS yuvadan önce bulunurdu” varsayımıyla durur. Bu varsayım, yuvalar yalnız BOS'tan DOLU'ya geçtiği sürece doğrudur. Bir DOLU yuva yeniden BOS olunca, o yuvadan geçerek yerleşmiş bütün anahtarların yolu kesilir. Silinen yuvanın gerisinde kalan anahtarlar tablodadır ama bulunamaz.

İngilizce adı “mezar taşı”dır: yuvada artık bir öğe yaşamaz ama orada bir öğenin bulunduğu kaydedilmiştir. Silindi işareti iki kurala da uyar. Aramanın yolu kesilmez, çünkü işaretli yuva arama için doludur. Bellek boşa gitmez, çünkü işaretli yuva ekleme için boştur.

14.5.2Kod izleme: sil(13), ardından ara(24)

Silme yordamı, aramada verilen kod parçasının ikinci fonksiyonudur:

int ara(int k) {
  int i = k % M;
  for (int d = 0; d < M; d++, i = (i + 1) % M) {
    if (tablo[i].durum == BOS) return -1;
    if (tablo[i].durum == DOLU &&
        tablo[i].anahtar == k) return i;
  }
  return -1;
}
bool sil(int k) {
  int i = ara(k);
  if (i < 0) return false;
  tablo[i].durum = SILINDI;   /* silindi işareti */
  return true;
}

sil önce ara ile anahtarın yuvasını bulur. Anahtar yoksa false döner. Varsa yuvanın durumunu SILINDI yapar. Anahtar alanına dokunulmaz; eski değer yuvada kalır. Bu bir sorun yaratmaz, çünkü ara bir anahtarı ancak durumu DOLU ise kabul eder. Tablo 14.13 silmeyi ve ardından yapılan aramayı izler.

ara(24) yuva 2'deki silindi işaretinde durmaz; iki if koşulu da yanlış çıkar ve döngü ilerler. Arama, silmeden önceki gibi üç yoklamada 24'ü bulur. Test programı aynı sırayı çalıştırdı: sil(13) 1 (true), sonraki ara(24) 4, ara(13) −1 ve ikinci bir sil(13) 0 (false) döndürdü. Yuva 2 elle BOS yapıldığında ise ara(24) −1 döndürdü; tuzak gerçekten oluştu.

Ekleme ve tekrar eden anahtar. ekle, SILINDI yuvayı yeniden kullanır. Bu, sunumun alıştırmasında sorulan bir tehlike doğurur. Tabloda 13 silinmiş, 24 yuva 4'te dururken ekle(24) çağrılsın. ekle ev adresi 2'ye bakar, yuvayı DOLU değil diye kabul eder ve 24'ü oraya yazar. Tabloda artık iki tane 24 vardır: yuva 2'de ve yuva 4'te. Test programında bu çağrı gerçekten 2 döndürdü ve tablo 22, 1, 24, 11, 24, 33 oldu. Daha sonra sil(24) yalnız ilk kopyayı siler; ikinci kopya tabloda kalır ve ara(24) silinmiş bir anahtarı bulmaya devam eder. Çözüm, eklemeden önce aramaktır:

int ekle_tekil(int k) {        /* anahtar zaten varsa yeniden eklemez */
  int i = ara(k);
  if (i >= 0) return i;        /* var: yerini döndür */
  return ekle(k);              /* ilk BOS ya da SILINDI yuvaya yaz */
}

ekle_tekil, anahtarın yoklama dizisinin tamamını ara ile tarar. Anahtar varsa onun yerini döndürür ve yeni kopya yazmaz. Yoksa ekle, dizideki ilk BOS ya da SILINDI yuvaya yazar. Test programında 13 silindikten sonra ekle_tekil(24) 4 döndürdü ve tablo değişmedi; ekle_tekil(46) ise 46'yı silindi işaretli yuva 2'ye yazdı. Bu sürüm, silindi işaretlerinin yerini geri kazanır ve tekrar eden anahtara izin vermez. Bedeli, her eklemede bir aramadır.

Silindi işaretinin de bir maliyeti vardır. İşaretli yuvalar arama için dolu sayıldığı için aramaları uzatır. Çok sayıda ekleme ve silme yapılan bir tabloda, gerçek öğe sayısı küçük olsa bile yuvaların büyük kısmı zamanla SILINDI olabilir. Bu durumda başarısız aramalar neredeyse bütün tabloyu tarar. Çare, tabloyu belirli aralıklarla yeniden kurmaktır: bütün DOLU öğeler yeni ve temiz bir tabloya yeniden eklenir, işaretler atılır. Bu işlem yeniden boyutlandırmayla aynıdır. Zincirlemede bu sorun hiç doğmaz.

14.5.3Yük faktörü ve beklenen yoklama sayısı

Bütün çakışma çözümlerinde maliyet, tablonun doluluğuyla artar. Yük faktörü α = n/m bu doluluğun ölçüsüdür. Hash tablolarının kuramsal analizi, basit düzgün hash varsayımı altında beklenen yoklama sayısını α'nın fonksiyonu olarak verir. Tablo 14.14 dört α değeri için sonuçları özetler.

Tablodaki sayılar şu formüllerden gelir:

• Zincirleme: başarılı arama 1 + α/2, başarısız arama 1 + α (ilk 1, kovaya erişimdir). İkisi de Θ(1 + α).
• Doğrusal yoklama (Knuth): başarılı arama ½ (1 + 1/(1 − α)), başarısız arama ½ (1 + 1/(1 − α)²).
• Düzgün açık adresleme (CLRS): başarılı arama (1/α) · ln(1/(1 − α)), başarısız arama 1/(1 − α). Çift hash bu ideale çok yakın davranır.

Başarısız aramanın 1/(1 − α) formülünün arkasında basit bir düşünce vardır. Her yoklama, rastgele bir yuvaya bakar ve bu yuva α olasılıkla doludur. İlk yoklama her zaman yapılır. İkinci yoklamaya ilk yuva doluysa geçilir: olasılık α. Üçüncüye ilk iki yuva doluysa geçilir: olasılık yaklaşık α². Beklenen toplam 1 + α + α² + … = 1/(1 − α) geometrik toplamıdır. α = 0,9 iken bu 10 eder: on yuvadan biri boştur ve boş yuvaya rastlamak ortalama on deneme sürer.

Formüllerin ikinci dersi, maliyetin α ile doğrusal değil, 1/(1 − α) ile büyümesidir. α 0,5'ten 0,75'e çıkınca doğrusal yoklamada başarısız arama 2,5'ten 8,5'e, 0,9'da 50,5'e çıkar. Zincirlemede ise artış yumuşaktır: α = 0,9'da başarısız arama 1,9 yoklamadır ve α 1'i aştığında da tablo çalışmaya devam eder.

Formüller bir varsayıma dayandığı için ölçümle denetlendi. 100 003 yuvalı (asal) bir tabloya, sabit tohumla üretilen sözde rastgele anahtarlar eklendi. Her α için başarılı aramada ortalama yoklama sayısı eklenen bütün anahtarlar üzerinden, başarısız aramada ise tabloda olmayan 20 000 anahtar üzerinden hesaplandı. Çift hashte h₂(k) = 1 + (k mod (m − 2)) kullanıldı. Tablo 14.15 sonuçları formüllerle yan yana verir. Anahtarlar sabit tohumla üretildiği için sayılar makineden bağımsızdır; yalnız süre ölçülmemiştir.

Ölçümler formüllerle uyumludur; sapmalar %4'ün altındadır. En büyük sapmalar doğrusal yoklamada, α = 0,75 ve 0,9'da görülür (%2–4). Yüksek dolulukta birkaç uzun blok ortalamayı belirgin biçimde etkiler. Çift hashin değerleri, düzgün açık adresleme formülünü üç basamağa kadar tutturur.

Kanıt. Zincirlemede beklenen maliyet Θ(1 + α)'dır; α sabitle sınırlıysa bu da sabittir. Düzgün açık adreslemede başarısız arama ve ekleme en çok 1/(1 − α) ≤ 1/(1 − α₀), başarılı arama bundan da azdır. Sağ taraf n'ye bağlı değildir. Silme, bir arama ve sabit iş olduğu için aynı sınırı taşır. ∎

Pratikte kullanılan eşikler şöyledir: açık adreslemede α ≤ 0,5–0,7, zincirlemede α ≤ 1 civarı. Karesel yoklamada teorem gereği eşik en çok 0,5 olmalıdır. Eşik aşılınca tablo büyütülür.

14.5.4Yeniden boyutlandırma

Tablo boyutu sabit bir makroyla verilirse yük faktörü öğe sayısıyla birlikte büyür. Öğe sayısı önceden bilinmiyorsa tablonun dizisi dinamik olmalı ve eşik aşılınca büyütülmelidir.

typedef struct {
  yuva *a;      /* m yuvalık dinamik dizi */
  int m, n;     /* boyut, dolu yuva sayısı */
} Tablo;
/* ekledikten sonra: */
if (2 * t->n > t->m)             /* α > 1/2 */
  yeniden_boyutla(t, sonraki_asal(2 * t->m));

Tablo yapısı üç alan taşır: yuva dizisinin adresi, yuva sayısı m ve dolu yuva sayısı n. Dizi artık malloc ya da calloc ile alınır ve boyutu çalışma sırasında değişebilir. Kodun ikinci kısmı, her eklemeden sonra çalışacak denetimdir. 2 * t->n > t->m koşulu α > 1/2 demektir; kesirli sayı kullanmamak için iki taraf 2m ile çarpılmıştır. Eşik aşılınca tablo, eski boyutun iki katından küçük olmayan ilk asal boyuta büyütülür. Asal seçim bölme yöntemi ve karesel yoklama için gereklidir.

Sunumdaki parça, iki yardımcı fonksiyonun var olduğunu varsayar. Test programı için yazılan sürümleri şunlardır:

int sonraki_asal(int x) {        /* x'ten küçük olmayan ilk asal */
  for (;; x++) {
    int asal = x >= 2;
    for (int d = 2; d * d <= x && asal; d++)
      if (x % d == 0) asal = 0;
    if (asal) return x;
  }
}

int tablo_ekle(Tablo *t, int k) {  /* doğrusal yoklama, m = t->m */
  int i = k % t->m;
  for (int d = 0; d < t->m; d++, i = (i + 1) % t->m) {
    if (t->a[i].durum != DOLU) {
      t->a[i].anahtar = k;
      t->a[i].durum = DOLU;
      t->n++;
      return i;
    }
  }
  return -1;
}

sonraki_asal, x'ten başlayarak ilk asalı bulur. Her adayı √x'e kadar olan bölenlerle dener; d * d <= x koşulu karekök hesaplamadan bu sınırı uygular. tablo_ekle, açık adreslemedeki ekle'nin dinamik tablo sürümüdür. Tek farkları, boyutu M makrosundan değil t->m alanından almak ve dolu yuva sayacını artırmaktır. 5'ten başlayan ve her seferinde iki katın ilk asalını alan boyut dizisi 5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, … biçiminde ilerler.

Neden yeniden hash? Büyütmenin akla gelen ilk yolu, eski diziyi yeni dizinin başına kopyalamaktır. Bu yanlıştır. Bir öğenin yuvası k mod m'ye bağlıdır ve m değişince ev adresi de değişir. 12, 5 yuvalı tabloda 12 mod 5 = 2'dedir; 11 yuvalı tabloda ev adresi 12 mod 11 = 1'dir. Yuva 2'ye kopyalanan 12, yeni tabloda ara(12) ile bulunamaz: arama yuva 1'e bakar, boş bulur ve durur. Her öğe yeni tabloya baştan eklenmelidir. Bu işleme yeniden hash'leme (rehashing) denir.

bool yeniden_boyutla(Tablo *t, int yeni_m) {
  yuva *eski = t->a;
  int eski_m = t->m;
  yuva *a = calloc(yeni_m, sizeof *a);  /* BOS */
  if (a == NULL) return false;
  t->a = a; t->m = yeni_m; t->n = 0;
  for (int i = 0; i < eski_m; i++)
    if (eski[i].durum == DOLU)
      tablo_ekle(t, eski[i].anahtar);
  free(eski);
  return true;
}

• Satır 2–3: Eski dizinin adresi ve boyutu yerel değişkenlerde saklanır. Tablo yapısı birazdan yeni diziye bağlanacağı için eski dizi ancak bu kopyalar üzerinden okunabilir.
• Satır 4–5: Yeni dizi calloc ile alınır. calloc, malloc'tan farklı olarak belleği sıfırlar; BOS = 0 olduğu için bütün yuvalar boş başlar. Bellek alınamazsa fonksiyon false döndürür. Bu durumda tablo hiç değişmemiştir: eski dizi yerindedir, sadece büyütülememiştir.
• Satır 6: Tablo yeni diziye bağlanır ve n sıfırlanır; tablo_ekle her eklemede n'yi yeniden artıracaktır.
• Satır 7–9: Eski dizinin her yuvasına bakılır. Yalnız DOLU yuvalar yeni tabloya eklenir. BOS ve SILINDI yuvalar atlanır; böylece silindi işaretleri de temizlenir.
• Satır 10: Eski dizi free edilir. Bu satır unutulursa her büyütme eski diziyi sızdırır.

Fonksiyonun bir inceliği tablo_ekle ile ilişkisidir. tablo_ekle büyütme denetimini kendisi yapsaydı, yeniden hash'leme sırasında tekrar büyütme tetiklenebilirdi. Yeni boyut eski boyutun iki katından büyük ve n sıfırdan başladığı için bu kodda eşik aşılmaz. Yine de denetimin tablo_ekle'nin dışında, çağıran tarafta durması daha güvenlidir. Sunumdaki düzen de budur.

14.5.5Kod izleme: yeniden_boyutla

5 yuvalı tabloya 7, 12 ve 3 eklenmiştir. Doğrusal yoklamayla 7 yuva 2'ye, 12 yuva 3'e (ev adresi 2 dolu), 3 yuva 4'e (ev adresi 3 dolu) yerleşmiştir. n = 3, m = 5, α = 0,6 > 0,5: tablo büyütülecektir. Yeni boyut sonraki_asal(10) = 11'dir. Tablo 14.16 izlemeyi verir.

Eski tabloda üç öğe bitişik bir blok oluşturuyordu ve 12 ile 3 ev adreslerinden kaymıştı. Yeni tabloda üçü de kendi ev adresindedir; çakışma yoktur. Büyütme, yük faktörünü düşürmenin yanında kümeleri de dağıtmıştır. Test programı aynı sonucu iki yoldan aldı: yeniden_boyutla doğrudan çağrılınca ve 7, 12, 3 eşik denetimli eklemeyle sırayla eklenince. İkinci yolda büyütme tam üçüncü eklemeden sonra tetiklendi. Sayaçlı sarmalayıcı dört ayırma (iki başlangıç dizisi ve iki yeni dizi) ve dört bırakma gösterdi.

Tek büyütmenin maliyeti. calloc yeni diziyi sıfırlarken m' yuvaya dokunur, döngü eski m yuvayı dolaşır ve n öğeyi yeniden ekler. Toplam O(n + m)'dir. Tek bir ekleme bu yüzden bazen çok pahalı olur.

Kanıt. Son büyütme, öğe sayısı n_s ≤ n iken yapılmış olsun ve bu büyütmede n_s öğe yeniden eklensin. Bir önceki büyütme, en geç tablo boyutu bunun yarısıyken tetiklenmiştir; o anda en çok n_s/2 öğe vardı. Ondan öncekinde en çok n_s/4, ve bu böyle sürer. Toplam yeniden ekleme sayısı en çok n_s + n_s/2 + n_s/4 + … < 2n_s ≤ 2n'dir. Her büyütmenin calloc maliyeti de tablo boyutuyla orantılıdır ve boyutlar da her seferinde en az iki katına çıktığı için aynı geometrik toplamla sınırlıdır. n eklemenin toplam maliyeti O(n), ekleme başına O(1) olur. ∎

Bu türden bir analize amortize analiz (amortized analysis) denir: tek tek işlemlerin bazıları pahalı olsa da bir işlem dizisinin toplam maliyeti işlem sayısına bölünür. Teorem bir ölçümle denetlendi. 5 yuvadan başlayan tabloya bir milyon öğe eklendi ve α > 1/2 olduğunda tablo bir sonraki asala büyütüldü. 19 büyütme oldu ve son boyut 3 292 489'a çıktı. Toplam yeniden ekleme sayısı 1 646 169'du, yani öğe başına 1,65: teoremdeki 2'nin altında. Büyütmelerde alınan yuvaların toplamı öğe başına 6,6 çıktı.

14.6Zincirleme mi, açık adresleme mi?

İki çakışma çözümü aynı sözlük işlemlerini sunar ve ikisi de α sabitken ortalama O(1)'dir. Aralarındaki seçim, verinin ve uygulamanın özelliklerine bağlıdır. Tablo 14.17 farkları yan yana koyar.

Zincirlemenin en güçlü yanı esnekliğidir. Öğe sayısı önceden bilinmese bile tablo çalışmaya devam eder; yalnız zincirler uzar. Silme, bağlı listeden düğüm çıkarmak kadar basittir ve tablonun geri kalanını etkilemez. Kötü bir hash fonksiyonu bazı zincirleri uzatır, ama zarar o kovalarla sınırlı kalır. Bedeli bellek ve önbellektir. Test makinesinde 4 baytlık bir anahtar için 16 baytlık düğüm alındı. Düğümler heap'in farklı yerlerinde olduğu için zincirde her adım işlemcinin yeni bir bellek bloğu getirmesini gerektirebilir.

Açık adresleme bu iki noktada üstündür. Bütün öğeler tek bir dizide durur, işaretçi yoktur, malloc yalnız tablo büyütülürken çağrılır. Doğrusal yoklamanın ardışık yoklamaları aynı önbellek bloğuna düşer. Bedeli, yük faktörüne duyarlılık ve silmenin karmaşıklığıdır. α 0,5 civarında tutulursa tablonun yarısı boş kalır; zincirlemenin düğüm yüküyle karşılaştırıldığında bu çoğu zaman yine de ucuzdur.

Pratik bir kural şöyle özetlenebilir. Öğe sayısı öngörülemiyorsa, çok silme yapılıyorsa ya da hash fonksiyonunun kalitesinden emin olunamıyorsa zincirleme seçilir. Bellek ve hız kritikse, silme seyrekse ve yük faktörü düşük tutulabiliyorsa açık adresleme seçilir. Gerçek kitaplıklar iki yolu da kullanır. Java'nın HashMap'i zincirlemeye dayanır; Python'un dict'i açık adreslemeye dayanır.

14.7Karmaşıklık özeti

Tablo 14.18 hash tablosu işlemlerinin maliyetini toplar. Ortalama sütunu, yük faktörünün sabit tutulduğunu ve hash fonksiyonunun anahtarları düzgün dağıttığını varsayar.

Son iki satır, hash tablosunun dengeli arama ağacına göre zayıf kaldığı yerdir. Arama ağacı en küçük öğeyi O(lg n)'de bulur ve öğeleri O(n)'de sıralı gezer. Hash tablosunda öğeler kovalara dağınık durduğu için en küçük öğe için bütün kovalara bakılır. Sıralı gezinme için önce bütün öğeler bir diziye toplanır, sonra sıralanır.

En kötü durum yalnız şanssızlıkla gelmez; kasıtlı olarak da üretilebilir. Hash fonksiyonu herkesçe biliniyorsa bir saldırgan, hepsi aynı kovaya düşen binlerce anahtar hazırlayabilir. Örneğin bir web sunucusu istek parametrelerini hash tablosunda tutuyorsa, aynı kovaya düşen parametre adlarıyla dolu tek bir istek, sunucuyu O(n²) işe sokar. Bu saldırıya hash taşkını (hash flooding) denir. Önlem, hash fonksiyonunu program başlarken rastgele seçmektir. Fonksiyon, önceden tanımlanmış bir aileden rastgele seçilir. Saldırgan hangi fonksiyonun seçildiğini bilmediği için çakışan anahtar hazırlayamaz. Ailenin herhangi iki farklı anahtarı çakıştırma olasılığı en çok 1/m ise aileye evrensel denir. Bu yönteme evrensel hash (universal hashing) adı verilir (CLRS, Kesim 11.3.3). Python ve Rust gibi dillerin dizgi hash'leri bu nedenle her çalıştırmada rastgele bir anahtarla başlar.

14.8Sık yapılan hatalar

Hash tablosu kodlarında en sık görülen altı hata şunlardır. Her biri bu notta bir örnekle karşılaşılan durumlardır.

1. Negatif anahtarda k % m'nin negatif çıkması. C'de -7 % 11 −7'dir. Negatif indis dizinin dışına yazar. Anahtar unsigned tutulmalı ya da kalan h_guvenli'deki gibi düzeltilmelidir.
2. m'yi 10 ya da 2'nin kuvveti seçmek. Bölme yöntemiyle bu seçim yalnız son basamaklara ya da son bitlere bakar. 10'un katları m = 10'da tek kovaya toplanır. m, 2'nin kuvvetlerinden uzak bir asal olmalıdır.
3. Açık adreslemede silinen yuvayı BOS yapmak. Silinen yuvadan geçerek yerleşmiş anahtarların aramaları yarıda kalır. Yuva SILINDI ile işaretlenmelidir.
4. Tablo doluyken sonsuz döngüye girmek. Yoklama döngüsü boş yuva bulana kadar dönerse dolu tabloda hiç durmaz. Deneme sayısı m ile sınırlanmalıdır. Karesel yoklamada m denemede bile bütün yuvalar yoklanmaz; tablo yarıdan fazla doldurulmamalıdır.
5. malloc sonucunu denetlememek; free sonrası düğümü kullanmak. NULL dönen malloc'un sonucuna yazmak programı çökertir. Silinen düğümün sonraki alanını free'den sonra okumak tanımsız davranıştır; adres önce saklanmalıdır.
6. Yeniden boyutlandırmada öğeleri eski indisleriyle kopyalamak. Ev adresi m'ye bağlıdır. Eski konumuna kopyalanan öğe yeni tabloda bulunamaz. Her öğe yeni tabloya yeniden eklenmelidir.

14.9Alıştırmalar ve çözümleri

Sunumdaki altı alıştırmanın çözümleri aşağıda ara adımlarıyla verilmiştir. Bütün sonuçlar bir doğrulama betiğiyle yeniden hesaplandı.

14.9.1Doğrusal yoklamayla küçük tablo

Soru. m = 7, h(k) = k mod 7, doğrusal yoklama: 10, 17, 24, 3 sırayla eklenince tablo ne olur?

Çözüm. Dört anahtarın ev adresleri 10 mod 7 = 3, 17 mod 7 = 3, 24 mod 7 = 3 ve 3 mod 7 = 3'tür: hepsi eş anlamlıdır. 10, yuva 3'e yazılır. 17 için yuva 3 doludur, yuva 4'e yazılır. 24 için yuva 3 ve 4 doludur, yuva 5'e yazılır. 3 için yuva 3, 4 ve 5 doludur, yuva 6'ya yazılır. Son tablo: yuva 3–6 = 10, 17, 24, 3. Yoklama sayıları 1, 2, 3 ve 4'tür; toplam 10.

14.9.2Aynı anahtarlar zincirlemeyle

Soru. Aynı anahtarlar zincirlemeyle (başa ekleme) yerleştirilirse en uzun zincir kaç düğümdür?

Çözüm. Dört anahtarın hepsi kova 3'e düşer. Başa ekleme son ekleneni başa koyduğu için zincir 3 → 24 → 17 → 10 olur: dört düğüm. Öteki altı kova boştur. Hash fonksiyonu bu dört anahtarı hiç dağıtamamıştır; 7'nin katlarından 3 fazla olan sayılar için k mod 7 kötü bir seçimdir. Zincirleme bu kötü dağılımı tek bir kovaya hapseder, ama o kovadaki arama yine dört düğüm sürer.

14.9.3Karesel yoklama dizisi

Soru. m = 11 ve karesel yoklamada 0, 1, 4, 9, 16, 25 (mod 11) yoklama dizisini yazmak.

Çözüm. İlk dört değer 11'den küçüktür ve olduğu gibi kalır: 0, 1, 4, 9. 16 mod 11 = 5 ve 25 mod 11 = 3'tür. Dizi 0, 1, 4, 9, 5, 3'tür. Altı değerin hepsi farklıdır; bu, karesel yoklama teoremindeki ⌈11/2⌉ = 6 sınırıyla uyumludur. Yedinci deneme 36 mod 11 = 3'tür ve tekrar başlar.

14.9.4Dolu tabloda başarısız arama

Soru. α = 0,9 olan doğrusal yoklamalı tabloda başarısız arama kaç yoklama bekler?

Çözüm. Knuth'un formülüyle ½ (1 + 1/(1 − 0,9)²) = ½ (1 + 1/0,01) = ½ · 101 = 50,5 yoklama. Ölçümde 51,1 bulundu. Aynı doluluktaki çift hash için beklenen değer 10, zincirleme için 1,9'dur. α → 1 iken doğrusal yoklamanın maliyeti patlar.

14.9.5Toplama ve polinom hash'i

Soru. “ab” ve “ba” için toplama hash'ini ve 31 tabanlı polinom hash'ini (mod 11) hesaplamak.

Çözüm. “a” = 97, “b” = 98'dir. Toplama: 97 + 98 = 195 ve 195 mod 11 = 8; iki dizgi de 8. kovaya düşer. Polinom: “ab” için 97 · 31 + 98 = 3105 ve 3105 mod 11 = 3; “ba” için 98 · 31 + 97 = 3135 ve 3135 mod 11 = 0. Polinom hash'i iki anagramı ayırır. dizgi_hash aynı değerleri ara adımlarda mod alarak verir: “ab” için önce 97 mod 11 = 9, sonra (9 · 31 + 98) mod 11 = 377 mod 11 = 3.

14.9.6Eklemeden önce aramak

Soru. Açık adreslemede ekle, SILINDI yuvaya yazmadan önce neden ara çağırmalıdır?

Çözüm. Aynı anahtar, silindi işaretinden sonraki bir yuvada zaten bulunabilir. Silme kesimindeki örnekte 13 silindikten sonra 24, yuva 4'te durur; 24'ün yoklama dizisindeki ilk yuva ise silindi işaretli yuva 2'dir. Denetimsiz ekle(24), 24'ü yuva 2'ye ikinci kez yazar. Önce ara çağrılırsa 24 yuva 4'te bulunur ve ekleme yapılmaz. ekle_tekil fonksiyonu bunu yapar.

14.10Özet

• Hash tablosu anahtarı karşılaştırmaz, anahtardan konumu hesaplar. Arama, ekleme ve silme ortalama O(1), en kötü O(n)'dir. Bedeli sıra bilgisinin kaybıdır: sıralı gezinme, en küçük/en büyük ve aralık sorguları ucuz değildir.
• Doğrudan adresleme anahtarı indis olarak kullanır; evren büyükse kurulamaz. Hash fonksiyonu h: U → {0, …, m − 1} anahtarı küçük bir aralığa indirir. m < |U| olduğundan çakışma kaçınılmazdır; doğum günü paradoksu çakışmanın yaklaşık √m anahtardan sonra beklendiğini gösterir.
• İyi bir hash fonksiyonu hızlı, düzgün dağıtan, bütün bitleri kullanan ve deterministiktir. Bölme yönteminde m, 2'nin kuvvetlerinden uzak bir asal seçilir. Çarpma yönteminde A ≈ 0,618 ve m = 2^p kullanılabilir. Uzun anahtarlar katlanır; dizgiler 31 tabanlı polinom hash'iyle Horner kuralına göre hesaplanır. C'de negatif % sonucuna dikkat edilmelidir.
• Açık adreslemede bütün öğeler tablodadır ve α ≤ 1'dir. Doğrusal yoklama birincil kümelenme, karesel yoklama ikincil kümelenme yaratır; çift hash anahtara özgü adım boyuyla kümelenmeyi en aza indirir. Karesel yoklamada m asal ve α ≤ 1/2 olmalı, çift hashte h₂ sıfır olmamalı ve m ile aralarında asal olmalıdır.
• Açık adreslemede silinen yuva BOS yapılmaz, silindi işaretiyle işaretlenir. Arama işaretten geçer, ekleme işaretli yuvayı yeniden kullanır; tekrar eden anahtarı önlemek için eklemeden önce aranır.
• Zincirlemede her kova bir bağlı listenin başıdır. Başa ekleme O(1), arama Θ(1 + α)'dır. Silme bağlı listeden düğüm çıkarmaktır; öncül işaretçisi ve baştaki düğüm durumu dikkat ister. Bütün düğümler sonunda free edilmelidir.
• Beklenen yoklama sayısı 1/(1 − α) mertebesinde büyür. Eşik aşılınca tablo iki katının ilk asalına büyütülür ve bütün öğeler yeniden hash'lenir; amortize maliyet ekleme başına O(1)'dir.
• En kötü durum kötü niyetli girdilerle tetiklenebilir; evrensel hash, fonksiyonu çalışma anında rastgele seçerek buna karşı korur.

14.11Kavram listesi

• hash tablosu hash table
• hash fonksiyonu hash function
• doğrudan adresleme direct addressing
• kova bucket
• çakışma collision
• yük faktörü load factor
• sözlük dictionary
• soyut veri tipi abstract data type
• bölme yöntemi division method
• çarpma yöntemi multiplication method
• katlama folding
• açık adresleme open addressing
• yoklama probe
• doğrusal yoklama linear probing
• karesel yoklama quadratic probing
• çift hash double hashing
• kümelenme primary clustering
• ayrı zincirleme separate chaining
• silindi işareti tombstone
• yeniden boyutlandırma rehashing
• amortize analiz amortized analysis
• önbellek cache
• sarkan işaretçi dangling pointer
• bellek sızıntısı memory leak

14.12Kendini Dene

1. m = 11, h(k) = k mod 11 ve doğrusal yoklamayla 20, 31, 42, 9, 53 sırayla ekleniyor. Son tablo nedir? 53 kaç yoklamada yerleşir?

   Cevap

   Beş anahtarın hepsinin ev adresi 9'dur. 20 → 9, 31 → 10, 42 → 9, 10 dolu, başa dönülür → 0, 9 → 9, 10, 0 dolu → 1, 53 → 9, 10, 0, 1 dolu → 2. Tablo: yuva 0 = 42, 1 = 9, 2 = 53, 9 = 20, 10 = 31. 53 beş yoklamada yerleşir.

2. Aynı anahtarlar m = 11 kovalı zincirli tabloya başa eklemeyle konuyor. Kova 9'un zinciri nasıldır? zincir_ara(20) kaç düğüme bakar?

   Cevap

   Zincir 53 → 9 → 42 → 31 → 20'dir; son eklenen baştadır. 20 zincirin sonunda olduğu için arama beş düğüme bakar.

3. 16, 32, 48 ve 64 anahtarları m = 16 ve m = 17 ile bölme yöntemine sokuluyor. Ev adresleri nedir? Sonuç neyi gösterir?

   Cevap

   m = 16 ile dördü de 0'a düşer, çünkü k mod 16 yalnız son dört biti alır ve bu anahtarların son dört biti sıfırdır. m = 17 ile ev adresleri 16, 15, 14 ve 13'tür; dördü de farklıdır. 2'nin kuvveti olan tablo boyutu örüntülü veride kümelenme yaratır, asal boyut yaratmaz.

4. dizgi_hash("ali", 7) kaç döndürür? (a = 97, l = 108, i = 105)

   Cevap

   1. tur: 97 mod 7 = 6. 2. tur: 6 · 31 + 108 = 294, 294 mod 7 = 0. 3. tur: 0 · 31 + 105 = 105, 105 mod 7 = 0. Sonuç 0.

5. Doğrusal yoklamalı tabloda yuva 0–5 = 22, 1, 13, 11, 24, 33'tür. sil(22) çağrılıyor. Ardından ara(33) kaç yoklama yapar? Yuva 0 BOS yapılsaydı ne olurdu?

   Cevap

   Yuva 0 SILINDI olur. ara(33) yuva 0'daki işaretten geçer, 1, 2, 3 ve 4'te farklı anahtarlar bulur ve yuva 5'te 33'ü bulur: 6 yoklama. Yuva 0 BOS yapılsaydı arama ilk yoklamada durur ve −1 döndürürdü; 33 tabloda olduğu hâlde bulunamazdı.

6. Zincirli bir tabloda n = 2000, m = 1000; açık adresli bir tabloda ise α = 0,8 ve doğrusal yoklama kullanılıyor. Her birinde başarılı ve başarısız arama ortalama kaç yoklama sürer?

   Cevap

   Zincirlemede α = 2: başarılı 1 + α/2 = 2, başarısız 1 + α = 3. Doğrusal yoklamada başarılı ½ (1 + 1/0,2) = 3, başarısız ½ (1 + 1/0,04) = 13. Zincirli tablo iki kat dolu olduğu hâlde daha hızlıdır.

7. 11 yuvalı boş bir tabloya sırayla anahtar ekleniyor; her eklemeden sonra 2 * n > m ise tablo sonraki_asal(2 * m) boyutuna büyütülüyor. İlk iki büyütme kaçıncı eklemeden sonra olur ve yeni boyutlar nedir?

   Cevap

   İlk büyütme 6. eklemeden sonra olur (12 > 11); yeni boyut sonraki_asal(22) = 23. İkincisi 12. eklemeden sonra olur (24 > 23); yeni boyut sonraki_asal(46) = 47.

8. Çift hash m = 10 ile kullanılıyor ve bir anahtar için h₁ = 5, h₂ = 6. Yoklama dizisi nedir ve neden sorunludur?

   Cevap

   Dizi (5 + 6i) mod 10: 5, 1, 7, 3, 9, 5, 1, … Yalnız beş yuva yoklanır, çünkü 6 ile 10'un ortak böleni 2'dir. Tabloda boş yer olsa bile bu anahtar onu bulamayabilir. m asal seçilirse sorun ortadan kalkar.

9. Kova 2'nin zinciri 22 → 7 → 12 iken zincir_sil(22) çağrılıyor. Döngü kaç tur döner, hangi işaretçi güncellenir?

   Cevap

   Döngü hiç dönmez: p ilk düğümdür ve anahtarı 22'dir. onceki NULL kalır; bu yüzden kova[2] = p->sonraki yapılır ve kova artık 7'nin düğümünü gösterir. Ardından 22'nin düğümü free edilir; zincir 7 → 12 olur.

10. Anahtar int k = -15 ve m = 11. C'de k % m kaçtır? Doğru ev adresi nedir?

    Cevap

    C'de -15 % 11 −4'tür; bu indis dizinin dışındadır. Doğru ev adresi −4 + 11 = 7'dir (h_guvenli(-15, 11)).

14.13İleri okuma

• E. Horowitz, S. Sahni ve S. Anderson-Freed, Fundamentals of Data Structures in C (2. baskı), Bölüm 8: statik ve dinamik hash, bölme, orta-kare ve katlama yöntemleri, doğrusal ve karesel yoklama ile zincirlemenin bu notun izlediği kaynağıdır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (3. baskı), Bölüm 11: doğrudan adresleme, zincirleme analizi, bölme ve çarpma yöntemleri, evrensel hash ve açık adreslemenin beklenen yoklama sayısının kanıtlarını verir.
• R. Sedgewick, Algorithms in C, Parts 1–4 (3. baskı), Bölüm 14: hash fonksiyonları, zincirleme, doğrusal yoklama ve çift hashi C kodlarıyla ve deneysel karşılaştırmalarla işler.
• D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2. baskı), Kesim 6.4: doğrusal yoklamanın ½ (1 + 1/(1 − α)) ve ½ (1 + 1/(1 − α)²) formüllerinin özgün çözümlemesini ve çarpma yöntemindeki altın oran seçiminin gerekçesini içerir.

14.14Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Bölüm 8 (Hashing).
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, Bölüm 11 (Hash Tables).
3. R. Sedgewick, Algorithms in C, Parts 1–4, 3. baskı, Addison-Wesley, Bölüm 14 (Hashing).
4. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2. baskı, Addison-Wesley, 1998, Kesim 6.4.

İlgili sayfalar: Bölüm 14 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.