Çakışma
- Algoritmalar kursu
- Başlangıç
- Ders 71/80
- 4 dk
İki anahtarın aynı indekse düşmesi durumunu ve zincirleme çözümü öğrenirsin.
Hash table'da arama
Hash table'da arama: anahtarı hash'le, indeksteki listede anahtarı ara. Bulunursa değeri döndür, yoksa None.
Arama ortalama O(1)'dir çünkü çakışma azsa liste kısadır. En kötü durum (hepsi aynı indekste) O(n)'dir.
Yük faktörü
Yük faktörü = eleman sayısı / tablo boyutu. Yük faktörü yüksekse çakışma artar ve performans düşer.
Yük faktörü 0.7'yi aşarsa tablo yeniden boyutlandırılır (rehash). Bu, O(1) ortalama erişimi korur.
Uygulama Hash table'da bul
ht_get(table, key, size) yaz. hash_func ile indeks bul, listede anahtarı ara. print(ht_get([[(5,'a')],[],[]], 5, 3)) ile a yazdır.
Başlangıç kodu
def ht_get(table, key, size):
# Değeri bulÖrnek çözüm
def ht_get(table, key, size):
# Değeri bul
idx = hash_func(key, size)
for pair in table[idx]:
if pair[0] == key:
return pair[1]
return None
print(ht_get([[(5, 'a')], [], []], 5, 3))Beklenen çıktı
a
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Çakışma: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
arama |
O(1) ortalama |
çakışma |
Listede ara |
yük faktörü |
Doluluk |
rehash |
Yeniden boyut |
2 Yük faktörü neyi ölçer?
- Doluluk oranını Doğru cevap
- Tablo boyutunu
- Hash kalıtesini
- Arama hızını
Açıklama: Doluluk oranını ölçer.
3 Rehash
Yük faktörü yüksekse ____ yapılır.Yük faktörü yüksekse rehash yapılır.Açıklama: rehash doğru.