HashMap-də əməliyyatlar kolleksiyanın ölçüsü ilə proporsional vaxt mürəkkəbliyinə malik olduğu şərtlər hansılardır?

HashMap-də əməliyyatlar (məsələn, get, put) adətən amortizasiya olunmuş vaxt mürəkkəbliyi O(1)-dir. Ancaq bəzi hallarda, mürəkkəblik O(n)-ə qədər arta bilər, burada n kolleksiyanın ölçüsüdür. Bu, aşağıdakı hallarda baş verir:

• Bütün açarlar pis hash funksiyası nəticəsində bir kovaya (bucket) düşür, bu da uzun siyahıya və ya tək bir hüceyrədə ağaca səbəb olur.
• Çatışmalar bərabər paylanmır və daxili məlumat strukturu zəifləyir.

Java 8 və daha yuxarı versiyalarda, əgər bir kovada çox sayda element olsa, HashMap əlaqəli siyahını balanslı ağaca (TreeNode) çevirir, bu da ən pis halda O(log n)-ə endirir, amma O(1)-ə deyil.

Buna görə, əməliyyatlar kolleksiyanın ölçüsü ilə proporsional olur, güclü çatışmalar və pis hash paylanması hallarında.