HashMap'teki işlemler hangi koşullarda koleksiyonun boyutuna orantılı zaman karmaşıklığına sahiptir?

HashMap içindeki işlemler (örneğin, get, put) genellikle amortize edilmiş zaman karmaşıklığı O(1) olan işlemlerdir. Ancak bazı durumlarda, karmaşıklık O(n)’ye kadar çıkabilir, burada n koleksiyonun boyutudur. Bu durumlar şunlardır:

• Tüm anahtarlar kötü bir hash fonksiyonu nedeniyle tek bir kovaya (bucket) düşerse, bu durumda uzun bir liste veya tek bir hücrede bir ağaç oluşur.
• Çakışmalar eşit olmayan şekilde dağılıyorsa ve veri yapısı bu kovada bozuluyorsa.

Java 8 ve üzeri sürümlerde, bir kovada çok fazla öğe varsa, HashMap bağlı listeyi dengeli bir ağaca (TreeNode) dönüştürür, bu da en kötü durumu O(log n)’ye düşürür, ancak O(1)’ye değil.

Bu nedenle, işlemler koleksiyonun boyutuna orantılı hale gelir, güçlü çakışmalar ve kötü hash dağılımı durumlarında.