Çakışma

İ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.

Örnek çözümü göster

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

Kendini test et

Çakışma: kavramları eşleştir

arama

O(1) ortalama
çakışma

Listede ara
yük faktörü

Doluluk
rehash

Yeniden boyut
Yük faktörü neyi ölçer?
- Doluluk oranını
- Tablo boyutunu
- Hash kalıtesini
- Arama hızını
Cevabı göster

Doluluk oranını — Doluluk oranını ölçer.

Rehash

Yük faktörü yüksekse ____ yapılır.

Cevabı göster

Yük faktörü yüksekse rehash yapılır.

Sıradaki ders: Özet - Hash table

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler