Hash tabloları

Telefon rehberinde Elvin'in numarasını tüm listeyi tarayarak bulmak O(n), sıralı bir listede ikili aramayla bulmak O(log n) sürer. Peki adım sayısı n'ye hiç bağlı olmasaydı? Hash tablosu (özet tablosu) tam olarak bunu yapar: anahtarı doğrudan bir dizi indeksine çevirir. Python'un dict ve set türleri, veri tabanlarının hash indeksleri, önbellekler ve derleyicilerin sembol tabloları bu fikir üzerine kuruludur.

Hash fonksiyonu

• Belirlenimcilik: aynı anahtar her zaman aynı hash değerini verir.
• Düzgün dağılım: anahtarlar kovalara yaklaşık eşit dağılır.
• Hız: hesaplama O(anahtar uzunluğu) sürer.
• Anahtarın tamamını kullanır: yalnızca ilk harfe bakan bir fonksiyon “Aysel” ile “Anar”ı aynı kovaya atar.

Çakışmalar ve çözümleri

Olası anahtarlar kovalardan çok daha fazladır; bu yüzden güvercin yuvası ilkesine göre iki farklı anahtarın aynı kovaya düşmesi, yani çakışma kaçınılmazdır. Üstelik beklenenden erken olur: buna “doğum günü paradoksu” denir. Yalnızca 23 kişilik bir grupta iki kişinin aynı gün doğmuş olma olasılığı %50'yi aşar.

• Zincirleme (separate chaining): her kova bir liste tutar; çakışan anahtarlar bu listeye eklenir.
• Açık adresleme: tüm anahtarlar dizinin kendisinde durur; kova doluysa bir sonraki boş yer aranır. Doğrusal sondalama: h(k), h(k) + 1, h(k) + 2, … (mod m).
• Karesel sondalama (h(k) + i²) ve çift hash (h₁(k) + i · h₂(k)), anahtarların bir yere yığılmasını (kümelenmeyi) azaltır.

def insert_linear(table, key):
    m = len(table)
    i = key % m
    probes = 1
    while table[i] is not None:
        i = (i + 1) % m
        probes += 1
    table[i] = key
    return probes

table = [None] * 11
for k in [12, 44, 13, 88, 23, 94, 11, 39, 20]:
    p = insert_linear(table, k)
    print(k, '-> slot', table.index(k), 'probes:', p)
print(table)
print('load factor:', round(9 / 11, 2))

12 -> slot 1 probes: 1
44 -> slot 0 probes: 1
13 -> slot 2 probes: 1
88 -> slot 3 probes: 4
23 -> slot 4 probes: 4
94 -> slot 6 probes: 1
11 -> slot 5 probes: 6
39 -> slot 7 probes: 2
20 -> slot 9 probes: 1
[44, 12, 13, 88, 23, 11, 94, 39, None, 20, None]
load factor: 0.82

Doluluk oranı ve ortalama O(1)

α bir eşiği aştığında (örneğin Java HashMap'te 0,75) tablo yaklaşık iki katına büyütülür ve bütün anahtarlar yeni m için yeniden hash'lenir (rehashing). Bu ara sıra yapılan O(n) iş, dinamik dizideki gibi amortize edilir; bu yüzden ekleme, arama ve silme ortalamada O(1) kalır. En kötü durumda, yani tüm anahtarlar tek kovaya düştüğünde, O(n)'dir.

class HashMap:
    def __init__(self, m=5):
        self.buckets, self.n = [[] for _ in range(m)], 0
    def _index(self, key):
        h = 0
        for ch in key:
            h = h * 31 + ord(ch)
        return h % len(self.buckets)
    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
        self.n += 1
        if self.n / len(self.buckets) > 0.75:
            pairs = [p for b in self.buckets for p in b]
            self.buckets = [[] for _ in range(2 * len(self.buckets) + 1)]
            for p in pairs:
                self.buckets[self._index(p[0])].append(p)
    def get(self, key):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v

caps = HashMap()
for pair in ['Azerbaijan:Baku', 'Georgia:Tbilisi', 'Japan:Tokyo', 'Italy:Rome', 'Egypt:Cairo']:
    caps.put(*pair.split(':'))
print(caps.get('Azerbaijan'), caps.get('Japan'), caps.get('France'))
print(len(caps.buckets), [len(b) for b in caps.buckets])

Baku Tokyo None
11 [1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0]