Farklı koşullarda bir öğenin hash tablosuna eklenme işleminin verimliliği nasıl değerlendirilir?

Bir öğenin bir karma tablosuna eklenme verimliliği birkaç faktöre bağlıdır:

1. Tablo yük oranı (yük faktörü) — öğe sayısının dizi boyutuna oranı. Düşük yükte, ekleme genellikle amortize edilmiş O(1) sürede gerçekleşir.

2. Hash fonksiyonunun kalitesi — anahtarların küresel dağılımı, çakışmaları en aza indirir.

3. Çakışma yönetimi:

   • Zincirleme (chaining) ile ekleme, bağlı liste veya başka bir konteynerde ekleme yapmaktır. Ortalama O(1), ancak en kötü durumda O(n), eğer tüm öğeler aynı kuyruğa düşerse.
   • Açık adresleme (doğrusal tarama, kuadratik tarama) ile ekleme, boş bir yer aramayı gerektirebilir, bu da yüksek yük altında zamanı artırır.

4. Yeniden karma (rehashing) — yük oranı eşiğine ulaşıldığında, tablo genişletilir, bu da öğelerin yeniden dağıtımını gerektirir ve geçici olarak ekleme süresini artırır.

Özetle: iyi bir hash fonksiyonu ve makul bir yük oranıyla, ekleme amortize edilmiş O(1) süredir. Yüksek yük veya kötü hash fonksiyonu durumunda, zaman O(n)’ye kadar düşebilir.