Kaip vertinama HashMap elemento paieškos efektyvumas esant kolizijoms?

HashMap paieškoje pagal raktą vidutiniškai vyksta per O(1) laiką, tačiau susidūrus su kolizijomis, efektyvumas priklauso nuo jų apdorojimo būdo.

Anksčiau kolizijos buvo sprendžiamos naudojant grandines (sujungtas sąrašas), ir blogiausiu atveju (kai visi raktai patenka į tą pačią dėžutę) paieška tapdavo O(n).

Nuo Java 8, jei vienoje dėžutėje esantis elementų skaičius viršija tam tikrą slenkstį, susijęs sąrašas paverčiamas subalansuotu medžiu (pvz., raudonai-juodu medžiu). Tai pagerina blogiausio atvejo paiešką iki O(log n) šiai dėžei.

Taigi:

• Su nedidelėmis kolizijomis paieška išlieka arti O(1).
• Su daug kolizijų vienoje dėžutėje, paieška bus O(log n).

Šis patobulinimas žymiai padidina HashMap našumą nepalankiuose scenarijuose.