Hash fonksiyonu
- Algoritmalar kursu
- Başlangıç
- Ders 70/80
- 4 dk
Anahtarı bir dizin indeksine çeviren hash fonksiyonunu öğrenirsin.
Çakışma
Çakışma, iki farklı anahtarın aynı indekse hash'lenmesidir. Çakışma kaçınılmazdır ama iyi bir hash fonksiyonu azaltır.
Çakışma çözme yöntemleri: ayrı zincirleme (her indekste bir liste) ve açık adresleme (boş yer arama).
Ayrı zincirleme
Ayrı zincirleme'de her indekste bir liste tutulur. Çakışan anahtarlar aynı listeye eklenir. Arama, listede yapılır.
Eğer çakışma azsa, her liste kısa olur ve arama yaklaşık O(1) kalır. Çok çakışma varsa O(n)'ye yaklaşır.
Uygulama Hash table'e ekle
ht_insert(table, key, value, size) yaz. hash_func ile indeks bul, table'a ekle. print(ht_insert([[]]*3, 5, 'a', 3)) ile indeks 2 bul.
Başlangıç kodu
def ht_insert(table, key, value, size):
# EkleÖrnek çözüm
def ht_insert(table, key, value, size):
# Ekle
idx = hash_func(key, size)
table[idx].append((key, value))
return idx
print(ht_insert([[], [], []], 5, 'a', 3))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Çakışma
İki anahtar aynı indekse hash'lenirse ____ olur.İki anahtar aynı indekse hash'lenirse çakışma olur.Açıklama: çakışma doğru.
2 Hash fonksiyonu: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
çakışma |
Aynı indeks |
zincirleme |
Liste ile çözüm |
açık adresleme |
Boş yer arama |
hash fonksiyonu |
İndeks üretir |
3 Çakışma çözme yöntemlerinden biri nedir?
- Doğrusal arama
- Ayrı zincirleme Doğru cevap
- İkili arama
- Bubble sort
Açıklama: Ayrı zincirleme bir çözme yöntemidir.