Hash fonksiyonu

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.

Örnek çözümü göster

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))

Kendini test et

Çakışma

İki anahtar aynı indekse hash'lenirse ____ olur.

Cevabı göster

İki anahtar aynı indekse hash'lenirse çakışma olur.

Hash fonksiyonu: kavramları eşleştir

çakışma

Aynı indeks
zincirleme

Liste ile çözüm
açık adresleme

Boş yer arama
hash fonksiyonu

İndeks üretir
Çakışma çözme yöntemlerinden biri nedir?
- Doğrusal arama
- Ayrı zincirleme
- İkili arama
- Bubble sort
Cevabı göster

Ayrı zincirleme — Ayrı zincirleme bir çözme yöntemidir.

Sıradaki ders: Çakışma

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler