Bölüm 12: Eşlemeler ve Hash Tabloları

12.1Eşleme ve hash fikri

Dizi ve bağlı liste gibi yapılarda öğelere ya konumlarıyla (dizinin 5. hücresi) ya da sırayla (listenin başından itibaren) ulaştık. Gündelik hayatta ise bilgiyi çoğu zaman bir ad ile ararız. Öğrenci işleri bir öğrenciyi okul numarasıyla bulur. Sözlük bir kelimenin anlamını kelimenin kendisiyle verir. Derleyici bir değişkenin tipini değişkenin adına bakarak öğrenir. Bu kesim, bu tür aramaları tanımlayan eşleme ADT'sini ve onu hızlı yapmanın ardındaki fikri anlatır.

12.1.1Eşleme (Map)

Bir telefon rehberini düşünelim. Rehberdeki her satırda bir isim ve bir telefon numarası vardır. İsim satırı tanımlar; numara ise o isme bağlı bilgidir. “Ayşe Demir'in telefonu nedir?” sorusunu sorarken elimizde isim vardır, aradığımız şey numaradır. Bu düzende isme anahtar (key), numaraya değer (value) denir.

Anahtarların tekil olması tanımın en önemli parçasıdır. Rehberde aynı isim iki kez geçerse “bu ismin numarası” sorusunun tek bir cevabı kalmaz. Eşleme bu belirsizliğe izin vermez: aynı anahtarla ikinci kez ekleme yapılırsa yeni bir çift oluşmaz, var olan çiftin değeri değişir. Değerler için böyle bir kısıt yoktur. İki farklı kişinin numarası aynı olabilir; iki farklı öğrencinin notu da aynı olabilir.

Şekil 12.1 eşlemeyi bir rehber örneği üzerinde gösterir. Üç isim, ortadaki bir fonksiyondan geçerek bir tablonun 02, 01 ve 14 numaralı yuvalarına gönderilir. Numaralar da bu yuvalarda saklanır. Şekildeki ortadaki kutu, bu bölümün asıl konusu olan hash fonksiyonudur. Görevi, bir ismi tablodaki bir yuva numarasına çevirmektir.

Eşlemenin bir soyut veri tipi olduğunu vurgulamak gerekir. Soyut veri tipi (abstract data type, kısaca ADT) bir yapının ne yaptığını söyler: hangi işlemler vardır ve her işlem neyi değiştirir. Nasıl yapıldığını söylemez. Eşleme ADT'si sırasız bir diziyle, sıralı bir diziyle, bir arama ağacıyla ya da bir hash tablosuyla gerçeklenebilir. Bu gerçeklemelerin hepsi aynı soruları cevaplar; fark, cevabın ne kadar sürede geldiğindedir.

Hash tablosu, eşlemenin en yaygın gerçeklemesidir. Nedeni basittir: ekleme, arama ve silme hash tablosunda ortalama O(1) sürer. Tabloda bin öğe de olsa bir milyon öğe de olsa bir anahtarın değerine ortalama olarak aynı sürede ulaşılır. Sıralı dizide ikili arama bile O(log n) karşılaştırma yapar. Bu bölümün geri kalanı, bu “ortalama sabit süre”nin nereden geldiğini ve hangi koşullarda bozulduğunu anlatır.

12.1.2Eşleme ADT'sinin temel işlemleri

Eşleme ADT'si dört temel işlemle tanımlanır: ekleme, arama, silme ve güncelleme. Java'nın java.util.Map arayüzü bu işlemleri put, get ve remove adlarıyla verir. Güncelleme için ayrı bir metot yoktur; var olan bir anahtarla yapılan put güncelleme anlamına gelir.

Aşağıdaki kısa kod parçası bu işlemleri art arda kullanır. Satır sonlarındaki yorumlar her çağrının sonucunu gösterir.

Map<Integer, String> m = new HashMap<>();
m.put(105, "Murat");   m.put(21, "Leyla");
m.put(21, "Ali");      // güncelleme: "Leyla" → "Ali"
m.get(21);             // "Ali"
m.remove(105);         // "Murat"
m.get(88);             // null: böyle bir anahtar yok

İlk satır, anahtarları Integer, değerleri String olan boş bir eşleme oluşturur. Sol taraftaki tür Map arayüzüdür; sağdaki new HashMap<>() ise bu arayüzün hash tablosuyla yapılmış gerçeklemesidir. Değişkeni arayüz türünde tanımlamak iyi bir alışkanlıktır: ileride HashMap yerine TreeMap kullanmak gerekirse yalnız bu satır değişir.

İkinci satırda iki çift eklenir: (105, "Murat") ve (21, "Leyla"). Üçüncü satırdaki m.put(21, "Ali") yeni bir çift eklemez, çünkü 21 anahtarı zaten vardır. Bu çağrı bir güncellemedir: 21'in değeri "Leyla"dan "Ali"ye döner ve eşlemede yine iki çift kalır. m.get(21) artık "Ali" döndürür. m.remove(105), 105 anahtarlı çifti çıkarır ve değeri olan "Murat"ı döndürür. Son satırdaki m.get(88) ise null döndürür, çünkü eşlemede 88 anahtarı hiç yoktur.

put'un da bir dönüş değeri vardır, ama yukarıdaki kod bunu kullanmaz. Anahtar yeniyse put null döndürür. Anahtar varsa değeri günceller ve eski değeri döndürür. Bu ayrıntı, bir ekleme ile bir güncellemeyi kod içinde ayırt etmenin en kolay yoludur.

12.1.3Dizide sabit sürede erişim

Hash tablosunun fikrine bir soruyla yaklaşalım: bir dizide arama O(1) sürede yapılabilir mi? Öğeleri birbiriyle karşılaştırarak bu zordur. Sırasız bir dizide aranan öğe her yerde olabilir; en kötü durumda bütün hücrelere bakmak gerekir. Bu doğrusal aramadır ve O(n) sürer. Dizi sıralıysa ikili arama her adımda aralığı yarıya indirir ve O(log n) karşılaştırma yapar. Karşılaştırmaya dayanan hiçbir yöntem bundan iyisini genel olarak sağlayamaz.

Ama dizinin bir özelliği daha vardır. Aranan öğenin konumu, yani indisi biliniyorsa erişim tek adımdır:

int[] siraliDizi = {1, 3, 5, 7, 9};
int aranacakIndis = 2;                   // erişilmek istenen öğenin indisi
int oge = siraliDizi[aranacakIndis];     // O(1): oge = 5

siraliDizi[aranacakIndis] ifadesi diziyi taramaz. Dizinin bellekteki başlangıç adresine indis × hücre boyu eklenir ve o adrese doğrudan gidilir. Bu hesap dizinin uzunluğundan bağımsızdır. Beş öğeli dizide de beş milyon öğeli dizide de aynı sürede yapılır. Bu yüzden indisle erişim O(1)'dir.

Buradan hash tablosunun temel fikri çıkar: anahtarı doğrudan bir dizi indisine çevirebilirsek, karşılaştırma yapmadan tek adımda doğru hücreye gideriz. Bölümün geri kalanı bu fikrin nasıl hayata geçirildiğini ve karşılaştığı engelleri anlatır.

12.1.4İndisleme: anahtar = indis

En basit durumdan başlayalım. Anahtarlar 0 ile 9 arasındaki tam sayılar olsun. O zaman k anahtarını dizinin k numaralı hücresine koymak yeterlidir: 3 anahtarı A[3]'te, 7 anahtarı A[7]'de durur. Bir anahtarın tabloda olup olmadığını öğrenmek için yalnız o anahtarın hücresine bakılır. Bu yönteme indisleme denir.

Şekil 12.2 anahtar uzayı {1, 3, 5, 6, 7, 9} olan bir örneği gösterir. Her anahtar kendi numarasını taşıyan hücreye yerleşmiştir. Kullanılmayan 0, 2, 4 ve 8 numaralı hücreler boştur.

Şeklin alt iki parçası, başarılı ve başarısız aramanın aynı maliyette olduğunu gösterir. ara(3) yalnız A[3]'e bakar ve dolu olduğunu görür. ara(0) yalnız A[0]'a bakar ve boş olduğunu görür. İkisinde de başka hiçbir hücre incelenmez. Ekleme ve silme de aynı şekilde tek hücreyi değiştirir.

12.1.5Doğrudan adresleme ve sınırı

İndisleme fikrini genelleştirdiğimizde doğrudan adresleme (direct addressing) elde edilir. Olası her anahtar için dizide bir hücre ayrılır. Anahtar k, A[k] hücresinde saklanır. Bu tabloda arama, ekleme ve silme O(1)'dir ve tablo hiçbir karşılaştırma yapmaz.

Şekil 12.3 yöntemin zayıf tarafını gösterir. Ali, Beyza, Deniz ve Onur adlı dört kişi, 30 hücrelik bir dizinin 0, 2, 5 ve 29 numaralı hücrelerine yerleşmiştir. Kullanılan hücre dört, ayrılan hücre otuzdur. Diğer 26 hücre boş durur ama yine de bellekte yer kaplar.

Doğrudan adreslemenin iki ciddi sınırı vardır:

• Bellek israfı. Anahtar uzayı büyükse ayrılması gereken dizi de büyür. Dokuz haneli okul numaralarını doğrudan adreslemek için 10⁹ hücre gerekir. Her hücre 4 baytlık bir int olsa bile bu yaklaşık 4 GB eder. Oysa bir bölümde birkaç yüz öğrenci vardır. Hücrelerin milyonda birinden azı kullanılır.
• Anahtar tam sayı olmayabilir. "Ali" ya da "Beyza" gibi bir dize, dizi indisi olarak kullanılamaz. A["Ali"] diye bir erişim yoktur.

Çözüm, büyük ve belki tam sayı bile olmayan anahtar uzayını küçük bir diziye sıkıştıran bir fonksiyon kullanmaktır. Bu fonksiyon her anahtarı 0 ile N − 1 arasında bir indise çevirir; N burada dizinin boyudur ve saklanacak öğe sayısıyla orantılı seçilir. Böyle bir fonksiyona hash fonksiyonu denir.

12.1.6Hash tekniği

Hash tekniği, öğeleri saklamak ve onlara hızlı erişmek için kullanılır. Temel adım, bir öğe için dizide hızlıca bir konum bulmaktır. Bu konuma kova (bucket) ya da açık adreslemede yuva (slot) denir. Konum belli olunca öğeyi eklemek, çıkarmak ve güncellemek kolaydır, çünkü dizinin yalnız o hücresiyle uğraşılır.

Şekil 12.4 bu süreci tek bir anahtar için gösterir. "Ali" anahtarı hash fonksiyonuna girer, fonksiyon 8 değerini üretir ve öğe kovalar dizisinin 8 numaralı kovasına yerleşir. Daha sonra "Ali" arandığında aynı hesap yeniden yapılır, yine 8 bulunur ve doğrudan 8. kovaya bakılır.

Bu 8 değeri nereden geldi? Java'da her nesnenin bir hashCode() metodu vardır. "Ali" dizesi için bu metot 65918 döndürür. Tabloda 13 kova varsa 65918'in 13'e bölümünden kalan alınır: 65918 mod 13 = 8. Yani “hash fonksiyonu” aslında iki adımlı bir hesaptır. Önce anahtar bir tam sayıya, sonra bu tam sayı tablonun aralığına çevrilir. Bu iki adım ve 65918 sayısının nasıl hesaplandığı sonraki kesimde ayrıntılı işlenir.

12.2Hash fonksiyonları

Hash tablosunun temelinde hash fonksiyonu durur. Fonksiyon anahtarı alır ve öğenin tablodaki konumunu üretir. Tablonun hızlı olup olmaması büyük ölçüde bu fonksiyonun kalitesine bağlıdır. İyi bir fonksiyon anahtarları kovalara dengeli dağıtır ve her işlem bir iki adımda biter. Kötü bir fonksiyon anahtarları birkaç kovaya yığar; o zaman tablo, bir listeden farksız hâle gelir.

12.2.1İyi bir hash fonksiyonu

İyi bir hash fonksiyonundan dört özellik beklenir:

• Belirleyici (deterministic) olmalı. Aynı anahtar her zaman aynı indisi vermelidir. "Ali" ekleme sırasında 8. kovaya gönderilip arama sırasında 3. kovada aranırsa bir daha bulunamaz. Bu yüzden fonksiyon rastgele sayı, saat ya da başka bir dış etkene bağlı olamaz.
• Hızlı olmalı. Hash tablosunun bütün üstünlüğü, aramanın sabit sürede bitmesidir. Hash hesabı uzun sürerse bu üstünlük kaybolur. Fonksiyonun maliyeti O(1) kabul edilir. Bir dizenin hash'i aslında dizenin uzunluğu kadar sürer, ama anahtar uzunluğu tablodaki öğe sayısından bağımsız bir sabit sayılır.
• Düzgün dağılım sağlamalı. Anahtarları kovalara olabildiğince eşit yaymalıdır. Kovalar dengeli dolarsa her kovada az öğe olur ve aynı kovaya düşen anahtar sayısı, yani çakışma sayısı azalır.
• Anahtarın tamamını kullanmalı. Yalnız ilk harfe bakan bir fonksiyon "Ali", "Ayşe" ve "Ahmet" anahtarlarını aynı kovaya atar. Anahtarın her parçası sonucu etkilemelidir; yoksa bir parçada benzeşen anahtarlar hep çakışır.

Dördüncü özelliğin önemini somut sayılarla görelim. 13 kovalı bir tabloya "Ali", "Ayşe" ve "Ahmet" konacak olsun. Yalnız ilk harfin kodunu (A = 65) kullanan bir fonksiyon üçünü de 65 mod 13 = 0 numaralı kovaya gönderir. Java'nın bütün karakterleri kullanan String.hashCode() metoduyla hesap yapılırsa aynı üç anahtar 8, 6 ve 5 numaralı kovalara düşer. Aynı tablo ve aynı anahtarlar, yalnız fonksiyon değiştiği için üç çakışmadan sıfır çakışmaya geçmiştir.

Fonksiyonun ne kadar kötü olabileceğine en uç örnek, her anahtar için aynı indisi döndüren fonksiyondur. Bu durumda bütün öğeler tek bir kovada toplanır. Arama, o kovadaki öğeleri tek tek gezmek zorunda kalır ve O(n) sürer. Hash tablosu, karmaşık bir bağlı listeye dönüşmüş olur.

Fonksiyonun yanında kapasite, yani kova sayısı N da önemlidir. Kapasite büyük seçilirse boş kovalar belleği israf eder. Küçük seçilirse kovalar kalabalıklaşır ve çakışmalar artar. Pratikte N, saklanacak öğe sayısıyla orantılı tutulur. Öğe sayısı arttıkça tablo büyütülür (12.5.2).

12.2.2Hash kodu ve sıkıştırma

Bir hash fonksiyonu iki aşamada düşünülür. Şekil 12.5 bu aşamaları "Ali" anahtarı üzerinde gösterir.

1. Hash kodu (hash code): Anahtar, tablodan bağımsız olarak bir tam sayıya çevrilir. Java'da bu iş her nesnenin hashCode() metoduyla yapılır. Hash kodu tablonun boyunu bilmez; çok büyük ya da negatif olabilir.
2. Sıkıştırma (compression function): Hash kodu, 0 ile N − 1 arasındaki bir indise indirilir. Bu adım tablonun boyuna bağlıdır. Tablo büyütülürse aynı hash kodu farklı bir indise sıkıştırılır.

İki aşamayı ayırmanın pratik bir yararı vardır. Hash kodunu hesaplamak anahtarın sorumluluğudur: String sınıfı kendi kodunu, Integer sınıfı kendi kodunu hesaplar. Sıkıştırma ise tablonun işidir. Böylece aynı tablo her türden anahtarla çalışabilir ve aynı anahtar her boydaki tabloya konabilir.

En çok kullanılan iki sıkıştırma yöntemi şunlardır:

Bölme yöntemi. h(k) = k mod N. Hash kodunun N'ye bölümünden kalan alınır. Kalan her zaman 0 ile N − 1 arasındadır (negatif kodlar için bkz. 12.3.4). Yöntem basit ve hızlıdır. Ama N'nin seçimine duyarlıdır. N asal seçilirse anahtarlardaki düzenli örüntüler, örneğin hep 10'un katı olan anahtarlar, aynı kovalara yığılmaz.

Tablo 12.3'ün arkasındaki neden şudur. N = 10 iken k mod 10 yalnız sayının son hanesine bakar. Bütün anahtarların son hanesi 0 olduğu için hepsi 0. kovaya düşer. Anahtarın diğer haneleri sonucu hiç etkilemez; bu, “anahtarın tamamını kullanma” ilkesine aykırıdır. N = 11 ise 10 ile ortak böleni olmayan bir sayıdır. 10'un katları 11'e bölündüğünde kalanlar 10, 9, 8, … diye ilerler ve kovalara yayılır. Genel kural: anahtarlar d'nin katlarıysa ve d ile N'nin ortak böleni g ise, anahtarlar kovaların yalnız 1/g'sini kullanabilir. N asal olursa bu ortak bölen ancak d, N'nin katıysa 1'den büyük olur.

MAD yöntemi (Multiply-Add-and-Divide, çarp-topla-böl). h(k) = ((a·k + b) mod p) mod N. Burada p, N'den büyük bir asal sayıdır; a ve b, tablo kurulurken rastgele seçilen sabitlerdir ve a ≠ 0'dır. Çarpma ve toplama, anahtardaki düzenli örüntüleri karıştırır. Böylece N asal olmasa bile dağılım düzelir.

12.2.3equals ve hashCode sözleşmesi

Java'da hash tablosu iki metoda dayanır. hashCode() anahtarın hangi kovaya gideceğini belirler. equals() ise kovadaki bir anahtarın aranan anahtarla gerçekten aynı olup olmadığını söyler. Tablonun doğru çalışması için bu iki metodun birbiriyle uyumlu olması gerekir. Java bu uyumu bir sözleşme (contract) olarak tanımlar.

Sözleşmenin dört sonucu vardır:

• Eşit nesneler. a.equals(b) doğruysa iki nesnenin hash kodu aynıdır. Bu kural çiğnenirse eşit anahtarlar farklı kovalara düşer. a ile eklenen bir değer b ile aranınca bulunamaz.
• Aynı hash kodu. İki nesnenin hash kodunun aynı olması, nesnelerin eşit olduğu anlamına gelmez. Java'da "Aa" ve "BB" dizelerinin hashCode() değeri aynıdır (ikisi de 2112), ama dizeler farklıdır. Bu yüzden hash tablosu kovaya ulaştıktan sonra anahtarları ayrıca equals ile karşılaştırır.
• Birlikte ezme. Bir sınıf equals'ı yeniden tanımlıyorsa (eziyorsa, override) hashCode'u da aynı alanlara göre yeniden tanımlamalıdır. Yalnız birini ezmek sözleşmeyi bozar.
• Değiştirilebilir anahtar. Tabloya eklendikten sonra equals/hashCode'da kullanılan alanları değişen bir anahtar, doğru kovada aranamaz. Yeni hash kodu başka bir kovayı gösterir; öğe ise eski kovada kalmıştır.

Kısacası, hash tablosunda kova seçimini hashCode, anahtarın gerçekten aynı olup olmadığını equals belirler. Java 16 ile gelen record türleri bu işi kendiliğinden doğru yapar:

record Ogrenci(int no, String ad) {}
Map<Ogrenci, Double> notlar = new HashMap<>();
notlar.put(new Ogrenci(42, "Ada"), 87.5); // record: equals/hashCode hazır (Java 16+)

record Ogrenci(int no, String ad) {} satırı, no ve ad alanları olan değişmez bir sınıf tanımlar. Derleyici bu sınıf için iki alanı birlikte karşılaştıran bir equals ve iki alandan hesaplanan bir hashCode üretir. Bu yüzden new Ogrenci(42, "Ada") ile eklenen not, başka bir new Ogrenci(42, "Ada") nesnesiyle sorulduğunda bulunur. Ayrıca record alanları sonradan değiştirilemez; değiştirilebilir anahtar sorunu da baştan önlenmiş olur.

12.2.4hashCode unutulursa

Sözleşmenin çiğnendiği en yaygın durum, equals'ın ezilip hashCode'un unutulmasıdır. Aşağıdaki Nokta sınıfı iki noktayı koordinatları aynıysa eşit sayar, ama hashCode() metodu yoktur.

class Nokta {
  int x, y;
  Nokta(int x, int y) { this.x = x; this.y = y; }
  public boolean equals(Object o) {
    return o instanceof Nokta p
        && x == p.x && y == p.y;
  }
  // hashCode() yok -> Object'inki
}
Map<Nokta, String> m = new HashMap<>();
m.put(new Nokta(1, 2), "A");
m.get(new Nokta(1, 2));  // büyük olasılıkla null (!)

equals metodundaki o instanceof Nokta p ifadesi iki iş yapar. Önce o'nun bir Nokta olup olmadığını sorar. Öyleyse onu p adlı bir Nokta değişkenine bağlar. Ardından iki koordinat karşılaştırılır. Bu metoda göre new Nokta(1, 2) ile ikinci bir new Nokta(1, 2) eşittir.

hashCode() ezilmediği için Java, Object sınıfındaki varsayılan metodu kullanır. Bu metot nesnenin kimliğine dayanır: her yeni nesne için genellikle farklı bir değer üretir. İki noktanın koordinatları aynı olsa da ayrı nesneler oldukları için kimlik hash'leri neredeyse her zaman farklıdır. Şekil 12.6 bunun sonucunu adım adım gösterir.

Şekildeki (a) ve (b) adımlarındaki 3 ve 6 sayıları yalnız örnektir. Kimlik hash'i her çalıştırmada değişebilir. Ama sonuç neredeyse her zaman aynıdır: get yanlış kovaya bakar ve null döndürür. “Neredeyse” sözcüğü de önemlidir. İki kimlik hash'i tesadüfen aynı kovaya düşebilir. O zaman get doğru değeri bulur ve hata gizlenir. Böyle hatalar bazen çalışan, bazen çalışmayan programlara yol açtığı için bulunması en zor hatalardandır.

Burada bir ayrıntıya daha dikkat etmek gerekir. Java HashMap'i bir kovadaki düğümü incelerken önce hash kodlarını karşılaştırır, ancak kodlar eşitse equals'ı çağırır. Bu yüzden iki nokta tesadüfen aynı kovaya düşse bile kimlik hash'leri farklıysa equals çağrılmaz ve eşleşme yine bulunmaz. Kısacası hashCode ezilmeyen bir sınıfta, equals ne kadar doğru yazılmış olursa olsun, eşleme bu eşitliği görmez.

Çözüm, hashCode'u equals'ta kullanılan alanlarla ezmektir:

public int hashCode() {
  return Objects.hash(x, y);
}

Objects.hash(x, y), verilen alanlardan String.hashCode()'a benzer bir hesapla tek bir sayı üretir: 31 · (31 · 1 + x) + y. x = 1, y = 2 için sonuç 31 · 32 + 2 = 994'tür. Eşit iki noktanın koordinatları aynı olduğundan bu değer de aynıdır; iki nokta aynı kovaya düşer. Sözleşme sağlanmıştır. Nokta(2, 1) için sonuç 31 · 33 + 1 = 1024 olur; koordinatların sırası sonucu etkiler.

12.2.5Örnek hash fonksiyonları

Uygulamada pek çok hash fonksiyonu kullanılır. Aşağıda dört tanesi, kısa Java kodlarıyla verilmiştir.

Mod alma (bölme kalanı). Tam sayı anahtarlar için en basit fonksiyondur:

int modulusHash(int anahtar, int diziBoyu) {
  return Math.floorMod(anahtar, diziBoyu);
}

Burada % yerine Math.floorMod kullanılır. Java'da % işleminin sonucu bölünenin işaretini alır; negatif bir anahtar için negatif bir kalan çıkabilir. Math.floorMod ise bölen pozitif olduğu sürece her zaman 0 … diziBoyu − 1 aralığında bir sonuç verir. Bu fark 12.3.4'te ayrıntılı işlenir.

CRC32. Döngüsel artıklık denetimi (Cyclic Redundancy Check), aslında veri iletiminde bozulmaları yakalamak için tasarlanmış bir sağlama toplamıdır. Bitleri iyi karıştırdığı için hash fonksiyonu olarak da kullanılabilir. Java'da java.util.zip paketinde hazır gelir:

long crc32Hash(String anahtar) {
  CRC32 crc = new CRC32();  // java.util.zip
  crc.update(anahtar.getBytes());
  return crc.getValue();
}

Metot dizeyi bayt dizisine çevirir, CRC32 nesnesine verir ve 32 bitlik sonucu long olarak döndürür. Sonuç 0 ile 2³² − 1 arasındadır; tabloda kullanmak için yine sıkıştırma gerekir. Örneğin "Ali" için bu metot 1933558706 döndürür.

DJB2. Daniel J. Bernstein'ın dizeler için önerdiği, kısa ve hızlı bir fonksiyondur:

int djb2Hash(String s) {
  int h = 5381;
  for (int i = 0; i < s.length(); i++)
    h = (h * 33) ^ s.charAt(i);
  return h;
}

Fonksiyon 5381 ile başlar. Her karakterde o ana kadarki sonucu 33 ile çarpar ve karakterin koduyla birleştirir. Klasik DJB2 bu birleştirmeyi toplama ile yapar: h * 33 + c. Yukarıdaki kod ise XOR (^, bit düzeyinde dışlayan veya) kullanan biçimdir. İki biçim de yaygındır. Çarpma int sınırını kolayca aşar; sonuç taşar ve negatif olabilir. "Ali" için sonuç 193442657'dir, ama uzun dizelerde negatif değerler sık görülür. Bu yüzden indis için yine güvenli bir sıkıştırma gerekir.

Java String.hashCode(). Java'nın dizeler için kullandığı fonksiyondur:

// Σ s[i] · 31^(n−1−i)
"abc".hashCode()  // 96354

n karakterli bir dize için formül s[0] · 31ⁿ⁻¹ + s[1] · 31ⁿ⁻² + … + s[n−1]'dir. Her karakter, dizedeki konumuna göre 31'in farklı bir kuvvetiyle çarpılır. "abc" için 97 · 31² + 98 · 31 + 99 = 93217 + 3038 + 99 = 96354 bulunur. Konumun katsayıya girmesi sayesinde "abc" ile "cba" farklı kodlar alır. Yalnız karakter kodlarını toplayan bir fonksiyon ise bu iki dizeyi ayırt edemezdi.

Neden 31? 31 tek bir asal sayıdır. Tek olduğu için çarpma sırasında taşan bitler bilgiyi tamamen yok etmez; çift bir çarpan her adımda en alt biti sıfırlardı. Ayrıca 31 · h, işlemcide (h << 5) − h biçiminde bir kaydırma ve bir çıkarmayla hızla hesaplanabilir.

12.2.6Kod izleme: "Ali".hashCode()

Aşağıdaki hash metodu, String.hashCode() ile aynı hesabı açık bir döngüyle yapar. main bu metodu "Ali" için çağırır, sonra sonucu 13 kovalı bir tabloya sıkıştırır.

// String.hashCode() ile aynı hesap:
int hash(String s) {
  int h = 0;
  for (int i = 0; i < s.length(); i++)
    h = 31 * h + s.charAt(i);
  return h;
}

// main:
int kod = hash("Ali");                // 65918
int indis = Math.floorMod(kod, 13);   // 8

Metot h = 0 ile başlar. Döngü dizenin her karakteri için bir kez döner. Her turda önceki h 31 ile çarpılır ve sıradaki karakterin kodu eklenir. s.charAt(i) bir char döndürür; Java bu değeri toplamada kendiliğinden karakterin Unicode koduna, yani bir tam sayıya çevirir. "Ali" dizesinin karakter kodları A = 65, l = 108 ve i = 105'tir. Tablo 12.4 döngünün her turunu verir.

Son değer formülle de doğrulanabilir: 65 · 31² + 108 · 31 + 105 = 62465 + 3348 + 105 = 65918. Döngü bu kuvvetleri ayrı ayrı hesaplamaz. Her turda önceki toplamı 31 ile çarpmak, daha önce eklenen her karakterin katsayısını bir kuvvet yükseltir. Bu yöntem, polinom değerlendirmede bilinen Horner yöntemidir. n karakter için n çarpma ve n toplama yapar; maliyet O(n), ek bellek O(1)'dir.

Son adım sıkıştırmadır: Math.floorMod(65918, 13). 13 · 5070 = 65910 ve 65918 − 65910 = 8'dir. "Ali" 13 kovalı tabloda 8. kovaya düşer. Şekil 12.7 izlemenin başını ve sonunu gösterir.

Kısa dizelerde sonuç pozitif çıkar, ama uzun dizelerde çarpım int sınırını (2³¹ − 1 = 2.147.483.647) aşar. Java'da tam sayı taşması hata vermez; sayı sessizce sarılır ve negatif olabilir. Örneğin "Sercan".hashCode() −1821977712'dir. Daha ilginç bir örnek "polygenelubricants" dizesidir: bu dizenin hash kodu tam olarak Integer.MIN_VALUE, yani −2147483648'dir. Bu değer 12.3.4'te önemli bir tuzağı gösterecektir.

12.2.7Kod izleme: modulusHash()

Bölme yöntemini 10 hücrelik bir tablo üzerinde izleyelim. Kod beş anahtarı sırayla alır, her biri için hücre indisini hesaplar ve anahtarı o hücreye yazar.

int modulusHash(int anahtar, int diziBoyu) {
  return Math.floorMod(anahtar, diziBoyu);
}

// main:
Integer[] tablo = new Integer[10];
for (int k : new int[]{5, 1, 10, 26, 99}) {
  int j = modulusHash(k, tablo.length);
  tablo[j] = k;
}

Integer[] tablo = new Integer[10] on hücrelik bir dizi oluşturur. Dizi int değil Integer türünde olduğu için her hücre başlangıçta null'dır; böylece boş hücre ile 0 değeri birbirinden ayrılır. Döngüdeki new int[]{5, 1, 10, 26, 99} ifadesi anahtarları sırayla verir. Her turda modulusHash(k, tablo.length) anahtarın 10'a bölümünden kalanı döndürür ve anahtar o hücreye yazılır.

Beş anahtar beş farklı hücreye yerleşmiş, hiçbir hücreye iki anahtar düşmemiştir. Bu bir şanstır. Sırada 15 olsaydı 15 mod 10 = 5 hesaplanırdı ve 15, 5'in hücresine yazılırdı. Kod 5'in üzerine yazar ve 5 kaybolurdu. Bu tablo, çakışmaları hiç ele almadığı için yalnız gösterim amaçlıdır. Her ekleme O(1), beş ekleme toplam O(5) sürmüştür; tablo 10 hücrelik sabit bir alan kullanır.

12.2.8Çakışmalar

Örneğin 10 kovalı tabloda bölme yöntemiyle h(5) = h(105) = 5'tir. 5 ile 105 farklı anahtarlardır ama aynı indisi üretirler. İki öğe aynı hücrede doğrudan saklanamayacağı için tablonun bu durumu çözen bir stratejisi olmalıdır.

Çakışmalar tesadüf değildir; anahtar uzayı tablodan büyük olduğu sürece kaçınılmazdır. Bunun nedeni basit bir sayma ilkesidir.

Teorem bize hash fonksiyonu tasarımının sınırını söyler. Dokuz haneli okul numaraları için U = 10⁹'dur ve tablo 1000 kovalıysa en kalabalık kovaya en az bir milyon olası numara gider. İyi bir fonksiyon çakışmayı yok edemez; yalnız gerçekte gelen anahtarların kovalara dengeli dağılmasını umabilir. Çakışma, öngörülenden de erken başlar. 365 kovalı bir tabloya rastgele 23 anahtar konursa en az bir çakışma olma olasılığı yaklaşık 0,507'dir. Bu, “doğum günü problemi” olarak tanınan sonuçtur: 23 kişilik bir sınıfta iki kişinin aynı gün doğmuş olma olasılığı yarıdan fazladır.

Şekil 12.9 çakışmayı bir örnekle gösterir. Altı anahtar-değer çifti 10 yuvalı tabloya bölme yöntemiyle yerleştiriliyor. İlk beşi boş yuvalara düşer. (105, Murat) çifti ise 5. yuvaya gitmek ister, ama orada (5, Ali) vardır.

Çakışmaları çözmenin iki ana stratejisi vardır:

• Ayrı zincirleme (separate chaining): Her kova, o kovaya düşen bütün öğeleri bir bağlı listede tutar. Çakışan öğe listeye eklenir.
• Açık adresleme (open addressing): Bütün öğeler dizinin kendisinde durur. Dolu bir yuvaya gelen öğe için belirli bir kurala göre dizide başka bir boş yuva aranır.

Sonraki iki kesim bu stratejileri kodlarıyla ve izlemeleriyle ele alır.

12.3Ayrı zincirleme

Ayrı zincirleme, çakışmayı en doğrudan yoldan çözer: bir kovaya birden çok öğe düşüyorsa kova bu öğelerin hepsini tutar. Bunun için her kova tek bir öğe yerine bir bağlı listenin başını saklar. Bu listeye zincir (chain) denir. Yöntemin adındaki “ayrı” sözcüğü, her kovanın kendi zincirini tutmasından gelir.

12.3.1Zincirleme fikri

10 kovalı bir tabloya h(k) = k % 10 ile sırasıyla (5, "Ali"), (1, "Tuna"), (10, "Leyla"), (26, "Ceren"), (99, "Sena") ve (105, "Murat") çiftlerini ekleyelim. Her ekleme şu adımları izler:

• h(5) = 5: 5. kova boştur; (5, "Ali") düğümü kovaya bağlanır.
• h(1) = 1: 1. kova boştur; (1, "Tuna") düğümü kovaya bağlanır.
• h(10) = 0: 0. kova boştur; (10, "Leyla") düğümü kovaya bağlanır.
• h(26) = 6: 6. kova boştur; (26, "Ceren") düğümü kovaya bağlanır.
• h(99) = 9: 9. kova boştur; (99, "Sena") düğümü kovaya bağlanır.
• h(105) = 5: 5. kova doludur, orada (5, "Ali") vardır. Bu bir çakışmadır. Yeni düğüm zincirin başına eklenir: kova artık önce 105'i, 105 de 5'i gösterir.

Yeni düğüm neden zincirin sonuna değil de başına eklenir? Kova, zincirin yalnız ilk düğümünü bilir. Sona eklemek için zincirin sonuna kadar yürümek gerekir. Başa eklemek ise yalnız iki referans ataması ister: yeni düğüm eski başı gösterir, kova yeni düğümü gösterir. Bu işlem zincirin uzunluğundan bağımsızdır, yani O(1)'dir. Ancak 12.3.5'te görüleceği gibi ekleme öncesinde anahtarın zincirde zaten olup olmadığı denetlenir. Bu denetim zaten bütün zinciri gezer. Bu yüzden Java HashMap gibi bazı gerçeklemeler düğümü sona ekler; iki seçim de doğrudur.

Zincirlemede bir kovaya kaç öğe düşerse düşsün tablo dolmaz. Zincirler gerektiği kadar uzar. Bu esneklik yöntemin en büyük üstünlüğüdür, ama bir bedeli vardır: zincir uzadıkça arama yavaşlar. Bu yüzden zincirlerin ortalama uzunluğu, yani tablonun ne kadar dolu olduğu izlenir.

12.3.2Hash tablosu terimleri

Kod okumayı kolaylaştırmak için zincirlemeli tablonun parçalarına ad verelim. Şekil 12.11 bu adları aynı altı çiftli tablo üzerinde gösterir.

Kapasite ile büyüklüğü karıştırmamak gerekir. Kapasite tablonun kaç kovası olduğunu, büyüklük tabloda kaç çift bulunduğunu söyler. Şekildeki tabloda 10 kovanın 5'i doludur ama çift sayısı 6'dır, çünkü bir kovada iki çift vardır. Zincirlemede büyüklük kapasiteyi aşabilir; 10 kovalı tabloda 25 çift de saklanabilir.

12.3.3Kod: HashTablosu sınıfı

Aşağıdaki sınıf, anahtarları Integer, değerleri String olan zincirlemeli bir hash tablosunun iskeletidir.

public class HashTablosu {
  private HashDugumu[] kovalar;   // zincirlerin ilk düğümleri
  private int kovaSayisi, buyukluk;

  public HashTablosu(int kapasite) {
    this.kovaSayisi = kapasite;
    this.kovalar = new HashDugumu[kapasite];
    this.buyukluk = 0;
  }
  private class HashDugumu {
    private Integer anahtar;
    private String deger;
    private HashDugumu sonraki;
    public HashDugumu(Integer anahtar, String deger) {
      this.anahtar = anahtar; this.deger = deger;
    }
  }
}

Sınıfın alanları ve parçaları şunlardır:

• kovalar, HashDugumu türünde bir dizidir. Her hücre bir zincirin ilk düğümünü gösterir; zincir boşsa hücre null'dır.
• kovaSayisi dizinin uzunluğunu, buyukluk saklanan çift sayısını tutar.
• Yapıcı, istenen kapasitede bir dizi ayırır. Java'da yeni bir nesne dizisinin bütün hücreleri null ile başlar; bu yüzden ayrıca bir döngüyle kovaları boşaltmak gerekmez. new HashTablosu(10) çağrısı 10 boş kova oluşturur ve buyukluk = 0 olur.
• HashDugumu, sınıfın içinde tanımlanmış bir iç sınıftır. Her düğüm bir anahtar, bir deger ve bir sonraki düğümü gösteren sonraki referansı tutar. Bu, tek yönlü bağlı listenin düğümüdür; yalnız anahtar alanı eklenmiştir.

Düğümün değerin yanında anahtarı da tutması şarttır. Bir kovada birden çok çift olabileceği için, aranan anahtarın hangi düğümde olduğu ancak düğümdeki anahtara bakılarak anlaşılır. Yalnız değer saklansaydı 5. kovadaki "Murat" ile "Ali"den hangisinin 105'e ait olduğu bilinemezdi.

Alan maliyeti: dizi N referans, her düğüm bir anahtar, bir değer ve bir sonraki referansı tutar. Toplam alan O(N + n)'dir.

12.3.4Kova indisi ve negatif hash kodları

Bir anahtarın hangi kovaya gideceğini getKovaIndisi metodu hesaplar:

// Basit yol: anahtar % kovalar.length → negatif olabilir!
private int getKovaIndisi(Integer anahtar) {
  int h = anahtar.hashCode();  // = anahtar
  return Math.floorMod(h, kovalar.length);
}

Metot önce anahtarın hash kodunu alır. Integer sınıfında hashCode() sayının kendisini döndürür; 41'in hash kodu 41'dir. Ardından kod, Math.floorMod ile dizinin uzunluğuna sıkıştırılır. İlk satırdaki yorum önemli bir uyarı içerir: “basit yol” olan anahtar % kovalar.length negatif bir sonuç verebilir.

Java'da % işleminin sonucu bölünenin işaretini alır. 41 % 10 = 1'dir, ama −7 % 10 = −7'dir. Negatif bir sayı dizi indisi olarak kullanılırsa Java ArrayIndexOutOfBoundsException fırlatır. Math.floorMod ise bölen pozitif olduğu sürece her zaman 0 ile bölen − 1 arasında bir sonuç verir.

Anahtarlar her zaman pozitif tam sayılar olsa bile bu ayrıntı önemlidir. String gibi anahtarların hashCode() değeri sık sık negatif çıkar; örneğin "Sercan"ın hash kodu −1821977712'dir. Tablo her tür anahtarla çalışacaksa negatif kodlara hazırlıklı olmalıdır.

Math.floorMod içeride nasıl çalışır? Bölen n > 0 iken davranışı aşağıdaki kısa metotla aynıdır:

private int getKovaIndisi(Integer anahtar) {
  int h = anahtar.hashCode();  // = anahtar
  return Math.floorMod(h, kovalar.length);
}

// floorMod'un n > 0 için eşdeğeri:
static int floorMod(int x, int n) {
  int r = x % n;       // işaret x'ten gelir
  if (r < 0) r += n;   // negatifse n ekle
  return r;
}

Metot önce Java'nın % işlemini yapar. Sonuç negatifse n ekler. x % n sonucu her zaman −(n − 1) ile n − 1 arasında olduğundan, negatif bir sonuca n eklemek onu 1 ile n − 1 arasına taşır. Pozitif sonuca dokunulmaz. Tablo 12.8 iki çağrının izlemesini verir.

Negatif sorunu için akla gelen bir başka çözüm, mutlak değer almaktır: Math.abs(h) % N. Bu çözüm hemen her zaman çalışır, ama bir istisnası vardır. int türü −2147483648 ile 2147483647 arasındaki sayıları tutar. En küçük değer olan Integer.MIN_VALUE = −2147483648'in pozitif karşılığı int'e sığmaz. Java'da Math.abs(Integer.MIN_VALUE) taşar ve yine −2147483648 döndürür.

12.3.5Kod: yerlestir()

Tabloya anahtar-değer çifti ekleyen metot üç adımda çalışır: kovayı bul, zinciri tara, gerekirse başa ekle.

public void yerlestir(Integer anahtar,
                      String deger) {
  int kovaIndisi = getKovaIndisi(anahtar);
  HashDugumu ilk = kovalar[kovaIndisi];
  while (ilk != null) {    // anahtar var mı?
    if (ilk.anahtar.equals(anahtar)) {
      ilk.deger = deger;   // varsa güncelle
      return;
    }
    ilk = ilk.sonraki;
  }
  buyukluk++;
  HashDugumu dugum =
      new HashDugumu(anahtar, deger);
  dugum.sonraki = kovalar[kovaIndisi];
  kovalar[kovaIndisi] = dugum;   // başa ekle
}

Kodun satırları şöyle çalışır:

• kovaIndisi = getKovaIndisi(anahtar) anahtarın kovasını O(1)'de bulur. Bundan sonra yalnız bu kovayla uğraşılır; diğer kovalara hiç bakılmaz.
• ilk = kovalar[kovaIndisi], zincirin ilk düğümünü gösteren bir yardımcı referanstır. Adı “ilk” olsa da döngü içinde zincir boyunca ilerler.
• while (ilk != null) döngüsü zinciri baştan sona tarar. Her düğümde ilk.anahtar.equals(anahtar) sorulur. Anahtar bulunursa yalnız değer değişir (ilk.deger = deger) ve metot döner. Bu bir güncellemedir; buyukluk artmaz, çünkü çift sayısı değişmemiştir.
• Döngü ilk == null ile biterse anahtar tabloda yoktur. buyukluk bir artar, yeni bir düğüm oluşturulur.
• dugum.sonraki = kovalar[kovaIndisi] yeni düğümü eski zincirin başına bağlar. kovalar[kovaIndisi] = dugum ise kovayı yeni düğüme yöneltir. Bu iki satırın sırası önemlidir.

Karşılaştırmanın == ile değil equals ile yapıldığına dikkat edilmelidir. Anahtarlar Integer nesneleridir. == iki referansın aynı nesneyi gösterip göstermediğini sorar. Java küçük sayılar (−128 … 127) için hazır nesneleri yeniden kullandığından == bu aralıkta doğru sonuç verir gibi görünür. 128 ve üstünde ise aynı değerli iki Integer genellikle farklı nesnedir ve == false döndürür. equals ise değerleri karşılaştırır.

Maliyet. Kova bulma O(1)'dir. Zincir tarama, zincirin uzunluğu kadar sürer. Başa ekleme O(1)'dir. Toplam O(1 + zincir uzunluğu) olur. Zincirlerin ortalama uzunluğu küçük tutulduğu sürece bu ortalamada sabittir (12.3.10).

12.3.6Kod izleme: yerlestir()

10 kovalı bir tabloda yalnız (105, "Murat") çifti olsun; buyukluk = 1. Sırasıyla yerlestir(21, "Leyla"), yerlestir(41, "Sena") ve yerlestir(21, "Ali") çağrılıyor. Tablo 12.9 her çağrının adımlarını verir.

İlk çağrıda 1. kova boştur. ilk = null olduğu için döngüye hiç girilmez; anahtarın tabloda olmadığı hemen anlaşılır. buyukluk 2 olur. Yeni düğüm (21, "Leyla") oluşturulur. dugum.sonraki = kovalar[1] satırı null atar, çünkü kova boştu. Son satır kovayı yeni düğüme yöneltir.

İkinci çağrıda 41 de 1. kovaya düşer: bu bir çakışmadır. Döngü 21 düğümünü inceler; 21 ≠ 41 olduğu için ilk = ilk.sonraki ile ilerlenir ve ilk null olur. Anahtar tabloda yoktur. buyukluk 3 olur. Yeni düğüm (41, "Sena") oluşturulur, sonraki alanı eski baş olan 21'i gösterir, kova da 41'i gösterir. Zincir artık 41 → 21'dir. Eski zincir kaybolmamış, yeni düğümün arkasına geçmiştir.

Üçüncü çağrı bir güncellemedir. Döngü önce 41'i görür; eşit değildir, ilerlenir. Sonra 21'i görür: 21.equals(21) doğrudur. Değer "Leyla"dan "Ali"ye döner ve metot return ile biter. Yeni düğüm eklenmez, buyukluk 3'te kalır. Bu çağrı iki karşılaştırma yapmıştır.

12.3.7Kod ve izleme: getir()

Bir anahtarın değerini döndüren metot, yerlestir'in tarama kısmının aynısıdır:

public String getir(Integer anahtar) {
  int kovaIndisi = getKovaIndisi(anahtar);
  HashDugumu ilk = kovalar[kovaIndisi];
  while (ilk != null) {
    if (ilk.anahtar.equals(anahtar))
      return ilk.deger;        // bulundu
    ilk = ilk.sonraki;
  }
  return null;                 // anahtar yok
}

Metot anahtarın kovasını bulur ve yalnız o kovanın zincirini tarar. Diğer kovalara hiç bakılmaz. Anahtar bulunursa değeri döner. Zincir biterse anahtar tabloda yoktur ve metot null döndürür. Maliyeti O(1 + zincir uzunluğu)'dur. Zincirlerin ortalama uzunluğu n / N'dir.

Önceki izlemenin sonundaki tabloda (5. kova → 105; 1. kova → 41 → 21) üç arama yapalım:

getir(105) zincirin ilk düğümünde eşleşmeyi bulur; bir karşılaştırma yeterlidir. getir(21) önce 41'i görür. 41 aynı kovaya düşmüş başka bir anahtardır, yani çakışmanın sonucudur. Zincirde ilerlenir, ikinci düğümde 21 bulunur. getir(88) boş bir kovaya bakar; döngüye hiç girilmez ve null döner. Başarısız bir arama boş kovada tek adımda biter. Kova dolu olsaydı bütün zincir taranmak zorunda kalırdı, çünkü anahtarın zincirde olmadığı ancak sona gelince anlaşılır.

12.3.8Kod: sil()

Zincirden bir düğümü çıkarmak, tek yönlü bağlı listeden düğüm silmekle aynıdır. Bir düğümü listeden koparmak için ondan önceki düğümün sonraki alanını değiştirmek gerekir. Bu yüzden tarama sırasında bir önceki düğüm de izlenir.

public String sil(Integer anahtar) {
  int kovaIndisi = getKovaIndisi(anahtar);
  HashDugumu ilk = kovalar[kovaIndisi];
  HashDugumu onceki = null;
  while (ilk != null &&
         !ilk.anahtar.equals(anahtar)) {
    onceki = ilk;
    ilk = ilk.sonraki;
  }
  if (ilk == null) return null;   // yok
  buyukluk--;
  if (onceki != null)       // ortadan/sondan
    onceki.sonraki = ilk.sonraki;
  else                      // baştan
    kovalar[kovaIndisi] = ilk.sonraki;
  return ilk.deger;
}

Kod satır satır şöyle çalışır:

• onceki = null ile başlanır: zincirin ilk düğümünden önce bir düğüm yoktur.
• while döngüsünün koşulu iki parçalıdır: zincir bitmemişse ve düğümün anahtarı aranan değilse ilerle. Java && işlecinde ilk koşul yanlışsa ikinciye bakmaz. Bu yüzden ilk == null iken ilk.anahtar'a erişilmez ve NullPointerException oluşmaz.
• Döngüde her adımda onceki = ilk ve ilk = ilk.sonraki yapılır; iki referans birlikte ilerler.
• Döngü bitince iki durum vardır. ilk == null ise anahtar zincirde yoktur ve metot null döndürür. Değilse ilk silinecek düğümü gösterir.
• Silme iki biçimde yapılır. Düğüm zincirin ortasında ya da sonundaysa (onceki != null) önceki düğüm silinen düğümü atlar: onceki.sonraki = ilk.sonraki. Düğüm zincirin başındaysa (onceki == null) kova güncellenir: kovalar[kovaIndisi] = ilk.sonraki.
• Son olarak buyukluk bir azaltılmış, silinen değer döndürülür. Kopan düğümü artık hiçbir referans göstermediği için Java'nın çöp toplayıcısı onu bellekten temizler.

Maliyet, getir'le aynıdır: O(1 + zincir uzunluğu). Düğümü koparmak birkaç referans atamasıdır.

12.3.9Kod izleme: sil()

Tablo yine 5. kova → (105, "Murat") ve 1. kova → (41, "Sena") → (21, "Ali") biçiminde, buyukluk = 3 olsun. Sırasıyla sil(21), sil(105) ve sil(88) çağrılıyor.

sil(21) zincirin ortasından silmenin örneğidir. Döngü 41'de eşleşme bulamaz ve iki referansı ilerletir: onceki 41'i, ilk 21'i gösterir. 21 aranan anahtar olduğu için döngü koşulu yanlış olur ve döngü biter. ilk != null olduğundan silme yapılır. onceki null olmadığı için düğüm ortada ya da sondadır: onceki.sonraki = ilk.sonraki ile 41, 21'i atlar ve doğrudan null'ı gösterir. 21 zincirden kopar.

sil(105) baştan silmenin örneğidir. Döngünün koşulu ilk düğümde yanlış olur; döngü gövdesi hiç çalışmaz ve onceki null kalır. Bu yüzden else dalına girilir ve kovanın kendisi güncellenir: kovalar[5] = ilk.sonraki. 105'in ardında düğüm olmadığı için kova boşalır.

sil(88) başarısız bir silmedir. Kova boş olduğu için döngü hemen biter, ilk == null kontrolü null döndürür. Tablo ve buyukluk değişmez.

12.3.10Zincirlemenin maliyeti

Zincirlemeli tabloda bütün işlemler O(1 + zincir uzunluğu) sürer. Peki bir zincir ne kadar uzun olur? Bunu tablonun doluluk oranı belirler.

Ortalama uzunluk her zincirin bu uzunlukta olduğu anlamına gelmez. Bir kova boş, bir başkası kalabalık olabilir. Analizde genellikle şu varsayım yapılır: hash fonksiyonu her anahtarı kovalardan birine, öteki anahtarlardan bağımsız olarak, eşit olasılıkla gönderir. Bu varsayıma basit düzgün hash (simple uniform hashing) denir.

Teoremin asıl mesajı şudur: λ bir sabitin altında tutulursa, örneğin hiçbir zaman 0,75'i aşmazsa, işlemlerin beklenen maliyeti O(1)'dir. Bunun için tablo, çift sayısı arttıkça büyütülür. Bu işleme yeniden boyutlandırma denir ve 12.5.2'de ele alınır. Zincirlemede λ 1'i aşabilir; bu yalnız zincirleri uzatır ve işlemleri yavaşlatır, tabloyu kullanılamaz yapmaz.

En kötü durum ise başkadır. Bütün anahtarlar aynı kovaya düşerse tek bir zincir n uzunluğunda olur ve arama O(n) sürer. Bu, kötü bir hash fonksiyonunda ya da özellikle aynı kovaya düşecek biçimde seçilmiş anahtarlarda görülür. Basit düzgün hash varsayımı yalnız ortalamayı güvence altına alır.

12.4Açık adresleme

Ayrı zincirleme her çakışmada yeni bir düğüm oluşturur. Düğümler belleğin farklı yerlerine dağılır ve her düğüm fazladan bir referans taşır. Açık adresleme bu ek yapıları kullanmaz. Bütün çiftler dizinin kendisinde saklanır ve her yuvada en çok bir çift bulunur. Çakışan bir anahtar için dizide başka bir boş yuva aranır.

12.4.1Yoklama dizisi

Açık adreslemede bir anahtar önce kendi ev yuvasına, yani h(k) numaralı yuvaya bakar. Yuva boşsa anahtar oraya yerleşir. Doluysa belirli bir kurala göre ikinci bir yuva, o da doluysa üçüncü bir yuva denenir. Bir yuvanın dolu olup olmadığına bakma işine yoklama (probing) denir. Denenen yuvaların sırası da anahtarın yoklama dizisidir (probe sequence).

Yuva başına en çok bir çift saklandığından çift sayısı yuva sayısını aşamaz: n ≤ N, yani λ ≤ 1'dir. Zincirlemedeki gibi λ'nın 1'i aşması mümkün değildir. Üç yaygın yoklama yöntemi vardır:

Açık adreslemenin zincirlemeye göre üstünlükleri şunlardır. Ek düğüm ve referans yoktur; bellek yalnız dizi kadardır. Dizi bellekte ardışık durduğu için işlemci önbelleği onu verimli kullanır; ardışık yuvaları yoklamak, dağınık düğümler arasında gezinmekten pratikte hızlıdır. Bedelleri de vardır. Yük faktörü düşük tutulmalıdır, çünkü tablo doldukça yoklama dizileri hızla uzar. Silme de özel bir işlem ister (12.4.5).

Bu kesimin bütün örnekleri aynı veriyi kullanır: N = 13 yuvalı tabloya, h(k) = k mod 13 ile sırasıyla 18, 41, 22, 44, 59, 32, 31 ve 73 anahtarları eklenir. Ev yuvaları sırasıyla 5, 2, 9, 5, 7, 6, 5 ve 8'dir. Aynı veri üç yöntemle eklendiğinde aradaki farklar doğrudan görülür.

12.4.2Doğrusal yoklama

Doğrusal yoklama en basit yöntemdir: ev yuvası doluysa bir sonrakine, o da doluysa ondan sonrakine bakılır. Dizinin sonuna gelinince başa dönülür. Kod şöyledir:

// yerlestir(k): doğrusal yoklama, N = 13
int h = k % 13;                // ev yuvası
for (int i = 0; i < 13; i++) {
  int j = (h + i) % 13;          // h, h+1, h+2…
  if (tablo[j] == null) {      // boş mu?
    tablo[j] = k;
    break;
  }                            // dolu: i++
}

h = k % 13 ev yuvasıdır. Döngü değişkeni i deneme sayısını tutar. Her turda j = (h + i) % 13 denenecek yuvadır: i = 0 için ev yuvası, sonra bir sonraki yuva, sonra bir sonraki. % 13 sayesinde 12. yuvadan sonra 0. yuvaya dönülür. Boş yuva bulununca anahtar yazılır ve break ile döngüden çıkılır. Döngü en çok 13 kez döner, çünkü 13 farklı i değeri bütün yuvaları bir kez dener.

İlk üç anahtar boş tabloya geldiği için ilk denemede yerleşir: 18 → 5, 41 → 2, 22 → 9. Sonraki anahtarların izlemesi Tablo 12.13'te verilmiştir.

44 için ev yuvası 5'tir, ama orada 18 vardır. Bir sonraki yuva 6 boştur; 44 iki yoklamada yerleşir. 59 ev yuvası 7'de yer bulur. 32'nin ev yuvası 6'dır. Ama 6'ya biraz önce 44 yerleşmiştir. 7'de 59 vardır; 32 ancak 8'de yer bulur. 32, ev yuvası 5 olmadığı hâlde 5'ten başlayan kalabalığın içine düşmüştür.

31'in durumu daha da kötüdür. Ev yuvası 5'tir ve 5'ten 9'a kadar bütün yuvalar doludur. 31 altı yoklamadan sonra 10. yuvaya yerleşir. 73'ün ev yuvası 8'dir; 8, 9 ve 10 dolu olduğundan 11'e kadar gider. Sonunda 5'ten 11'e kadar yedi yuva tek bir dolu blok oluşturur.

Kümelenme kendini besler. Bir kümenin herhangi bir yuvasına düşen anahtar, kümenin sonuna kadar yürür ve kümeyi bir yuva uzatır. Küme uzadıkça ona düşen anahtar sayısı da artar. Yukarıdaki örnekte 32 ve 73'ün ev yuvaları 5 değildir, ama ikisi de 5'te başlayan kümeye takılmıştır. Ayrıca iki küme arasındaki tek boş yuva dolduğunda iki küme birleşir ve daha da büyük bir küme oluşur.

Doğrusal yoklamanın maliyeti kümelerin uzunluğuna bağlıdır. Tablo seyrekken neredeyse her anahtar ilk denemede yerleşir. Tablo doldukça kümeler uzar ve yoklama sayısı hızla artar. Bu artışın sayısal karşılığı 12.5.1'de verilmiştir.

12.4.3Karesel yoklama

Birincil kümelenmenin nedeni, yoklamanın komşu yuvalara bakmasıdır. Karesel yoklama, sıçramaları büyüterek kümeden çabuk çıkmaya çalışır: ev yuvasından 1, 4, 9, 16, … yuva ötesi denenir.

// yerlestir(k): karesel yoklama, N = 13
int h = k % 13;                // ev yuvası
for (int i = 0; i < 13; i++) {
  int j = (h + i * i) % 13;      // h, h+1, h+4…
  if (tablo[j] == null) {      // boş mu?
    tablo[j] = k;
    break;
  }                            // dolu: i++
}

Kodun doğrusal yoklamadan tek farkı j'nin hesabıdır: (h + i * i) % 13. i = 0, 1, 2, 3 için ev yuvasına sırasıyla 0, 1, 4 ve 9 eklenir. Aynı anahtarları bu kez karesel yoklamayla ekleyelim.

Fark 32 ile başlar. Doğrusal yoklamada 32, 8. yuvaya yerleşip kümeyi büyütmüştü. Karesel yoklamada üçüncü deneme 6 + 2² = 10'dur ve 32 kümenin dışına, 10. yuvaya yerleşir. 31 dördüncü denemede 5 + 3² = 14, yani 14 mod 13 = 1. yuvaya sıçrar. 8. yuva boş kaldığı için 73 de ev yuvasına ilk denemede yerleşir. Toplam yoklama 19'dan 14'e, en uzun yoklama 6'dan 4'e inmiştir.

Karesel yoklama birincil kümelenmeyi azaltır, ama başka bir sorun bırakır. Aynı ev yuvasına düşen anahtarlar hep aynı yoklama dizisini izler. Örnekte 18, 44 ve 31'in ev yuvası 5'tir; üçü de 5, 6, 9, 1, … sırasını dener. Ev yuvası aynı olan anahtarlar birbirinin yolunu tıkar. Bu duruma ikincil kümelenme (secondary clustering) denir. Etkisi birincil kümelenmeden hafiftir, çünkü yalnız aynı ev yuvasına düşen anahtarları etkiler.

Karesel yoklamanın ikinci zayıflığı, her yuvayı denemeyebilmesidir. N = 13 ve h = 5 için i = 0, 1, …, 12 değerleri sırasıyla 5, 6, 9, 1, 8, 4, 2, 2, 4, 8, 1, 9, 6 yuvalarını verir. On üç denemede yalnız yedi farklı yuva görülür: {1, 2, 4, 5, 6, 8, 9}. Bu yuvaların hepsi doluysa tabloda altı boş yuva olsa bile anahtar yer bulamaz. Bu sorunu önlemek için şu sonuç kullanılır.

N = 13 için teorem ilk yedi denemenin (i = 0 … 6) farklı olduğunu söyler. Yukarıda bulunan yedi farklı yuva tam olarak bunlardır; yedinci denemeden sonra yuvalar tekrarlanmaya başlar. Bu yüzden karesel yoklama kullanan tablolarda N asal seçilir ve λ 0,5'in altında tutulur.

12.4.4Çift hash

İkincil kümelenmenin nedeni, yoklama adımının yalnız ev yuvasına bağlı olmasıdır. Çift hash, adımı anahtarın kendisine bağlar. Bunun için ikinci bir hash fonksiyonu h₂ kullanılır ve i. deneme

h(k, i) = (h(k) + i · h₂(k)) mod 13, h₂(k) = 7 − (k mod 7)

formülüyle bulunur. k mod 7 0 ile 6 arasında olduğundan h₂(k) 1 ile 7 arasındadır; asla 0 olmaz. Adım 0 olsaydı anahtar hep ev yuvasını yoklar ve hiç ilerleyemezdi. Kod şöyledir:

// yerlestir(k): çift hash, N = 13
int h = k % 13;
int d = 7 - k % 7;             // adım: 1…7
for (int i = 0; i < 13; i++) {
  int j = (h + i * d) % 13;
  if (tablo[j] == null) {      // boş mu?
    tablo[j] = k;
    break;
  }                            // dolu: i++
}

d = 7 - k % 7 adımdır. Java'da % çıkarmadan önce yapıldığı için ifade 7 − (k mod 7) anlamına gelir. Döngünün geri kalanı öteki yöntemlerle aynıdır; yalnız j = (h + i * d) % 13 hesabı değişir.

Ev yuvası 5 olan üç anahtara bakalım. 18 ilk denemede yerleşir. 44'ün adımı 5'tir ve 10. yuvaya sıçrar. 31'in adımı 4'tür: önce 5'e, sonra 9'a, sonra 5 + 8 = 13, yani 0. yuvaya gider. Aynı ev yuvasından başlayan anahtarlar farklı adımlarla ilerler ve birbirinin yolunu tıkamaz. 44 artık 6. yuvayı işgal etmediği için 32 de ev yuvasına ilk denemede yerleşir. Toplam yoklama 11'e iner.

Çift hash ikincil kümelenmeyi tamamen ortadan kaldırmaz. İki anahtar hem aynı ev yuvasına hem aynı adımı alıyorsa yine aynı diziyi izler. Örnekte 59, 31 ve 73'ün adımı 4'tür; ama ev yuvaları farklı olduğu için birbirlerini etkilemezler. İki fonksiyonun birlikte çakışma olasılığı, tek fonksiyonunkinden çok daha küçüktür.

Adımın neden asal bir N ile birlikte kullanıldığını şu sonuç açıklar.

Örnekte N = 13 asaldır ve adımlar 1 ile 7 arasındadır; her anahtar gerekirse bütün yuvaları dener. N asal olmasaydı, örneğin N = 12 ve adım 4 olsaydı, yoklama yalnız h, h + 4, h + 8 yuvalarını gezer ve tabloda boş yer olsa bile onu bulamayabilirdi.

12.4.5Silme: “silindi” işareti

Açık adreslemede silme, ilk bakışta göründüğü kadar basit değildir. Doğrusal yoklama sonrası tabloyu ele alalım: 2'de 41, 5'ten 11'e kadar sırasıyla 18, 44, 59, 32, 22, 31, 73 vardır. 44 silinmek isteniyor.

Önce 44 bulunur: h(44) = 5, 5. yuvada 18 vardır, eşit değildir; 6. yuvada 44 bulunur. Akla gelen ilk çözüm, 6. yuvayı null yapmaktır. Ama bu tabloyu bozar. 32'yi arayalım: h(32) = 6, yani arama 6. yuvadan başlar. Yuva boştur. Açık adreslemede boş yuva, “aranan anahtar buradan ötede olamaz” demektir. Çünkü 32 eklenirken bu yuva boş olsaydı 32 buraya yerleşirdi. Arama “32 yok” cevabını verir. Oysa 32 tabloda, 8. yuvadadır.

Sorun, silinen yuvanın başka anahtarların yoklama dizisinin bir halkası olmasıdır. 32, 6 ve 7 dolu olduğu için 8'e yerleşmişti. 6'yı boşaltmak, 32'ye giden yolu koparır. Doğru çözüm yuvayı boşaltmak yerine onu özel bir işaretle işaretlemektir.

Şeklin son parçası işaretin ekleme sırasındaki rolünü gösterir. 57 eklenirken arama 5. yuvadan başlar. 6. yuvadaki ✗, ilk uygun yuva olarak not edilir. Ama arama orada durmaz, çünkü 57 tabloda daha ileride bir yerde zaten olabilir. Arama gerçekten boş bir yuvaya (12) varınca 57'nin tabloda olmadığı kesinleşir. Ancak o zaman 57, not edilen ilk uygun yuvaya, yani 6'ya yazılır. Böylece silinen yuvanın yeri boşa gitmez.

Silindi işaretlerinin bir bedeli vardır. İşaretler tabloda birikir ve aramalar onları dolu yuva gibi geçmek zorundadır. Çok sayıda silme yapılan bir tabloda yoklama dizileri, gerçek öğe sayısı az olsa bile uzar. Bu yüzden işaretli yuvaların sayısı da izlenir ve gerektiğinde tablo baştan oluşturulur. Yeniden oluşturma bütün işaretleri temizler.

12.4.6Kod: yuvaBul()

Açık adreslemede arama ve ekleme aynı yoklamayı yapar. Bu ortak adım, yuvaBul adlı tek bir yardımcı metotta toplanabilir. Metot hem anahtarın bulunup bulunmadığını hem de bulunamadıysa nereye eklenebileceğini tek bir tam sayıyla bildirir.

private int yuvaBul(int k) {       // findSlot
  int h = Math.floorMod(k, N), uygun = -1;
  for (int i = 0; i < N; i++) {
    int j = (h + i) % N;           // doğrusal
    if (tablo[j] == null ||
        tablo[j] == SILINDI) {
      if (uygun == -1) uygun = j;
      if (tablo[j] == null) break;
    } else if (tablo[j].anahtar == k)
      return j;                    // bulundu
  }
  return -(uygun + 1);        // yok: yer kodu
}

Metodun parçaları şunlardır:

• h ev yuvasıdır; Math.floorMod negatif anahtarları da güvenle yuvaya çevirir. uygun, şimdiye kadar görülen ilk boş ya da silinmiş yuvayı tutar. Başta henüz böyle bir yuva görülmediği için −1'dir.
• Döngü doğrusal yoklama yapar: j = (h + i) % N.
• Yuva boşsa (null) ya da silinmişse (SILINDI) ve henüz uygun yuva yoksa, bu yuva uygun olarak not edilir. Yuva gerçekten boşsa döngü break ile biter: anahtar bundan öteye yerleşmiş olamaz. Silinmiş yuvada ise döngü devam eder.
• Yuva doluysa ve anahtarı aranan anahtarsa yuvanın indisi döndürülür. Dönüş değeri 0 ya da pozitiftir ve “bulundu” anlamına gelir.
• Döngü anahtarı bulamadan biterse -(uygun + 1) döndürülür. Bu değer her zaman negatiftir ve “bulunamadı” anlamına gelir. İçinde eklenecek yuvanın bilgisi de vardır.

Neden yalnız -uygun değil de -(uygun + 1)? uygun = 0 olabilir. O zaman -uygun da 0 olurdu ve “0. yuvada bulundu” sonucundan ayırt edilemezdi. 1 eklemek bütün “bulunamadı” sonuçlarını kesin olarak negatif yapar: 0. yuva −1, 6. yuva −7 olarak kodlanır. Yuvayı geri almak için −(j + 1) hesaplanır. Java kütüphanesindeki Arrays.binarySearch da bulunamayan öğenin ekleneceği yeri aynı yöntemle bildirir.

yuvaBul üzerine arama ve ekleme birer satırda kurulur:

• getir(k): j = yuvaBul(k). j ≥ 0 ise tablo[j].deger, değilse null döndürülür.
• yerlestir(k, v): j ≥ 0 ise o yuvadaki değer güncellenir. Değilse yeni çift tablo[−(j + 1)] yuvasına yazılır.

Karesel yoklama ya da çift hash istenirse yalnız j'nin hesabı değişir: karesel için (h + i*i) % N, çift hash için (h + i*h2) % N. Metodun geri kalanı aynı kalır.

Kodda örtük bir varsayım vardır: tablo hiçbir zaman tamamen dolmaz. λ < 1 tutulur ve gerekince tablo büyütülür. Bu yüzden döngü her zaman en az bir boş ya da silinmiş yuva görür ve uygun −1'de kalmaz. Tablo tamamen dolu olsaydı uygun = −1 kalır ve dönüş değeri -(−1 + 1) = 0 olurdu; bu da yanlışlıkla “0. yuvada bulundu” diye okunurdu.

Maliyet. Her yoklama O(1)'dir; toplam süre yoklama sayısıyla orantılıdır. En kötü durumda bütün yuvalar denenir: O(N). Yük faktörü düşük tutulursa beklenen yoklama sayısı küçük bir sabittir.

12.4.7Kod izleme: yuvaBul()

Doğrusal yoklama sonrası tabloda 44 silinmiş, 6. yuvada ✗ olsun. Tablo: 2 → 41, 5 → 18, 6 → ✗, 7 → 59, 8 → 32, 9 → 22, 10 → 31, 11 → 73; geri kalan yuvalar boş. Önce yuvaBul(32), sonra yuvaBul(57) çağrılıyor.

Arama ✗ işaretini gördüğünde durmaz. 6'yı yalnız “gerekirse buraya eklenir” diye not eder ve devam eder. 8. yuvada 32 bulunur, metot 8 döndürür. getir bu durumda tablo[8].deger'i döndürür. ✗ işareti arama zincirini koparmamıştır.

yuvaBul(57) sekiz yoklama yapar. 6'daki ✗ ilk uygun yuva olarak not edilir. 12. yuva da boştur, ama if (uygun == -1) koşulu yanlış olduğu için uygun değişmez; ilk uygun yuva korunur. Gerçekten boş yuva görüldüğü için döngü biter: 57 bundan öteye yerleşmiş olamaz. Metot −7 döndürür. yerlestir bu sonucu şöyle kullanır: j = −7 < 0, öyleyse tablo[−(j + 1)] = tablo[6] = 57. Silinmiş yuva yeniden kullanılmıştır.

Ekleme 6'yı kullanmasaydı, yani 57'yi 12. yuvaya yazsaydı, tablo yine doğru çalışırdı. Ama 6'daki ✗ tabloda kalır ve her aramada fazladan bir yoklamaya yol açardı. İlk uygun yuvayı kullanmak, silinmiş yuvaları zamanla temizler ve yoklama dizilerini kısa tutar.

12.4.8Üç yoklama yönteminin karşılaştırması

Aynı sekiz anahtarın üç yöntemle eklenmesinden çıkan sayılar Tablo 12.18'de toplanmıştır.

Bu tek örnek genel eğilimi doğru yansıtır. Doğrusal yoklama kümelenmeye en açık yöntemdir. Karesel yoklama birincil kümelenmeyi kırar, ikincil kümelenmeyi bırakır. Çift hash iki tür kümelenmeyi de büyük ölçüde önler. Buna karşın pratikte doğrusal yoklama hâlâ çok kullanılır. Ardışık yuvaları yoklamak önbellek açısından en ucuz işlemdir ve yük faktörü düşük tutulursa kümeler kısa kalır. Çift hash ise her anahtar için ikinci bir hash hesabı ister ve yuvalar arasında uzun sıçramalar yapar.

Üç yöntemi farklı anahtarlarla denemek için sunumdaki deneme alanı ya da açık adresleme simülatörü kullanılabilir. Simülatör N = 11 yuvalı bir tabloda h(k) = k mod 11 ile çalışır; her ekleme ve aramada denenen yuvaları, silindi işaretlerini ve yük faktörünü gösterir.

12.5Performans ve uygulamalar

Hash tablosunun ortalama O(1) vaadi bir koşula bağlıdır: tablo fazla dolmamalıdır. Bu kesim doluluğun maliyete etkisini sayılarla gösterir. Ardından tablo dolarken ne yapıldığını, Java HashMap'in bu işleri nasıl çözdüğünü ve hash tablolarının tipik kullanım yerlerini anlatır.

12.5.1Yük faktörü

Yük faktörü λ = n / N, çift sayısının kova sayısına oranıdır. Burada n, koddaki buyukluk'tur; N ise kova ya da yuva sayısıdır. İki çakışma çözümünde λ'nın anlamı farklıdır:

• Zincirlemede λ, zincirlerin ortalama uzunluğudur. λ > 1 olabilir; tablo yine çalışır, ama işlemler yavaşlar. Beklenen maliyet O(1 + λ)'dır.
• Açık adreslemede λ ≤ 1 zorunludur, çünkü her yuvada en çok bir çift vardır. λ 1'e yaklaştıkça boş yuva bulmak zorlaşır ve yoklama sayısı hızla büyür.

Doğrusal yoklamada beklenen yoklama sayısını Donald Knuth hesaplamıştır. Tablo büyük ve hash fonksiyonu iyi olduğunda:

başarılı arama: ½ (1 + 1/(1 − λ)) başarısız arama: ½ (1 + 1/(1 − λ)²)

Başarısız arama, boş bir yuvaya varana kadar sürer. Ekleme de aynı yolu izlediği için bir eklemenin maliyeti, başarısız bir aramanınkiyle aynıdır. Formüllerdeki 1 − λ terimi boş yuvaların oranıdır. Boş yuvalar azaldıkça payda küçülür ve değer büyür. Başarısız aramada payda karesi alındığı için büyüme çok daha hızlıdır.

Tablo ve şekil iki sonucu açıkça gösterir. Birincisi, açık adreslemede λ = 0,5'e kadar maliyet düşüktür, ama sonrasında hızla artar. Tablonun %50'den %80'e dolması başarısız aramayı 2,5'ten 13 yoklamaya, yani yaklaşık beş katına çıkarır. %90'da ortalama 50 yoklama gerekir. İkincisi, zincirlemede maliyet λ ile yalnız doğrusal artar ve yüksek yük faktörlerinde bile kabul edilebilir kalır.

Bu yüzden pratikte iki farklı eşik kullanılır. Zincirlemede λ ≈ 0,75 yaygın bir sınırdır; Java HashMap da bu değeri kullanır. Açık adreslemede genellikle λ ≤ 0,5 tutulur. Eşik aşılınca tablo yaklaşık iki katına büyütülür.

12.5.2Yeniden boyutlandırma

Yük faktörü eşiği aşınca tablo büyütülür. Java'da dizinin boyu değiştirilemez; büyütme, daha büyük yeni bir dizi ayırmak ve bütün çiftleri oraya taşımak demektir. Bu işleme yeniden boyutlandırma (resizing) denir. Taşıma sırasında her anahtar yeniden hash'lenir (rehashing), çünkü indis h(k) mod N ile hesaplanır ve N değişmiştir.

Şekil 12.22 bir örneği adım adım gösterir. 5 kovalı zincirlemeli bir tabloya 12, 7, 20 ve 33 eklenmiştir. 12 ile 7 ikisi de 2. kovaya düşer ve bir zincir oluşturur. Dördüncü eklemeden sonra λ = 4/5 = 0,80 olur ve 0,75 eşiği aşılır. Tablo 11 kovaya büyütülür. Her anahtar k mod 11 ile yeni kovasına gider: 20 → 9, 7 → 7, 12 → 1, 33 → 0. Büyütmeden sonra 7 ile 12 ayrı kovalardadır; tabloda hiç çakışma kalmamıştır ve λ = 4/11 ≈ 0,36'dır.

Yeni kapasite neden tam iki kat (10) değil de 11'dir? Bölme yöntemi asal bir N ile daha iyi dağılım verir (12.2.2). Bu yüzden bazı gerçeklemeler eski boyun iki katından büyük ilk asal sayıyı seçer. Aşağıdaki kod daha basit bir kural kullanır: 2N + 1. Bu sayı her zaman tektir ve 5 için 11, yani asaldır; ama her zaman asal değildir (örneğin 7'den 15 elde edilir).

Bir yeniden boyutlandırma n çiftin hepsini taşıdığı için tek başına O(n) sürer ve pahalıdır. Ama sık yapılmaz. Kapasite her seferinde yaklaşık iki katına çıktığından, bir büyütmeden sonra yeniden büyütme gerekene kadar en az o kadar yeni ekleme yapılır. Pahalı işlemin maliyeti bu eklemelere dağıtılınca ekleme başına sabit bir pay düşer.

Teorem tek bir eklemenin hızlı olduğunu söylemez. Büyütmeyi tetikleyen ekleme O(n) sürer. Ortalama hızın yettiği çoğu programda bu sorun değildir. Her işlemin kısa sürmesi gereken gerçek zamanlı sistemlerde ise büyütme parça parça, birkaç eklemeye yayılarak yapılabilir.

12.5.3Kod izleme: yenidenBoyutlandir()

Zincirlemeli HashTablosu sınıfına eklenecek büyütme metodu şöyledir:

private void yenidenBoyutlandir() {
  HashDugumu[] eski = kovalar;
  int yeniN = 2 * eski.length + 1;
  kovalar = new HashDugumu[yeniN];
  buyukluk = 0;  kovaSayisi = yeniN;
  for (HashDugumu ilk : eski) {   // her kova
    while (ilk != null) {
      yerlestir(ilk.anahtar, ilk.deger);
      ilk = ilk.sonraki;
    }
  }
}

Metodun adımları şunlardır:

• eski = kovalar: eski dizi bir değişkende saklanır. Yeni dizi ayrıldıktan sonra eski zincirlere ancak bu değişken üzerinden ulaşılabilir.
• yeniN = 2 * eski.length + 1: yaklaşık iki kat ve tek bir kapasite hesaplanır.
• kovalar = new HashDugumu[yeniN]: alan artık boş yeni diziyi gösterir. getKovaIndisi kovalar.length'i kullandığı için bundan sonraki her indis hesabı yeni boya göre yapılır.
• buyukluk = 0: yerlestir her çifti eklerken buyukluk'u bir artırır. Sayaç sıfırlanmazsa çiftler iki kez sayılırdı.
• Dış döngü eski dizinin her kovasını, iç döngü o kovadaki zinciri gezer. Her düğüm için yerlestir(ilk.anahtar, ilk.deger) çağrılır; anahtar yeni tabloda yeni kovasına yerleşir.

Metot eski düğümleri yeniden kullanmaz; yerlestir her çift için yeni bir düğüm oluşturur. Eski dizi ve düğümleri artık hiçbir referansla gösterilmediğinde çöp toplayıcı onları temizler. Daha verimli bir gerçekleme düğümleri yeni zincirlere doğrudan taşıyabilir; ama yukarıdaki kod daha kısa ve anlaşılırdır.

Önceki örnekteki tabloyu izleyelim. Eski tabloda 0. kova → 20, 2. kova → 7 → 12, 3. kova → 33 vardır (7, 12'den sonra eklendiği için zincirin başındadır).

Eski 2. kovadaki zincir, iç döngünün iki tur dönmesine yol açar: önce 7, ilk = ilk.sonraki ile sonra 12 taşınır. Aynı eski kovada olan iki anahtar yeni tabloda 7. ve 1. kovalara ayrılmıştır. Sonunda dört çiftin hepsi taşınmış ve buyukluk yine 4 olmuştur. λ = 4/11 ≈ 0,36'dır.

Maliyet. Dış döngü N_eski kez döner, iç döngüler toplam n kez döner. Her yerlestir yeni tabloda ortalama O(1)'dir. Toplam süre O(N + n)'dir; eşik sayesinde N, n ile orantılı olduğundan bu O(n) demektir. Taşıma sırasında eski ve yeni dizi bir süre birlikte bellekte durur.

12.5.4Karmaşıklık karşılaştırması

Eşleme ADT'sinin farklı gerçeklemelerini bir arada karşılaştıralım.

Yıldızlı hücrenin açıklaması şudur: sırasız listede yeni çifti eklemek tek başına O(1)'dir, ama eşlemede anahtarlar tekil olduğundan önce anahtarın zaten var olup olmadığı denetlenir. Bu denetim bütün listeyi tarar ve O(n) sürer. Sıralı dizide arama ikili aramayla O(log n)'dir, ama ekleme ve silme öğeleri kaydırmak zorunda olduğu için O(n)'dir.

Hash tablosu için üç noktanın altını çizmek gerekir:

• En kötü durum. Bütün anahtarlar aynı kovaya düşerse tek bir uzun zincir ya da tek bir büyük küme oluşur ve işlemler O(n) sürer. Ortalama O(1), iyi bir hash fonksiyonuna ve sınırlı yük faktörüne bağlıdır.
• Alan. Toplam alan O(n + N)'dir: kova dizisi ve çiftler. Zincirlemede her düğüm bir referans fazlası taşır. Yük faktörü sınırlı tutulduğu için N = O(n)'dir ve alan O(n)'dir.
• Sıra yok. Hash tablosu anahtarları sırasız tutar. En küçük anahtarı bulmak, anahtarları sıralı listelemek ya da “50 ile 100 arasındaki anahtarlar” gibi aralık soruları bütün tabloyu gezmeyi gerektirir: O(n) ve sıralama gerekiyorsa daha fazlası. Sıralı erişim gereken işlerde arama ağaçları tercih edilir.

12.5.5Java HashMap içeride nasıl çalışır?

Java'nın java.util.HashMap sınıfı, bu bölümde anlatılan fikirleri birkaç akıllı ayrıntıyla birleştirir.

• Ayrı zincirleme ve 2'nin kuvveti kadar kova. HashMap çakışmaları zincirlemeyle çözer. Kova sayısı n her zaman 2'nin bir kuvvetidir; varsayılan değer 16'dır. Bu sayede indis bölme yerine hızlı bir bit işlemiyle bulunur: h & (n − 1). n = 16 = 2⁴ iken n − 1 = 15'in ikili gösterimi 1111'dir; & 15 sayının yalnız son dört bitini bırakır. Bu, negatif olmayan sayılarda h mod 16 ile aynı sonucu verir ve negatif kodlarda da 0 … 15 aralığında kalır.
• Bit karıştırma. Maske yalnız alt bitleri gördüğü için üst bitleri farklı, alt bitleri aynı olan anahtarlar hep aynı kovaya düşerdi. HashMap bu yüzden indisten önce h ^ (h >>> 16) hesaplar. >>> 16, sayının üst 16 bitini alt yarıya kaydırır; ^ (XOR) bu bitleri alt bitlerle karıştırır. Böylece üst bitler de indisi etkiler.
• λ = 0,75 eşiği. Öğe sayısı 0,75 · n'yi aşınca kova dizisi iki katına büyür ve düğümler yeni kovalara dağıtılır. 16 kovalı tabloda eşik 12'dir; 13. öğe eklenince tablo 32 kovaya çıkar. Kova sayısı 2'nin kuvveti olduğu için büyütmede her düğüm ya eski indisinde kalır ya da eski indis + eski boy konumuna gider; hangisine gideceğini tek bir bit belirler.
• Ağaçlaşma (Java 8 ve sonrası). Bir zincir 8 düğümü aşarsa ve tabloda en az 64 kova varsa zincir dengeli bir arama ağacına, bir kırmızı-siyah ağaca çevrilir. O kovadaki arama en kötü durumda O(n)'den O(log n)'e iner. Tablo 64 kovadan küçükse ağaca çevirmek yerine tablo büyütülür; küçük tabloda uzun zincirin daha olası nedeni kapasitenin azlığıdır.

Şekildeki 16 kovalı tablo bu ayrıntıları bir arada göstermek için çizilmiştir. Gerçek bir 16 kovalı HashMap'te 9. kovadaki uzun zincir ağaca çevrilmez; 64 kova sınırına ulaşılmadığı için tablo büyütülür.

HashMap'in gezinme sırası da sık sorulan bir konudur. keySet() ya da for döngüsüyle gezinme, kovaların sırasını izler; anahtarların ekleme sırasını değil. Ayrıca tablo büyüdüğünde düğümler kovalar arasında yer değiştirdiği için sıra da değişebilir. Ekleme sırası gerekiyorsa LinkedHashMap, anahtarların büyüklük sırası gerekiyorsa TreeMap kullanılır. Yalnız anahtarların varlığıyla ilgilenen işler için aynı hash tablosu yapısını kullanan HashSet vardır.

12.5.6Kod izleme: indis(k, 16)

Bit karıştırmanın etkisini görmek için HashMap'in indis hesabını taklit eden kısa bir metot yazalım. main üç anahtarın 16 kovalı tablodaki indisini yazdırır.

static int indis(Object key, int n) { // n = 2^k
  int h = key.hashCode();
  int m = h ^ (h >>> 16); // üst bitleri karıştır
  return m & (n - 1); // alt k bit
}
// main:
for (int k : new int[]{1, 65537, 131073})
  System.out.println(k + " -> " + indis(k, 16));

key.hashCode(), Integer anahtarlar için sayının kendisidir. h >>> 16 işlemi sayıyı 16 bit sağa kaydırır ve soldan sıfır doldurur; üst yarı alt yarıya iner. h ^ (h >>> 16), alt 16 biti üst 16 bitle XOR'lar; üst 16 bit ise değişmez. Son olarak m & (n − 1) alt 4 biti alır.

Seçilen üç anahtar özel olarak hazırlanmıştır: 1, 65537 ve 131073. Onaltılık (hexadecimal) gösterimde bunlar 0x00000001, 0x00010001 ve 0x00020001'dir. Alt 16 bitleri aynıdır (…0001); yalnız üst bitleri farklıdır. Karıştırma olmasaydı h & 15 üçü için de 1 verirdi.

Anahtar 1'in üst yarısı sıfırdır; kaydırma 0 verir, XOR sayıyı değiştirmez ve indis 1 olur. 65537'nin üst yarısı 1'dir. Alt yarıdaki 0001 ile kaydırılmış 0001 XOR'lanınca alt bitler 0000 olur; m = 65536, indis 0'dır. 131073'ün üst yarısı 2'dir (0010). 0001 ^ 0010 = 0011; m = 131075, indis 3'tür. Program şunları yazdırır:

1 -> 1
65537 -> 0
131073 -> 3

Karıştırma olmasaydı üç anahtar da 1. kovada çakışırdı; karıştırma ile 1, 0 ve 3 numaralı kovalara dağılmışlardır. Bunun maliyeti yalnız bir kaydırma ve bir XOR işlemidir. Hash kodu her zaman küçük olan anahtarlarda (h < 65536) üst yarı sıfır olduğu için karıştırma sonucu değiştirmez; bu anahtarlarda alt bitler zaten anahtarın bütün bilgisini taşır.

12.5.7Hash tablolarının kullanım alanları

“Bu anahtar var mı, varsa değeri ne?” sorusunun hızla cevaplanması gereken her yerde hash tablosu kullanılır. Birkaç tipik örnek:

• Sözlük ve yazım denetimi. Kelime → anlam eşlemesi bir hash tablosunda tutulur. Yazım denetleyicisi her kelime için “bu kelime sözlükte var mı?” diye sorar; sorunun cevabı ortalama sabit sürede gelir.
• Veritabanları. Hash indisleri, anahtara göre kayda hızlı erişim sağlar. İki tabloyu ortak bir sütuna göre birleştiren hash join algoritması, tablolardan birini bellekte bir hash tablosuna koyar ve ötekinin her satırı için eşini bu tabloda arar.
• Bellek önbelleği. Pahalı bir hesabın ya da sorgunun sonucu, bir URL ya da sorgu metni anahtarıyla saklanır. Aynı istek tekrar gelince sonuç hesaplanmadan tablodan alınır. Redis ve memcached gibi sistemler bu fikre dayanır.
• Web tarayıcı geçmişi. Ziyaret edilen adres → son ziyaret zamanı. Tarayıcı “bu bağlantı daha önce açıldı mı?” sorusuna göre bağlantının rengini değiştirir.
• Çerez ve oturum yönetimi. Çerez adı → değer; oturum kimliği → kullanıcı bilgisi. Sunucu her istekte oturum kimliğiyle kullanıcıyı bulur.
• Derleyiciler. Sembol tablosu, değişken adlarını tip, adres ve kapsam bilgisine eşler. Derleyici kodda bir ad gördüğünde onu bu tabloda arar.

Java programlarında bu işlerin çoğu HashMap ve HashSet ile yapılır. Bir dizideki öğelerin kaç kez geçtiğini saymak, iki listenin ortak öğelerini bulmak ya da tekrar eden öğeleri ayıklamak gibi küçük görevler de hash tablosuyla O(n) beklenen sürede çözülür. Bir sonraki uygulama bunun tipik bir örneğidir.

12.5.8Uygulama: ikiToplam()

Bir tam sayı dizisinde, toplamı verilen bir hedefe eşit olan iki öğenin indislerini bulmak isteyelim. Kaba kuvvet çözümü bütün (i, j) çiftlerini dener: iç içe iki döngü, O(n²) zaman. Hash tablosu bu işi tek geçişte yapar.

static int[] ikiToplam(int[] a, int hedef) {
  Map<Integer, Integer> gor = new HashMap<>();
  for (int i = 0; i < a.length; i++) {
    int ek = hedef - a[i]; // gereken eş
    if (gor.containsKey(ek))
      return new int[]{gor.get(ek), i};
    gor.put(a[i], i); // değer -> indis
  }
  return null; // çift yok
}

Fikir şudur: a[i]'ye bakarken, onunla toplamı hedefi veren eş ek = hedef − a[i]'dir. Bu eş daha önce görüldüyse çözüm bulunmuştur. Daha önce görülen değerler gor eşlemesinde, değer → indis biçiminde tutulur. containsKey(ek) sorusu ortalama O(1)'de cevaplanır. Eş yoksa a[i] eşlemeye eklenir; böylece sonraki öğeler onu eş olarak bulabilir.

İlk dört adımda aranan eşlerin (4, 9, 1, 7) hiçbiri daha önce görülmemiştir; her değer indisiyle eşlemeye eklenir. Beşinci adımda a[4] = 7 için gereken eş 5'tir ve 5, 3. indiste görülmüştür. Metot [gor.get(5), 4] = [3, 4] döndürür: a[3] + a[4] = 5 + 7 = 12.

Kontrolün eklemeden önce yapılması önemlidir. Önce eklenseydi, hedefin yarısına eşit bir öğe (örneğin hedef 12 iken 6) kendisini eş olarak bulurdu. Ayrıca aynı değerin iki kopyası doğru eşleşir: ilk kopya eşlemeye girer, ikinci kopya onu bulur.

Maliyet. Dizi bir kez gezilir. Her adımda ortalama O(1) bir arama ve bir ekleme yapılır. Toplam beklenen süre O(n), eşlemenin kullandığı ek bellek O(n)'dir. Kaba kuvvet ek bellek kullanmaz ama O(n²) sürer. Hash tablosu burada belleği zamana çevirmiştir; bu takas hash tablosu kullanımının tipik biçimidir.

12.5.9Uygulama: okul numarası için hash fonksiyonu

Genel amaçlı hash fonksiyonları her türlü anahtarla çalışmak zorundadır. Anahtarın yapısı biliniyorsa bu bilgiyle çok daha iyi bir fonksiyon tasarlanabilir. Bu uygulamada amaç, okul numaralarını 1000 öğelik bir diziye çakışmasız dağıtmaktır.

Numaralar ab070c0de biçimindedir; örneğin 210707003. Dokuz hanenin anlamı şöyledir:

• ab: kayıt yılı, 20 ile 24 arasında;
• c: bölüm kodu, 6 ya da 7;
• de: o yıl o bölümdeki kayıt sırası, 00 ile 99 arasında (iki hane);
• öteki haneler (“070” ve “0”) bütün numaralarda aynıdır ve bilgi taşımaz.

Bu biçimdeki bütün numaraları 0–999 aralığına dağıtan fonksiyon şudur:

hash(ab070c0de) = ((ab − 20) × 100 + (c − 6) × 500 + de) mod 1000

Fonksiyonun her terimi bir işe yarar. ab − 20, 0 ile 4 arasındadır ve 100'lük bir blok seçer: 2020 kaydı 0–99, 2021 kaydı 100–199 bloğuna düşer. c − 6, 0 ya da 1'dir; 7 kodlu bölüm 500 kaydırılır. de, 0–99 arasındadır ve bloğun içindeki yeri verir.

Olası numara sayısı 5 yıl × 2 bölüm × 100 sıra = 1000'dir ve fonksiyon bunların her birini farklı bir indise gönderir. Bölüm 6'nın numaraları 0–499, bölüm 7'ninkiler 500–999 aralığını doldurur; her yıl kendi 100'lük bloğunu kullanır. Hiç çakışma yoktur. Bu tür fonksiyona mükemmel hash (perfect hash) denir. Mükemmel hash ancak anahtar kümesi önceden bilindiğinde mümkündür; burada bu bilgiyi numaranın biçimi sağlar.

Fonksiyonun Java kodu şöyledir:

// s: "ab070c0de" biçiminde okul numarası
public int calculateHash(String s) {
  int ab = Integer.parseInt(s.substring(0, 2));
  int c  = Integer.parseInt(s.substring(5, 6));
  int de = Integer.parseInt(s.substring(7, 9));
  int yil   = (ab - 20) * 100;   // yıl bloğu
  int bolum = (c - 6) * 500;     // bölüm: 0/500
  return (yil + bolum + de) % 1000;
}

substring(başlangıç, bitiş) metodu başlangıç dahil, bitiş hariç karakterleri döndürür. s.substring(0, 2) 0. ve 1. karakterleri, yani yılı verir. s.substring(5, 6) yalnız 5. karakteri, yani bölüm kodunu verir. s.substring(7, 9) 7. ve 8. karakterleri, yani kayıt sırasını verir. Integer.parseInt bu parçaları tam sayıya çevirir; "03" 3 olur. Kalan satırlar formülü adım adım hesaplar.

Metot sabit sayıda işlem yapar; maliyeti O(1)'dir. Ama yalnız biçime uyan numaralar için doğrudur. Biçime uymayan bir girdi, örneğin yılı 25 olan 250707001, (500 + 500 + 1) mod 1000 = 1 verir ve 200706001 numarasıyla çakışır. Bölüm kodu 8 olan bir numara 1000'i aşan bir toplam üretir ve başka bir numaranın indisine sarılır. Yılı 20'den küçük bir numara negatif sonuç da verebilir. Gerçek bir programda girdi önce doğrulanmalı, biçim dışı numaralar reddedilmeli ya da genel amaçlı bir hash tablosuna yönlendirilmelidir.

12.6Sık yapılan hatalar

Hash tablosu kullanan programlarda aynı hatalar sık sık tekrarlanır. Bunların çoğu derleme sırasında yakalanmaz ve ancak belirli girdilerde ortaya çıkar. Tablo 12.26 bölüm boyunca anlatılan hataları bir arada verir.

Değiştirilebilir anahtar hatası özellikle sinsidir. Bir ArrayList anahtar olarak eşlemeye konup sonra listeye öğe eklenirse listenin hashCode()'u değişir. Örneğin [1, 2] listesinin hash kodu 994'tür; listeye 3 eklenince 30817 olur. get yeni kodla başka bir kovaya bakar ve null döndürür. Oysa çift hâlâ tablodadır ve size() 1'dir. Çift ne bulunabilir ne de silinebilir; tabloda erişilemez bir çöp olarak kalır.

Hataların çoğunun ortak kökü, hash tablosunun iki varsayımına dayanmasıdır: anahtarın hash kodu tabloda kaldığı sürece değişmez, ve eşit anahtarların hash kodu aynıdır. Bu iki varsayımdan biri bozulduğunda tablo hata vermez; yalnız yanlış cevap verir. Hash tablosuyla çalışan kodda ilk denetlenecek yer, anahtar sınıfının equals ve hashCode metotlarıdır.

12.7Özet

• Eşleme (map), tekil anahtarlardan değerlere bir eşlemedir. Temel işlemleri put, get ve remove'dur; var olan bir anahtarla yapılan put değeri günceller ve eski değeri döndürür. Eşleme bir ADT'dir; hash tablosu onu gerçeklemenin en yaygın yoludur.
• Doğrudan adresleme, her olası anahtara bir hücre ayırır ve O(1)'de çalışır, ama büyük anahtar uzaylarında belleği israf eder ve tam sayı olmayan anahtarlarla çalışmaz.
• Hash fonksiyonu, anahtarı önce bir hash koduna, sonra sıkıştırma ile 0 … N − 1 aralığında bir indise çevirir. İyi bir fonksiyon belirleyici, hızlı ve düzgün dağılımlıdır ve anahtarın tamamını kullanır. Bölme yönteminde N asal seçilir; MAD yöntemi ((a·k + b) mod p) mod N'dir. Java'da indis için Math.floorMod(h, N) kullanılır.
• equals/hashCode sözleşmesi: eşit nesnelerin hash kodu aynı olmalıdır; aynı hash kodu eşitlik anlamına gelmez. Kova seçimini hashCode, gerçek eşitliği equals belirler. İkisi birlikte ezilir.
• Çakışmalar, anahtar uzayı tablodan büyük olduğu sürece kaçınılmazdır (güvercin yuvası ilkesi).
• Ayrı zincirlemede her kova bir bağlı liste tutar; yeni düğüm başa eklenebilir. İşlemler O(1 + zincir uzunluğu)'dur; beklenen maliyet O(1 + λ)'dır ve λ > 1 olabilir. Silmede önceki düğüm izlenir.
• Açık adreslemede çiftler dizinin kendisinde durur ve λ ≤ 1'dir. Doğrusal yoklama birincil kümelenmeye, karesel yoklama ikincil kümelenmeye yol açar; karesel yoklama asal N ve λ < 1/2 ile boş yuva bulmayı güvenceye alır. Çift hash, adımı anahtara bağlayarak kümelenmeyi azaltır; adım sıfır olmamalı ve N ile aralarında asal olmalıdır. Silmede yuvaya silindi işareti konur.
• Yük faktörü λ = n/N'dir. Doğrusal yoklamada başarısız arama ortalama ½(1 + 1/(1 − λ)²) yoklama ister: λ = 0,5'te 2,5, λ = 0,8'de 13. Eşik aşılınca (zincirlemede ≈ 0,75, açık adreslemede ≈ 0,5) tablo yaklaşık iki katına büyütülür ve bütün anahtarlar yeniden hash'lenir. Büyütme tek başına O(n), ekleme başına amortize O(1)'dir.
• Hash tablosunda ekleme, arama ve silme ortalama O(1), en kötü O(n); alan O(n + N)'dir. Tablo sıra tutmaz.
• Java HashMap: zincirleme, 2'nin kuvveti kadar kova (varsayılan 16), h ^ (h >>> 16) ile bit karıştırma ve & (n − 1) maskesi, 0,75 eşiğinde iki katına büyüme, 8'i aşan zincirlerde (en az 64 kova varsa) kırmızı-siyah ağaç.
• Anahtar yapısı biliniyorsa mükemmel hash tasarlanabilir; okul numarası örneğinde 1000 olası numara 1000 farklı indise gider.

12.8Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• eşleme map
• anahtar key
• değer value
• doğrudan adresleme direct addressing
• hash tablosu hash table
• hash fonksiyonu hash function
• hash kodu hash code
• sıkıştırma compression function
• kova bucket
• çakışma collision
• ayrı zincirleme separate chaining
• açık adresleme open addressing
• yoklama probing
• doğrusal yoklama linear probing
• karesel yoklama quadratic probing
• çift hash double hashing
• kümelenme primary clustering
• yük faktörü load factor
• yeniden boyutlandırma resizing (rehashing)
• amortize analiz amortized analysis

12.9Kendini Dene

1. 5 kovalı, h(k) = k mod 5 kullanan ayrı zincirlemeli bir tabloya sırasıyla 8, 13, 3, 21 ve 6 ekleniyor; yeni düğüm zincirin başına eklenir. Son tablo nedir, λ kaçtır ve getir(8) kaç anahtar karşılaştırması yapar?

   Cevap

   Kovalar: 8 → 3, 13 → 3, 3 → 3, 21 → 1, 6 → 1. Başa ekleme nedeniyle son gelen başta durur: 1. kova 6 → 21, 3. kova 3 → 13 → 8; 0, 2 ve 4. kovalar boştur. λ = 5/5 = 1. getir(8) 3. kovada 3, 13 ve 8'i inceler: 3 karşılaştırma.

2. "Can".hashCode() değerini String.hashCode() formülüyle hesaplayın (C = 67, a = 97, n = 110). 13 kovalı tabloda bu anahtar hangi kovaya düşer?

   Cevap

   h = 67; 31 · 67 + 97 = 2174; 31 · 2174 + 110 = 67504. 13 · 5192 = 67496, kalan 8: kova 8. "Ali" de 8. kovaya düştüğü için iki anahtar çakışır.

3. 11 yuvalı, h(k) = k mod 11 kullanan doğrusal yoklamalı boş bir tabloya sırasıyla 4, 15, 26 ve 5 ekleniyor. Her anahtar hangi yuvaya yerleşir ve kaç yoklama yapar?

   Cevap

   4 → 4 (1 yoklama). 15'in ev yuvası 4, dolu; 5 boş (2 yoklama). 26'nın ev yuvası 4; 4 ve 5 dolu, 6 boş (3 yoklama). 5'in ev yuvası 5; 5 ve 6 dolu, 7 boş (3 yoklama). Toplam 9 yoklama; 4–7 arası tek bir kümedir.

4. Önceki sorudaki tabloda 15 silinip 5. yuva null yapılırsa getir(26) ne bulur? Yuvaya silindi işareti konursa ne değişir?

   Cevap

   null ile: arama 4'ten başlar (4 ≠ 26), 5 boştur ve “26 yok” der; oysa 26 6. yuvadadır. Silindi işaretiyle: 4 (4 ≠ 26), 5 (✗, atlanır), 6'da 26 bulunur; 3 yoklama.

5. yuvaBul bir aramada −1 döndürdü. Bu sonuç ne anlama gelir? Metot -(uygun + 1) yerine -uygun döndürseydi hangi durum ayırt edilemezdi?

   Cevap

   Negatif sonuç “anahtar yok” demektir; eklenecek yuva −(−1 + 1) = 0'dır. -uygun döndürülseydi uygun yuva 0 olduğunda sonuç da 0 olurdu ve “0. yuvada bulundu” ile karışırdı.

6. 11 yuvalı tabloda h(k) = k mod 11 ve h₂(k) = 7 − (k mod 7) ile çift hash kullanılıyor. Boş tabloya 13, 24 ve 35 eklenirse hangi yuvalara yerleşirler? Doğrusal yoklamada ne olurdu?

   Cevap

   Üçünün de ev yuvası 2'dir. 13 → 2. 24: adım 7 − 3 = 4, 2 dolu, 2 + 4 = 6. 35: adım 7 − 0 = 7, 2 dolu, 2 + 7 = 9. Doğrusal yoklamada 2, 3, 4 yuvalarına yerleşir ve bir küme oluştururlardı.

7. Varsayılan ayarlarla oluşturulmuş bir Java HashMap'e anahtarlar tek tek ekleniyor. Kaçıncı eklemede tablo ilk kez büyür ve kaç kovaya çıkar? Bir sonraki büyüme kaçıncı eklemededir?

   Cevap

   Varsayılan kova sayısı 16, eşik 0,75 · 16 = 12'dir. Öğe sayısı 12'yi aşınca, yani 13. eklemede tablo 32 kovaya büyür. Yeni eşik 0,75 · 32 = 24'tür; 25. eklemede tablo 64 kovaya çıkar.

8. Okul numarası 220706099 ve 220707099 için ((ab − 20) × 100 + (c − 6) × 500 + de) mod 1000 değerlerini bulun.

   Cevap

   İkisinde de ab = 22, de = 99. 220706099: c = 6, 200 + 0 + 99 = 299. 220707099: c = 7, 200 + 500 + 99 = 799.

9. Doğrusal yoklamalı bir tabloda λ = 2/3'tür. Knuth'un formüllerine göre başarılı ve başarısız bir arama ortalama kaç yoklama yapar?

   Cevap

   1 − λ = 1/3. Başarılı: ½(1 + 3) = 2. Başarısız: ½(1 + 9) = 5.

10. Bir Nokta sınıfında equals iki koordinatı karşılaştırıyor, hashCode ise x + y döndürüyor. Sözleşme sağlanır mı? Boş bir HashMap'e new Nokta(1, 2) ve new Nokta(2, 1) anahtarlarıyla iki put yapılırsa size() kaç olur?

    Cevap

    Sözleşme sağlanır: eşit noktaların koordinatları aynı olduğundan x + y de aynıdır. (1, 2) ile (2, 1)'in hash kodları aynıdır (3), ama equals'a göre farklıdırlar. İkisi aynı kovaya düşer ve ayrı çiftler olarak saklanır: size() 2'dir. Fonksiyon doğrudur ama zayıftır; toplamı aynı olan bütün noktalar çakışır.

12.10İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Bölüm 10: eşleme ADT'sini, hash kodu ve sıkıştırma ayrımını, MAD yöntemini, zincirleme ve doğrusal yoklamalı Java gerçeklemelerini bu nottakine yakın bir yapıyla verir.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 11: zincirlemenin ve açık adreslemenin beklenen maliyetlerini olasılık hesabıyla kanıtlar; evrensel hash fikrini tanıtır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 3.4: zincirleme ve doğrusal yoklamalı sembol tablolarını Java koduyla verir; yük faktörünün etkisini deneylerle gösterir.
• D. E. Knuth, The Art of Computer Programming, Cilt 3: Sorting and Searching (2. baskı, 1998), Kesim 6.4: doğrusal yoklamanın beklenen yoklama sayısı formüllerinin kaynağıdır; hash fikrinin tarihçesini de anlatır.

12.11Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
3. D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2. baskı, Addison-Wesley, 1998.
4. Oracle, Java SE 17 API Specification: java.util.Map, java.util.HashMap ve java.util.HashSet belgeleri.
5. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.

İlgili sayfalar: Bölüm 12 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.