Derinlemesine anlamanız gereken tek bir veri yapısı varsa, o hash tablodur. Python'da sözlükleri, JavaScript'te nesneleri, Java'da HashMap'leri güçlendirir ve muhtemelen herhangi bir gerçek uygulamadaki veri yapılarının yüzde altmışını oluşturur. Bir önbellek kullandığınızda, bir kullanıcıyı ID ile aradığınızda, kelime frekanslarını saydığınızda veya bir şeyin küme içinde olup olmadığını kontrol ettiğinizde — hash tablo kullanıyorsunuz.
Nasıl çalıştığını göstereyim, çünkü bunu anlamak performans hakkındaki düşünce şeklinizi değiştirir.
Temel Fikir
Hash tablo anahtar-değer çiftlerini depolar. Ona bir anahtar verirsiniz (kullanıcı adı gibi), size ilişkili değeri geri verir (kullanıcı nesnesi gibi). Etkileyici kısım? Bunu ortalama O(1) sürede yapar — 10 öğeniz olsun veya 10 milyon, sabit zaman.
Bu nasıl mümkün? Sır, hash fonksiyonudur.
Hash fonksiyonu bir anahtar alır ve onu bir sayıya — özellikle bir dizi indeksine — dönüştürür. Aradığınızı bulmak için her elemanı aramak yerine, tam olarak nerede olması gerektiğini hesaplar ve doğrudan oraya atlarsınız.
"alice" → hash("alice") → 738291 → 738291 % dizi_boyutu → indeks 3
array[3] = {name: "Alice", email: "alice@example.com"}
Bir hesaplama, bir dizi erişimi, bitti. O(1) olmasının nedeni budur.
İyi Bir Hash Fonksiyonu Nelere Sahip Olmalı
Belirleyici: Aynı girdi her zaman aynı çıktıyı üretmelidir.
Eşit dağılım: Anahtarlar diziye eşit yayılmalıdır. Anahtarlarınızın yarısı aynı indekse eşlenirse aslında bir bağlı liste oluşturmuşsunuzdur.
Hızlı hesaplama: Hashing'in tüm amacı hızdır.
Çarpışmaları Yönetmek
Sonlu boyutlu bir dizi ve potansiyel olarak sonsuz anahtar sayısıyla çarpışmalar matematiksel olarak kaçınılmazdır. İki farklı anahtar eninde sonunda aynı indekse hash'lenecektir.
Strateji 1: Zincirleme
Her dizi slotu bir bağlı liste tutar. Çarpışan anahtarlar aynı slotun listesine girer:
array[3] → ("alice", {...}) → ("bob", {...}) → null
array[4] → ("charlie", {...}) → null
Java'nın HashMap'i zincirleme kullanır. Bir kova 8'den fazla giriş aldığında bağlı listeyi dengeli ağaca (kırmızı-siyah ağaç) dönüştürür.
Strateji 2: Açık Adresleme
Slot doluysa bir sonraki müsait olanı arar. Python'un dict'i açık adresleme varyantı kullanır.
Gerçek Dünya Kullanım Kalıpları
Önbellek
cache = {}
def get_user(user_id): if user_id in cache: # O(1) arama return cache[user_id] user = database.query(user_id) # Pahalı veritabanı çağrısı cache[user_id] = user # O(1) ekleme return user
Frekans Sayma
def word_count(text):
counts = {}
for word in text.lower().split():
counts[word] = counts.get(word, 0) + 1
return counts
Bu O(n)'dir. Hash tablo olmadan her kelime için sonuçlarınızda arama yapmanız gerekirdi — O(n^2).
Tekrar Tespiti
def has_duplicates(items):
seen = set()
for item in items:
if item in seen:
return True
seen.add(item)
return False
Veri Gruplama
def group_anagrams(words):
groups = {}
for word in words:
key = tuple(sorted(word))
if key not in groups:
groups[key] = []
groups[key].append(word)
return list(groups.values())
İki Sayı Toplamı Problemi
Klasik mülakat sorusu: hedefe toplanan iki sayıyı bulun.
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
Hash tablo bunu O(n^2) brute force'tan O(n)'e çevirir. Bu kalıp — "aramaları önceden hesaplayabilir miyim?" — sürekli karşınıza çıkar.
O(1) Yalanı
Dürüst olmalıyım: O(1) ortalama durumdur, garanti değil. En kötü durumda — her anahtar aynı indekse hash'lendiğinde — hash tablo O(n)'ye düşer.
Pratikte iyi hash fonksiyonları ve uygun boyutlandırmayla bu neredeyse hiç olmaz. Ama bilmek önemlidir çünkü hash fonksiyonu kalitesinin neden önemli olduğunu ve hash çarpışma saldırılarını açıklar.
Yük Faktörü ve Yeniden Boyutlandırma
Yük faktörü giriş sayısının dizi boyutuna oranıdır. Yükseldiğinde çarpışmalar artar. Çoğu uygulama yük faktörü 0.75'i aştığında yeniden boyutlandırır — yeni daha büyük dizi oluşturur ve tüm anahtarları yeniden hash'ler.
Yeniden boyutlandırma O(n)'dir ama nadiren olduğu için amortisman maliyeti O(1) kalır.
Hash Tablolar Ne Zaman Cevap Değildir
Sıralı veri: Hash tablolar belirli bir sıra tutmaz. Sıralı anahtarlar gerekiyorsa TreeMap kullanın.
Aralık sorguları: "A ile M arasındaki tüm kullanıcıları bul" ağaç yapısı gerektirir.
Küçük veri setleri: 10-20'den az öğe için basit dizi araması CPU önbellek etkileri nedeniyle genellikle daha hızlıdır.
Bellek kısıtlı ortamlar: Hash tablolar hız için bellek takas eder.
Mülakat Sırrı
Kodlama mülakatlarında size iyi hizmet edecek bir ipucu: biri O(n^2) brute-force çözümünü optimize etmenizi istediğinde ilk içgüdünüz şu olmalı: "Bunu O(n) yapmak için hash tablo kullanabilir miyim?"
Ciddiyim, bu muhtemelen tüm kodlama mülakat problemlerinin yarısı için işe yarar: İki sayı toplamı, verilen toplama sahip çiftleri bulma, anagram gruplama, ilk tekrarlanmayan karakter.
Kalıp neredeyse her zaman aynıdır: bir kez gezin, ara sonuçları hash tabloda saklayın, iç döngüden kaçınmak için O(1) aramalar kullanın.
Sonuç
Hash tablolar yüzeyde aldatıcı derecede basittir — bir şey koy, çıkar, hızlı. Ama altında ne olduğunu anlamak — hash fonksiyonları, çarpışmalar, yük faktörleri, yeniden boyutlandırma — onları etkili kullanma sezgisini ve daha önemlisi ne zaman doğru seçim olmadığını bilmeyi sağlar.
Pratik programlamanın iş atı veri yapısıdır. İyi öğrenin ve problemleri çözerken içgüdüsel olarak onlara uzanacaksınız. Bu içgüdü, yeni başlayanı orta seviye geliştiriciden ayıran şeydir.
Yorumlar (