HashMapda kalitga asoslangan elementni qidirish samaradorligi qanday baholanadi?

HashMap da elementni kalit bo‘ylab qidirish odatda O(1) vaqt ichida amalga oshadi, ammo to‘qnashuvlar bo‘lsa, ularni boshqarish usuliga bog‘liq bo‘ladi.

Avval, to‘qnashuvlar zanjirlar (bog‘langan ro‘yxatlar) yordamida hal qilinardi, va eng yomon holatda (barcha kalitlar bir xil qutiga tushsa) qidirish O(n) ga aylanardi.

Java 8 dan boshlab, agar bir qutidagi elementlar soni belgilangan chegaradan oshsa, bog‘langan ro‘yxat muvozanatli daraxtga (masalan, qizil-oq daraxt) aylantiriladi. Bu, bu qutidagi qidirishning eng yomon holatini O(log n) ga yaxshilaydi.

Shunday qilib:

• Kam to‘qnashuvlar bilan qidirish O(1) ga yaqin bo‘lib qoladi.
• Ko‘p to‘qnashuvlar bo‘lsa, qidirish O(log n) bo‘ladi.

Ushbu yaxshilash HashMap ning ishlashini noqulay holatlarda sezilarli darajada oshiradi.