HashMap'teki öğeler üzerindeki işlemlerin zaman karmaşıklığı nedir ve HashMap, bir öğe seçerken belirtilen karmaşıklığı garanti eder mi?

HashMap içindeki temel işlemlerin (get, put, remove, containsKey) ortalama zaman karmaşıklığı O(1)’dir.

Bu, anahtarın hash koduna göre belirlenen hücrelerde (kova) öğelerin saklandığı bir karma tablo kullanılmasıyla sağlanır. İdeal durumda, her kovada sadece bir öğe bulunur.

Ancak, en kötü durumda, tüm anahtarların aynı hash koduna sahip olması veya çok sayıda çakışma olması durumunda, öğeler aynı kovaya düşer. Bu durumda, kova bağlı listeye (Java 8’e kadar) veya ağaca (Java 8 ve sonrası, eğer kovadaki öğe sayısı belirli bir eşiği aşarsa) dönüşebilir. Bu tür bir kovada yapılan işlemler O(n) zaman karmaşıklığına sahip olur, burada n, kovadaki öğe sayısıdır.

HashMap sabit zamanlı O(1) erişim garantisi vermez. Sadece ortalama O(1) zaman karmaşıklığını garanti eder. En kötü durumda, karmaşıklık O(n) olabilir.

Zaman karmaşıklığını etkileyen faktörler:

• Hash fonksiyonunun kalitesi: İyi bir hash fonksiyonu, anahtarları eşit şekilde dağıtarak çakışmaları en aza indirir.
• load factor (yükleme oranı): Hash tablosunun ne kadar dolu olabileceğini belirler ve boyutunun artırılmasını (rehash) tetikler. Yüksek load factor çakışma olasılığını artırabilir.
• Başlangıç kapasitesi: Çok küçük başlangıç kapasitesi, çok sayıda öğe ile sık sık yeniden boyutlandırma (rehash) gerektirir ki bu maliyetli bir işlemdir.