HashMap'te anahtar ile öğe aramanın karmaşıklığı nedir?

Ortalama karmaşıklık O(1)’dir, en kötü durumda O(n).

• Ortalama durum (O(1)): İyi bir hash fonksiyonu ve öğelerin kutulara (buckets) düzgün dağılımı ile arama, anahtarın hash değerinin hesaplanması ve karşılık gelen kutuya doğrudan erişimle sınırlıdır. Kutunun içinde, çakışma yoksa, öğe sabit zamanda bulunur.
• En kötü durum (O(n)): Tüm öğelerin aynı kutuya hashlenmesi durumunda ortaya çıkar. Bu durumda, arama bağlı liste içinde lineer taramaya dönüşür (veya Java 8+’de çok sayıda öğe içeren kutular için dengeli bir ağaç kullanılır, ancak ağacı dolaşmak bile O(log n) sürebilir, ve birçok çakışma varsa, toplamda O(n)’ye yaklaşır).

Java 8’den itibaren, belirli bir eşik (TREEIFY_THRESHOLD, varsayılan 8) üzerinde öğe içeren kutular için, bağlı liste dengeli bir ağaca (Kırmızı-Siyah Ağacı) dönüştürülür. Bu, tek bir kutu içindeki en kötü durumu O(log n)’ye iyileştirir, ancak tüm anahtarların aynı hash’e sahip olması durumunda, genel arama yine O(n)’ye yakın olabilir.