Hashing: zincirleme, açık adresleme ve rehash

Hashing, “bu anahtar var mı?” sorusunu ortalama sabit zamanda cevaplamanın yoludur. BST bunu $O(\log n)$‘de yapar, hash tablosu $O(1)$‘de. Java’nın HashMap ve HashSet sınıfları bunun üzerine kurulu. Derleyicinin sembol tablosu, önbellekler, veritabanı indeksleri hep hash kullanır.

Sınavda bu haftadan en sık gelen soru: “Şu anahtarları şu tabloya şu yöntemle ekle, son tabloyu yaz.” Yöntemi doğru uygulayan tam puan alır. Altın kurallar:

1. Ev hücresi $h(k) = k \bmod M$. Önce bunu her anahtar için hesapla, kenara yaz.
2. Çarpışma olursa yöntemin formülüne göre sıradaki hücreye bak. Formülde hep ev hücresinden başlarsın, son denenen hücreden değil.
3. Her şey mod M. Tablonun sonundan başa sararsın.
4. Açık adreslemede silme tembel yapılır.
5. λ eşiği aşılınca rehash: yeni boyut, yeni ev hücreleri.

Temel kavramlar

Hash fonksiyonu (hash function): anahtarı 0 ile M-1 arasında bir indekse çevirir. İyi bir hash fonksiyonu hızlı hesaplanır ve anahtarları tabloya eşit dağıtır. Tam sayı anahtarlarda standart seçim $k \bmod M$, M asal.

Neden asal? M = 10 seçersen sadece son basamak önemli olur; anahtarların çoğu 0 ile bitiyorsa hepsi aynı hücreye düşer. Asal M anahtarın bütün basamaklarını karıştırır.

String’ler için Java şu formülü kullanır (Horner yöntemiyle hesaplanır):

$h(s) = s_0 \cdot 31^{n-1} + s_1 \cdot 31^{n-2} + \dots + s_{n-1}$

System.out.println("ab".hashCode());   // 97*31 + 98
System.out.println("cat".hashCode());
System.out.println("act".hashCode());

3105
98262
96402

Karakter kodlarını sadece toplasaydın “cat” ve “act” ikisi de 312 verirdi. 31 ile çarpmak harflerin sırasını hesaba katar.

TUZAK · negatif hashCode. Uzun String’lerde toplam int’e sığmaz ve taşar, hashCode() negatif çıkabilir. h % M de negatif olur ve dizi indeksi patlar. Math.abs(h) % M bile güvenli değil: Math.abs(Integer.MIN_VALUE) yine negatiftir. Doğrusu Math.floorMod(h, M).

Çarpışma (collision): iki farklı anahtar aynı hücreye düşer. M, olası anahtar sayısından küçük olduğu için çarpışma kaçınılmazdır. Mesele onu nasıl çözdüğün.

Doluluk oranı (load factor): $\lambda = n / M$. Performansı belirleyen tek sayı budur.

Bu sayfanın bütün örneklerinde aynı anahtarları kullanacağız:

M = 11
anahtar  27  18  29  28  39  13  16
k mod 11  5   7   7   6   6   2   5

Ayrı zincirleme (separate chaining)

Her hücre bir bağlı liste tutar. Aynı hücreye düşen anahtarlar o listeye eklenir. Biz yeni anahtarı listenin başına ekliyoruz ($O(1)$).

0: -
1: -
2: 13
3: -
4: -
5: 16 -> 27
6: 39 -> 28
7: 29 -> 18
8: -
9: -
10: -

Arama: ev hücresine git, o listeyi tara. Ortalama liste uzunluğu λ olduğu için başarısız arama ortalama λ, başarılı arama yaklaşık $1 + \lambda/2$ eleman inceler. Zincirlemede λ = 1 civarı makul; λ > 1 de çalışır ama yavaşlar. Silme kolaydır: listeden çıkar.

Açık adresleme (open addressing)

Liste yok, anahtarlar doğrudan dizide durur. Çarpışmada bir yoklama dizisi (probe sequence) ile boş hücre aranır: $h_0, h_1, h_2, \dots$ Burada $\lambda \le 1$ zorunlu, pratikte $\lambda \le 0.5$ hedeflenir.

Doğrusal yoklama (linear probing)

$h_i(k) = (h(k) + i) \bmod M$

Dolu ise bir sağa bak. Örnek tablonun iz kaydı (parantez içi: incelenen hücre sayısı):

27 -> 5                    (1)
18 -> 7                    (1)
29 -> 7x 8                 (2)
28 -> 6                    (1)
39 -> 6x 7x 8x 9           (4)
13 -> 2                    (1)
16 -> 5x 6x 7x 8x 9x 10    (6)

idx: 0  1  2  3  4  5  6  7  8  9  10
key: -  -  13 -  -  27 28 18 29 39 16

5’ten 10’a kadar tek bir dolu blok oluştu. Bloğa düşen her yeni anahtar sonuna eklenir ve blok daha da büyür. Buna birincil kümelenme (primary clustering) denir. Doğrusal yoklamanın en büyük zayıflığı budur: 16’nın ev hücresi 5’ti ama 6 hücre gezdi.

Beklenen yoklama sayıları:

λ 0.9’a çıkınca başarısız arama ortalama 50 hücre gezer. Rehash eşiği bu yüzden var.

Karesel yoklama (quadratic probing)

$h_i(k) = (h(k) + i^2) \bmod M$

Sırayla ev + 0, +1, +4, +9, +16, … Kümeden hızla uzaklaşır.

27 -> 5
18 -> 7
29 -> 7x 8          (7+1)
28 -> 6
39 -> 6x 7x 10      (6+1, 6+4)
13 -> 2
16 -> 5x 6x 9       (5+1, 5+4)

idx: 0  1  2  3  4  5  6  7  8  9  10
key: -  -  13 -  -  27 28 18 29 16 39

16 bu sefer 3 yoklamada yerleşti. Birincil kümelenme gider ama aynı ev hücresine düşen anahtarlar yine aynı yolu izler: ikincil kümelenme (secondary clustering).

TUZAK · karesel yoklamada i² ev hücresine eklenir. 39 için ikinci deneme 7, üçüncü deneme 7 + 4 = 11 değil, 6 + 4 = 10. Her deneme $h(k) + i^2$, bir önceki denemeye eklenmez.

Neden M asal ve λ ≤ 0.5? M asal değilse $i^2 \bmod M$ az sayıda farklı değer alır. M = 16 için ev hücresi 0’dan ulaşılabilen hücreler sadece {0, 1, 4, 9}. Tablo yarı boşken bile yer bulunamayabilir. M asal ise ilk $\lceil M/2 \rceil$ deneme hep farklı hücrelere düşer; tablo en az yarı boşsa boş bir hücreye mutlaka varılır.

Çift hashing (double hashing)

$h_i(k) = (h(k) + i \cdot h_2(k)) \bmod M, \qquad h_2(k) = R - (k \bmod R)$

R, M’den küçük bir asal. Adım büyüklüğü anahtara bağlı olduğu için aynı ev hücresine düşen iki anahtar farklı yollar izler; ikincil kümelenme de gider. $h_2$ asla 0 olmamalı (yoksa yerinde sayar); $R - (k \bmod R)$ 1 ile R arasında olduğu için güvenli.

R = 7 ile:

key  h  h2  yol
27   5  1   5
18   7  3   7
29   7  6   7x 2      (7+6=13, mod 11 = 2)
28   6  7   6
39   6  3   6x 9
13   2  1   2x 3      (2'de 29 var)
16   5  5   5x 10

idx: 0  1  2  3  4  5  6  7  8  9  10
key: -  -  29 13 -  27 28 18 -  39 16

Dikkat: 29’un 2’ye yerleşmesi, daha sonra ev hücresi 2 olan 13’ü itti. Sırayı karıştırma; anahtarları verilen sırayla ekle.

Silme: tembel silme (lazy deletion)

Doğrusal tabloda 29’u (indeks 8) silmek istiyoruz. Hücreyi boşaltırsak 39’u aramak bozulur: 39’un yolu 6 → 7 → 8 → 9. Arama 8’de boş hücre görür, “39 yok” der ve durur. Oysa 39 indeks 9’da duruyor.

Çözüm: hücreye DELETED işareti koymak.

idx: 0  1  2  3  4  5  6  7  8  9  10
key: -  -  13 -  -  27 28 18 D  39 16

• Arama DELETED’i dolu gibi geçer: 39 için 6, 7, 8, 9 → 4 hücre, bulunur.
• Ekleme DELETED’i boş gibi kullanabilir: 50 (h = 6) için 6, 7 dolu, 8 DELETED → 50 oraya yazılır.

Çok silme yapılırsa DELETED hücreler birikir ve aramalar uzar; rehash bunları da temizler. Zincirlemede bu sorun yok, düğüm listeden çıkarılır.

Rehashing

λ eşiği aşınca daha büyük bir tablo açılır (genelde 2M’den büyük ilk asal) ve her anahtar yeni M ile yeniden hash’lenir. Eski indeksleri kopyalamak yanlıştır, çünkü $k \bmod M$ değişti.

M = 7, doğrusal yoklama, ekleme sonrası λ > 0.5 ise rehash:

insert 10  λ=0.143  3:10
insert 3   λ=0.286  3:10 4:3
insert 17  λ=0.429  3:10 4:3 5:17
insert 24  λ=0.571  3:10 4:3 5:17 6:24  -> rehash
yeni M = ilk asal >= 14 = 17
10 -> 10   3 -> 3   17 -> 0   24 -> 7
0:17 3:3 7:24 10:10

Eski tabloda dört anahtar 3-6 arasında bir küme oluşturmuştu; yeni tabloda hiç çarpışma yok. Rehash $O(n)$ sürer ama nadiren olur. Her seferinde boyut ikiye katlandığı için ekleme başına amortize maliyet $O(1)$ kalır. Java’nın HashMap’i varsayılan olarak λ > 0.75 olunca kapasiteyi ikiye katlar.

Hangi yöntem ne zaman?

Hash tablosu sıra bilmez. “Anahtarları sıralı yazdır”, “en küçük anahtar”, “10 ile 20 arasındaki anahtarlar” gibi işler için BST ya da AVL seç.

Sık yapılan hatalar

System.out.println("ab".hashCode());
System.out.println("cat".hashCode() == "act".hashCode());

static int insert(int[] table, int key) {
    int M = table.length;
    int h = key % M;
    for (int i = 0; i < M; i++) {
        int p = (h + i) % M;
        if (table[p] == -1) {
            table[p] = key;
            return p;
        }
    }
    return -1; // tablo dolu
}