HashMap operatsiyalarining kolleksiya hajmiga proportsional vaqt murakkabligi bo'lish shartlari qanday?

HashMap ichidagi operatsiyalar (masalan, get, put) odatda amortizatsiya qilingan vaqt murakkabligi O(1) ga ega. Biroq, ba'zi hollarda, murakkablik O(n) ga oshishi mumkin, bu yerda n to'plamning hajmi. Bu quyidagi hollarda yuzaga keladi:

• Barcha kalitlar yomon hash funksiyasi tufayli bitta kova (bucket) ga tushib qoladi, bu esa uzun ro'yxat yoki daraxtga olib keladi.
• To'qnashuvlar notekis taqsimlangan bo'lib, ichki ma'lumotlar tuzilmasi degradatsiya qilinadi.

Java 8 va undan yuqori versiyalarda, agar bitta kovada juda ko'p elementlar bo'lsa, HashMap bog'langan ro'yxatni muvozanatli daraxtga (TreeNode) aylantiradi, bu esa eng yomon holatni O(log n) ga kamaytiradi, lekin O(1) ga emas.

Shuning uchun, operatsiyalar to'plamning hajmiga proportsional bo'lib, kuchli to'qnashuvlar va yomon hash taqsimoti bo'lsa, amalga oshadi.