Karma İşlevlerinin İç Yapısı ve Çakışma Yönetimi
Python’un nesneleri nasıl karma değerine dönüştürdüğünü, açık adresleme ve zincirlemenin çakışmaları nasıl çözdüğünü ve ortalama durumdaki O(1)’in neden O(n)’e düşebileceğini anlayın.
Karma İşlevlerinin İç Yapısı ve Çakışma Yönetimi, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Karma Harita Nedir?
Bir karma harita (Python'daki sözlük), herhangi bir anahtarı temelindeki diziye karşılık gelen bir tamsayı indisine dönüştüren bir karma işlevi kullanarak anahtarları değerlere eşler. İdeal bir karma işlevi, anahtarları diziye eşit biçimde dağıtır ve ortalama durumda O(1) arama, ekleme ve silme sağlar. Temel diziye karma tablo veya kova dizisi adı verilir.
Python'da dict, yüksek düzeyde eniyilenmiş bir karma haritadır. İç yapısını anlamak, en kötü durum davranışı hakkında akıl yürütmenize ve uygun anahtarları seçmenize yardımcı olur.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Karma İşlevleri ve __hash__ Yöntemi
Python, anahtardan bir tamsayı hesaplamak için __hash__(key) çağrısını yapar, ardından kova indisini bulmak için bu tamsayının tablo boyutuna bölümünden kalanı alır. int, str ve tuple gibi yerleşik türlerin hızlı yerleşik karma uygulamaları vardır. list ve dict karma değeri alınabilir türler değildir (değişebilirdirler; onları değiştirmek, depolanmış herhangi bir karmayı geçersiz kılardı).
İyi bir karma işlevi anahtarları eşit biçimde dağıtır, belirlenimlidir ve hızlı hesaplanır. Python'ın dizge karması çalıştırmalar arasında rastgeleleştirilir (bir güvenlik özelliğidir) — sınamalarda yeniden üretilebilirlik sağlamak için devre dışı bırakmak üzere PYTHONHASHSEED=0 kullanınız.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Çakışmalar: İki Anahtarın Aynı Kovaya Karma Oluşturması
İki farklı anahtar aynı kova indisini ürettiğinde çakışma oluşur. Çakışmalar kaçınılmazdır (güvercin yuvası ilkesi: sonsuz sayıda anahtar, sonlu sayıda kova). İki standart çözüm stratejisi zincirleme ve açık adresleme yöntemleridir. Python, sözde rastgele yoklama kullanan bir açık adresleme çeşidinden yararlanır.
Zincirleme, her kovada bir bağlı liste (veya dinamik dizi) depolar; o kovada çakışan tüm anahtarlar bir zincir oluşturur. Açık adresleme ise bir yoklama dizisine göre sonraki boş kovayı arar.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NoneAçık Adresleme: Doğrusal Yoklama
Doğrusal yoklamada, i indisinde bir çakışma oluştuğunda harita, boş bir yuva bulana kadar i+1, i+2, ... konumlarını denetler (dizinin başına dönerek). Arama işlemi, anahtarı bulmak için aynı diziyi yoklamalıdır. Yoklama zincirini bozmamak için silme işlemlerinde yuvayı temizlemek yerine bir "mezar taşı" işareti kullanılması gerekir.
Kümelenme, bu yöntemin başlıca sakıncasıdır: dolu yuvalardan oluşan bir küme oluştuğunda, o bölgeye yapılacak sonraki eklemeler kümeyi genişletir ve performansı O(n)'e doğru düşürür.
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Yük Faktörü ve Yeniden Boyutlandırma
Yük faktörü, depolanan girdilerin toplam kapasiteye oranıdır: α = n/m. α arttıkça çakışma olasılığı yükselir ve performans düşer. Python'ın dict yapısı, yük faktörü yaklaşık 2/3'ü aştığında yeniden boyutlandırılır (kapasiteyi iki katına çıkarır). Yeniden boyutlandırma, mevcut tüm girdileri yeni ve daha büyük tabloya yeniden karma işleminden geçirir — seyrek gerçekleşen O(n) maliyetli bir işlemdir; bu sayede ekleme işleminin amortismanlı maliyeti O(1) olarak kalır.
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeOrtalama O(1) ile En Kötü Durum O(n) Karşılaştırması
İyi bir karma işlevi kullanıldığında çakışmalar seyrektir ve beklenen zincir uzunluğu n'den bağımsız olarak sabittir. Bu nedenle ortalama durumda arama, ekleme ve silme işlemleri O(1)'dir. Ancak en kötü durum — örneğin tüm anahtarları kasıtlı olarak aynı kovaya eşleyen hasımca hazırlanmış bir girdi — tüm işlemlerin O(n)'e düşmesine yol açar. Python'ın rastgeleleştirilmiş karma tohumu bu saldırının etkisini azaltır, ancak teorik olarak en kötü durumu ortadan kaldırmaz.
Mülakat çözümlemesinde "Çakışmalar nedeniyle ortalama O(1), en kötü durumda O(n)" deyiniz.
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pyPython Sözlüğü, Varsayılan Sözlük ve Sayaç Karşılaştırması
Python, bilinmesi gereken üç karma harita çeşidi sunar. dict genel amaçlı haritadır; eksik bir anahtara erişmek KeyError oluşturur. defaultdict(factory), eksik bir anahtara erişildiğinde varsayılan bir değer döndürür (liste toplamak veya sayım yapmak için kullanışlıdır). Counter, karma değeri alınabilen nesneleri saymaya yönelik özel bir alt sınıftır; ayrıca sayaçlar arasında aritmetik işlemleri destekler.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionKarma Harita ile Karma Küme Karşılaştırması
Bir karma küme yalnızca anahtarları depolar (ilişkili değerleri depolamaz) ve O(1) üyelik sınaması, ekleme ve silme işlemlerini destekler. Python'ın set yapısı bir karma kümedir. İlişkili verileri depolamadan yalnızca "bu öğe var mı?" sorusunu yanıtlamanız gerektiğinde küme kullanınız. Anahtarlarla değerleri (sayımlar, sonuçlar vb.) ilişkilendirmeniz gerektiğinde sözlük kullanınız.
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Sıfırdan Karma Harita Uygulama (Mülakat Sürümü)
Mülakat yapanlar bazen sizden temel bir karma harita uygulamanızı ister. Temel bileşenler şunlardır: sabit boyutlu bir kova dizisi (16 veya 1024 kullanınız), zincirleme için her kovada (anahtar, değer) çiftlerinden oluşan bir liste, bir karma işlevi (Python'ın yerleşik karma işlevini kapasiteye göre bölümünden kalan olarak kullanınız) ve yük faktörü 0,7'yi aştığında yeniden boyutlandırma. Yeniden boyutlandırmadan ve yük faktöründen kendiliğinizden söz etmeniz, bilgi düzeyinizin derin olduğunu gösterir.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedKarma Haritalar Ne Zaman Başarısız Olur: Karma Değeri Alınamayan Anahtarlar
Yalnızca karma değeri alınabilen nesneler sözlük anahtarı olabilir. Python'da bir nesnenin karma değeri alınabilir olması için __hash__ yöntemine ve __eq__ yöntemine sahip olması, ayrıca karma değerinin yaşam süresi boyunca değişmemesi gerekir. Listeler, kümeler ve sözlükler değişebilirdir ve bu nedenle karma değeri alınamaz. Demetler ve dondurulmuş kümeler, anahtar olarak kullanıldıklarında listelere ve kümelere karma değeri alınabilen alternatiflerdir.
Yaygın bir mülakat tuzağı şudur: anagramları gruplamak için sözlük anahtarı olarak sıralanmış bir demet (sıralanmış bir liste değil) kullanmanız gerekir.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Özet: Karma Harita Karmaşıklığı
Karma haritalar ekleme, silme ve arama için ortalama durumda O(1) sağlar — bu, birçok eniyilenmiş mülakat çözümünün temelidir. Temel varsayımlar şunlardır: iyi bir karma işlevi anahtarları eşit biçimde dağıtır, yük faktörü sınırlı kalır (yeniden boyutlandırma bunu korur) ve anahtar nesneleri değişmez olup karma değeri alınabilir. Bu varsayımlar geçerli olduğunda karma haritalar O(n) doğrusal taramaları O(1) aramalara dönüştürür ve iki toplam gibi çözümlerin O(n²) yerine O(n) zamanda çalışmasını sağlar.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı sınayınız.
Ders Özeti
Bu derste şunları öğrendiniz: bir karma harita, bir karma işlevi kullanarak anahtarları kova indislerine eşler ve ortalama durumda O(1) işlemler sağlar, çakışmalar zincirleme (kova başına bağlı liste) veya açık adresleme (sonraki boş yuvayı yoklama) ile çözülür ve yalnızca değişmez, karma değeri alınabilen nesneler sözlük anahtarı olabilir — bir dizi anahtarı gerektiğinde listeler yerine demetler kullanınız. Sırada iki toplamı ve bunun birçok mülakat çeşidini çözeceğiz.
Sıkça Sorulan Sorular
“Karma İşlevlerinin İç Yapısı ve Çakışma Yönetimi” dersi ücretsiz mi?
Evet — “Karma İşlevlerinin İç Yapısı ve Çakışma Yönetimi” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Karma İşlevlerinin İç Yapısı ve Çakışma Yönetimi” dersinde ne öğreneceğim?
Python’un nesneleri nasıl karma değerine dönüştürdüğünü, açık adresleme ve zincirlemenin çakışmaları nasıl çözdüğünü ve ortalama durumdaki O(1)’in neden O(n)’e düşebileceğini anlayın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.
“Karma İşlevlerinin İç Yapısı ve Çakışma Yönetimi” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Karma İşlevlerinin İç Yapısı ve Çakışma Yönetimi
- İki Toplam ve Çeşitli Türevleri
- Sıklık Sayma ve Gruplama
- En Uzun Ardışık Dizi ve LRU Önbelleği