🗂️ 8.1: Hash Table (Hash Tablosu)

# Python'un yerleşik hash() fonksiyonu
# Her obje için benzersiz bir tamsayı üretir

# String'lerin hash değerleri
print("String hash değerleri:")
print(f"hash('Ali') = {hash('Ali')}")
print(f"hash('Ayşe') = {hash('Ayşe')}")
print(f"hash('ali') = {hash('ali')}")  # Büyük/küçük harf fark eder!

# Sayıların hash değerleri (kendileri)
print(f"\nhash(42) = {hash(42)}")
print(f"hash(3.14) = {hash(3.14)}")

# Tuple hash'lenebilir, list hash'lenemez!
print(f"\nhash((1, 2, 3)) = {hash((1, 2, 3))}")
# hash([1, 2, 3])  # TypeError: unhashable type: 'list'

# Modülo ile indeks hesaplama
tablo_boyutu = 11
anahtar = "Ali"
indeks = hash(anahtar) % tablo_boyutu
print(f"\nTablo boyutu: {tablo_boyutu}")
print(f"'{anahtar}' için indeks: {indeks}")

# ===== PYTHON DICT TEMELLERİ =====

# 1. Oluşturma - Süslü parantez {} ile
ogrenciler = {
    "Ali": 85,      # anahtar: değer
    "Ayşe": 92,
    "Mehmet": 78
}
print(f"Öğrenciler: {ogrenciler}")

# 2. Ekleme - O(1) ortalama
# Yeni bir anahtar ile değer atama
ogrenciler["Fatma"] = 88
ogrenciler["Zeynep"] = 95
print(f"\nYeni eklemeler: {ogrenciler}")

# 3. Arama/Erişim - O(1) ortalama
# Köşeli parantez ile değere erişim
ali_notu = ogrenciler["Ali"]
print(f"\nAli'nin notu: {ali_notu}")

# 4. Güncelleme - O(1) ortalama
# Var olan anahtara yeni değer atama
ogrenciler["Ali"] = 90  # 85'ten 90'a güncellendi
print(f"Ali'nin yeni notu: {ogrenciler['Ali']}")

# 5. Silme - O(1) ortalama
# del anahtar kelimesi ile
del ogrenciler["Mehmet"]
print(f"\nMehmet silindi: {ogrenciler}")

# 6. Anahtar Kontrolü - O(1) ortalama
# 'in' operatörü ile
print(f"\n'Ayşe' var mı? {'Ayşe' in ogrenciler}")  # True
print(f"'Zehra' var mı? {'Zehra' in ogrenciler}")  # False

# 7. Güvenli Erişim - get() metodu
# Anahtar yoksa hata vermez, varsayılan değer döner
zehra_notu = ogrenciler.get("Zehra", "Kayıt yok")
print(f"Zehra'nın notu: {zehra_notu}")

# 8. Tüm Anahtarlar ve Değerler
print(f"\nTüm anahtarlar: {list(ogrenciler.keys())}")
print(f"Tüm değerler: {list(ogrenciler.values())}")
print(f"Tüm çiftler: {list(ogrenciler.items())}")

# ===== DİCT COMPREHENSION =====
# Liste comprehension'ın dict versiyonu
# Sözdizimi: {anahtar: değer for eleman in iterable}

# 1-10 arası sayıların kareleri
kareler = {x: x**2 for x in range(1, 11)}
print(f"Kareler: {kareler}")

# ===== SETDEFAULT =====
# Anahtar yoksa ekle, varsa mevcut değeri döndür
sayac = {}
kelimeler = ["elma", "armut", "elma", "kiraz", "elma"]

for kelime in kelimeler:
    # Eğer kelime yoksa 0 ile başlat, sonra 1 ekle
    sayac[kelime] = sayac.get(kelime, 0) + 1

print(f"\nKelime sayıları: {sayac}")

# ===== DEFAULTDICT =====
# collections modülünden - varsayılan değer fabrikası
from collections import defaultdict

# int() varsayılan olarak 0 döner
sayac2 = defaultdict(int)
for kelime in kelimeler:
    sayac2[kelime] += 1  # Olmayan anahtar otomatik 0 olur

print(f"defaultdict ile: {dict(sayac2)}")

# list() varsayılan olarak [] döner
gruplar = defaultdict(list)
ogrenciler = [("A", "Ali"), ("B", "Ayşe"), ("A", "Ahmet"), ("B", "Berk")]
for sinif, isim in ogrenciler:
    gruplar[sinif].append(isim)

print(f"\nSınıf grupları: {dict(gruplar)}")

# ===== COUNTER =====
# Sayma işlemi için özel dict
from collections import Counter

metin = "merhaba dünya merhaba python"
kelime_sayisi = Counter(metin.split())
print(f"\nCounter ile: {kelime_sayisi}")
print(f"En sık 2 kelime: {kelime_sayisi.most_common(2)}")

class HashTable:
    """
    Chaining yöntemi ile Hash Table implementasyonu.
    Her bucket bir liste (linked list yerine Python list).
    """

    def __init__(self, size=11):
        """
        Hash table oluştur.

        Args:
            size: Bucket sayısı (asal sayı tercih edilir)
        """
        self.size = size
        # Her bucket için boş liste oluştur
        self.buckets = [[] for _ in range(size)]
        self.count = 0  # Eleman sayısı

    def _hash(self, key):
        """Anahtarı indekse çevir."""
        return hash(key) % self.size

    def put(self, key, value):
        """Anahtar-değer çifti ekle veya güncelle."""
        index = self._hash(key)
        bucket = self.buckets[index]

        # Anahtar zaten var mı kontrol et
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Güncelle
                return

        # Yeni eleman ekle
        bucket.append((key, value))
        self.count += 1

    def get(self, key):
        """Anahtarın değerini döndür."""
        index = self._hash(key)
        bucket = self.buckets[index]

        for k, v in bucket:
            if k == key:
                return v

        raise KeyError(f"Anahtar bulunamadı: {key}")

    def remove(self, key):
        """Anahtarı sil."""
        index = self._hash(key)
        bucket = self.buckets[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.count -= 1
                return v

        raise KeyError(f"Anahtar bulunamadı: {key}")

    def __contains__(self, key):
        """'in' operatörü için."""
        try:
            self.get(key)
            return True
        except KeyError:
            return False

    def __str__(self):
        """Görselleştirme."""
        result = []
        for i, bucket in enumerate(self.buckets):
            if bucket:
                items = ", ".join(f"{k}:{v}" for k, v in bucket)
                result.append(f"[{i}] → {items}")
            else:
                result.append(f"[{i}] → boş")
        return "\n".join(result)

# Test
ht = HashTable(7)

# Eklemeler
for isim, yas in [("Ali", 25), ("Ayşe", 22), ("Mehmet", 30),
                   ("Fatma", 28), ("Zeynep", 24), ("Ahmet", 27)]:
    ht.put(isim, yas)
    print(f"Eklendi: {isim} → {yas}")

print(f"\n=== Hash Table Durumu ===")
print(ht)
print(f"\nToplam eleman: {ht.count}")

# Arama
print(f"\nAli'nin yaşı: {ht.get('Ali')}")
print(f"'Zeynep' var mı? {'Zeynep' in ht}")

def two_sum(nums, target):
    """
    Dizide toplamı target olan iki sayının indekslerini bul.

    Brute Force: O(n²) - Her çift için kontrol
    Hash Table: O(n) - Tek geçiş!

    Mantık: Her sayı için "target - sayı" değerini hash'te ara.
    """
    # Gördüğümüz sayıları ve indekslerini sakla
    seen = {}  # {değer: indeks}

    for i, num in enumerate(nums):
        # enumerate(liste): (indeks, değer) çiftleri döner
        complement = target - num  # Aranan tamamlayıcı

        if complement in seen:
            # Bulundu! Tamamlayıcının indeksi ve şimdiki indeks
            return [seen[complement], i]

        # Bu sayıyı kaydet
        seen[num] = i

    return []  # Bulunamadı

# Test
nums = [2, 7, 11, 15]
target = 9
print(f"Dizi: {nums}")
print(f"Hedef: {target}")
print(f"Sonuç: {two_sum(nums, target)}")  # [0, 1] çünkü 2 + 7 = 9

nums2 = [3, 2, 4]
target2 = 6
print(f"\nDizi: {nums2}")
print(f"Hedef: {target2}")
print(f"Sonuç: {two_sum(nums2, target2)}")  # [1, 2] çünkü 2 + 4 = 6

def first_repeating(s):
    """
    String'deki ilk tekrar eden karakteri bul.

    Hash Set kullanarak O(n) çözüm.
    Set, sadece anahtarları tutan bir hash table'dır.
    """
    seen = set()  # Gördüğümüz karakterler

    for char in s:
        if char in seen:  # O(1) kontrol
            return char
        seen.add(char)  # O(1) ekleme

    return None  # Tekrar yok

# Test
test_strings = ["abcabc", "abcdef", "aabbcc", "python"]

for s in test_strings:
    result = first_repeating(s)
    if result:
        print(f"'{s}' → İlk tekrar: '{result}'")
    else:
        print(f"'{s}' → Tekrar yok")