Sözlükler, kümeler ve hash sezgisi

Programlama Temelleri dersinde dict ve set yapılarını temel düzeyde kullandınız. Bu hafta aynı sözdizimini yeniden öğrenmeyeceğiz. Bunun yerine hangi işlem için hangi koleksiyonun uygun olduğunu, sözlük ve kümelerin üyelik kontrolünde neden güçlü olduğunu ve hash tabanlı erişim fikrini sezgisel düzeyde inceleyeceğiz.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

dict ile anahtar-değer ilişkisini problem bağlamında kurabilmeli,
set ile benzersizlik ve hızlı üyelik kontrolünü kullanabilmeli,
frekans sayımı, gruplama ve kayıt indeksleme yapabilmeli,
liste, sözlük ve küme arasında işlem gereksinimine göre seçim yapabilmeli,
hash fikrini matematiksel ayrıntıya girmeden açıklayabilmeli,
hashable olma fikrini sözlük anahtarı ve küme elemanı olabilme koşuluyla ilişkilendirebilmeli,
hash çakışmasının neden mümkün olduğunu ve bu nedenle ortalama durum ifadesinin neden önemli olduğunu sezgisel düzeyde açıklayabilmelisiniz.

2 Liste mi, sözlük mü?

Bir öğrenci listesini yalnızca sırayla dolaşacaksak liste uygun olabilir:

students = ["Ayşe", "Bora", "Cem"]

Fakat öğrenci numarasına göre sık sık arama yapacaksak farklı bir temsil daha anlamlıdır:

students = {
    101: "Ayşe",
    102: "Bora",
    103: "Cem"
}

Burada soru artık “listede kaçıncı sırada?” değil, “101 anahtarına karşılık gelen değer nedir?” olur.

3 Sözlüğü indeks olarak düşünmek

Sözlük, bir bilgiyi başka bir bilgi üzerinden bulmak için kullanılabilir. Örneğin ürün kodundan ürün bilgisine geçelim:

#| edit: false
#| completion: false
products = {
    "K101": {"name": "Kalem", "stock": 24},
    "D205": {"name": "Defter", "stock": 12},
    "S310": {"name": "Silgi", "stock": 30},
}

code = "D205"
print(products[code])
print(products[code]["stock"])

Bu kullanımda sözlük bir indeks (index) görevi görür: bir anahtardan ilgili kayda hızlıca ulaşmamızı sağlar.

4 Küme: benzersizlik ve üyelik

Küme, aynı değeri yalnızca bir kez tutar:

#| edit: false
#| completion: false
tags = ["python", "web", "python", "data", "web"]
unique_tags = set(tags)

print(unique_tags)
print("python" in unique_tags)
print("java" in unique_tags)

Kümenin en güçlü kullanım alanlarından biri şudur:

Bu değer daha önce görüldü mü?

Örneğin tekrar eden kullanıcı adlarını bulalım:

#| edit: false
#| completion: false
usernames = ["ada", "mert", "eda", "ada", "can", "eda"]
seen = set()
duplicates = set()

for username in usernames:
    if username in seen:
        duplicates.add(username)
    else:
        seen.add(username)

print("Tekrar edenler:", duplicates)

5 Frekans sayımı

Bir listedeki her değerin kaç kez görüldüğünü hesaplamak için sözlük çok uygundur:

#| edit: false
#| completion: false
words = ["python", "data", "python", "web", "python", "data"]
counts = {}

for word in words:
    if word in counts:
        counts[word] += 1
    else:
        counts[word] = 1

print(counts)

Aynı kalıbı daha kısa biçimde dict.get() ile yazabiliriz:

#| edit: false
#| completion: false
words = ["python", "data", "python", "web", "python", "data"]
counts = {}

for word in words:
    counts[word] = counts.get(word, 0) + 1

print(counts)

Tip

get(key, default) yöntemi, anahtar yokken hata üretmek yerine verdiğiniz varsayılan değeri döndürür. Frekans sayımında 0 iyi bir başlangıç değeridir.

6 Alıştırma — frekans tablosu

Aşağıdaki programda notların kaç kez tekrarlandığını counts sözlüğünde tutun.

#| exercise: hafta03-frekans
#| completion: false
#| persist: true
grades = [70, 80, 70, 90, 80, 70]
counts = {}

for grade in grades:
    # Bu satırı/satırları tamamlayın.
    pass

print(counts)

Beklenen sonuç:

{70: 3, 80: 2, 90: 1}

#| exercise: hafta03-frekans
#| check: true
scope = {}
try:
    exec(user_code, scope)
    correct = scope.get("counts") == {70: 3, 80: 2, 90: 1}
except Exception:
    correct = False

feedback = (
    {"correct": True, "message": "Frekans sözlüğü doğru oluşturuldu."}
    if correct
    else {"correct": False, "message": "Her not için mevcut sayacı bir artırmayı deneyin. dict.get() kullanabilirsiniz."}
)
feedback

counts[grade] = counts.get(grade, 0) + 1 kalıbını kullanabilirsiniz.

Solution.

grades = [70, 80, 70, 90, 80, 70]
counts = {}

for grade in grades:
    counts[grade] = counts.get(grade, 0) + 1

print(counts)

7 Gruplama

Frekans sayımında her anahtar için bir sayı tutuyorduk. Gruplamada ise her anahtar için bir liste tutabiliriz:

#| edit: false
#| completion: false
records = [
    {"name": "Ayşe", "department": "Yazılım"},
    {"name": "Bora", "department": "Siber"},
    {"name": "Cem", "department": "Yazılım"},
    {"name": "Deniz", "department": "Siber"},
]

groups = {}

for record in records:
    department = record["department"]
    if department not in groups:
        groups[department] = []
    groups[department].append(record["name"])

print(groups)

Bu kalıbı ilerleyen haftalarda dosyadan gelen kayıtları gruplarken tekrar kullanacağız.

8 Hash nedir? Sezgisel model

Sözlük ve kümenin hızlı üyelik/erişim davranışını anlamak için hash fikrini tanıyalım.

Bir hash fonksiyonunu, bir anahtardan o anahtar için kullanılabilecek sayısal bir özet üreten mekanizma gibi düşünebilirsiniz. Python bu değerden yararlanarak aramayı küçük bir aday bölgesine yönlendirebilir. Bu nedenle çoğu durumda bütün elemanları baştan sona dolaşmak gerekmez.

flowchart LR
    A["anahtar: D205"] --> B["hash değeri"]
    B --> C["olası konum"]
    C --> D["Defter kaydı"]

Bu görsel gerçek Python bellek düzenini birebir göstermez; yalnızca neden tüm kayıtları sırayla aramak zorunda kalmayabiliriz? sorusuna sezgisel bir model verir.

9 Çakışma (collision) neden mümkündür?

Hash tablosundaki olası konum sayısı sınırlıdır; kullanılabilecek anahtar sayısı ise çok daha fazla olabilir. Bu nedenle iki farklı anahtarın aynı aday konuma yönelmesi mümkündür. Buna hash çakışması (collision) denir.

flowchart LR
    A["anahtar A"] --> H1["hash"]
    B["anahtar B"] --> H2["hash"]
    H1 --> C["aynı aday bölge"]
    H2 --> C
    C --> R["çakışmayı çözme mekanizması"]

Python’ın kullandığı gerçek çözüm ayrıntıları bu dersin kapsamında değildir. Bizim için önemli sonuç şudur:

Hash tabanlı erişim çoğu durumda çok hızlıdır; fakat bu, her olası durumda kesin ve değişmez O(1) garanti anlamına gelmez.

Important

Bu derste dict ve set işlemlerini karar verirken ortalama durumda O(1) sezgisiyle düşüneceğiz. Çakışmalar, tablonun doluluk durumu ve gerçekleştirim ayrıntıları nedeniyle en kötü durum davranışı farklı olabilir.

10 `hashable` ne demektir?

Bir nesnenin sözlük anahtarı veya normal bir küme elemanı olabilmesi için Python açısından hashable olması gerekir. Basitçe, nesnenin kullanılabilir bir hash değerinin bulunması ve eşitlik ilişkisi açısından bu değerin güvenilir kalması gerekir.

Birçok değiştirilemez temel tür hashable’dır:

int
str
uygun elemanlardan oluşan tuple

Buna karşılık yaygın mutable koleksiyonlar genellikle hashable değildir:

list
dict
set

Burada teknik ölçüt doğrudan “mutable mı?” sorusu değil, hashable mı? sorusudur. Mutability ise neden birçok koleksiyonun hashable olmamasını beklediğimizi anlamaya yardımcı olur.

11 Neden liste anahtar olamaz?

Aşağıdaki kodu çalıştırın:

#| edit: false
#| completion: false
try:
    example = {[1, 2]: "değer"}
except TypeError as error:
    print(type(error).__name__ + ":", error)

Liste hashable olmadığı için sözlük anahtarı olarak kullanılamaz. Aynı şekilde normal bir set de başka bir kümenin normal elemanı olamaz.

Buna karşılık bir tuple, içindeki bütün elemanlar da hashable ise anahtar olabilir:

#| edit: false
#| completion: false
locations = {
    (41.29, 36.33): "Samsun",
    (39.93, 32.85): "Ankara"
}

print(locations[(41.29, 36.33)])

Ancak her tuple otomatik olarak hashable değildir:

#| edit: false
#| completion: false
try:
    value = hash((1, [2, 3]))
    print(value)
except TypeError as error:
    print(type(error).__name__ + ":", error)

İçteki liste hashable olmadığı için tuple da sözlük anahtarı olarak kullanılamaz.

12 Tahmin et — hangileri hashable?

Aşağıdaki değerlerin her biri için önce tahmininizi yapın, sonra kodu çalıştırın:

#| edit: false
#| completion: false
values = [
    42,
    "python",
    (1, 2),
    [1, 2],
    {"a": 1},
    {1, 2},
    (1, [2, 3]),
]

for value in values:
    try:
        print(repr(value), "-> hashable, hash =", hash(value))
    except TypeError:
        print(repr(value), "-> hashable değil")

Bu etkinlikte ezberlenecek uzun bir tür listesi yerine şu soruyu alışkanlık hâline getirin:

Bu değeri sözlük anahtarı veya küme elemanı yapmak istiyorsam Python onu hashable kabul ediyor mu?

13 Alıştırma — uygun anahtarı seç

Bir koordinatı sözlük anahtarı olarak tutmak istiyorsunuz. Aşağıdaki kodda key değerini hashable bir yapı olacak biçimde düzenleyin.

#| exercise: hafta03-hashable
#| completion: false
#| persist: true
key = [41.29, 36.33]

locations = {}
# Bu satır çalışmalı:
locations[key] = "Samsun"

print(locations)

#| exercise: hafta03-hashable
#| check: true
scope = {}
try:
    exec(user_code, scope)
    key = scope.get("key")
    locations = scope.get("locations")
    correct = isinstance(key, tuple) and locations.get(key) == "Samsun"
except Exception:
    correct = False

feedback = (
    {"correct": True, "message": "Koordinat hashable bir tuple olarak anahtar yapıldı."}
    if correct
    else {"correct": False, "message": "Koordinatı liste yerine (41.29, 36.33) gibi bir tuple ile temsil etmeyi deneyin."}
)
feedback

key = (41.29, 36.33) kullanabilirsiniz.

Solution.

key = (41.29, 36.33)
locations = {}
locations[key] = "Samsun"
print(locations)

14 İşlem gereksinimine göre seçim

Gereksinim	Genellikle uygun yapı
Sırayı ve tekrarları korumak	`list`
Anahtardan değere ulaşmak	`dict`
Benzersiz değerler	`set`
Çok sık üyelik kontrolü	çoğu zaman `set` veya `dict`
Aynı değerin kaç kez geçtiğini saymak	`dict`
Bir anahtara birden çok kayıt bağlamak	`dict` + `list`

15 Tahmin et — hangi yapı daha doğal?

Aşağıdaki durumların her biri için önce kendi seçiminizi yapın:

Bir sınavdaki öğrenci cevaplarını sırayla saklamak.
Kullanılmış e-posta adreslerini tekrar kabul etmemek.
Plaka kodundan şehir adına ulaşmak.
Metindeki kelimelerin kaç kez geçtiğini bulmak.
Ürünleri kategoriye göre gruplamak.

Tek bir “her zaman en iyi” veri yapısı yoktur. Doğru soru şudur:

Program en sık hangi işlemi yapacak?

16 Bölüm özeti

Sözlük, anahtar-değer ilişkisi ve indeksleme için uygundur.
Küme, benzersizlik ve üyelik kontrolünde kullanışlıdır.
Frekans sayımı dict ile doğal biçimde modellenir.
Gruplamada sözlük değerleri liste olabilir.
Hash, anahtardan hızlı erişim için kullanılan temel fikirdir.
İki farklı anahtar aynı aday konuma yönlenebilir; buna hash çakışması denir.
Sözlük anahtarı ve normal küme elemanı olabilmek için temel teknik koşul hashable olmaktır.
Hash tabanlı yapıların O(1) davranışı bu derste ortalama durum sezgisi olarak kullanılmalıdır.
Veri yapısı seçimi, sözdizimine değil işlem gereksinimine dayanır.

17 Kendinizi kontrol edin

dict ile set arasındaki temel model farkı nedir?
Frekans sayımı neden liste yerine sözlükle daha doğal ifade edilir?
x in some_set işlemi hangi problem türlerinde değerlidir?
Hash sezgisini bir cümleyle nasıl açıklarsınız?
Hash çakışması ne demektir?
Sözlük anahtarı için teknik ölçüt neden yalnızca “immutable” sözcüğüyle açıklanmamalıdır?
(1, 2) hashable iken (1, [2, 3]) neden hashable değildir?

1 Bu hafta neleri yapabilmelisiniz?

2 Liste mi, sözlük mü?

3 Sözlüğü indeks olarak düşünmek

4 Küme: benzersizlik ve üyelik

5 Frekans sayımı

6 Alıştırma — frekans tablosu

7 Gruplama

8 Hash nedir? Sezgisel model

9 Çakışma (collision) neden mümkündür?

10 hashable ne demektir?

11 Neden liste anahtar olamaz?

12 Tahmin et — hangileri hashable?

13 Alıştırma — uygun anahtarı seç

14 İşlem gereksinimine göre seçim

15 Tahmin et — hangi yapı daha doğal?

16 Bölüm özeti

17 Kendinizi kontrol edin

10 `hashable` ne demektir?