Ako sa hodnotí efektívnosť vyhľadávania prvku podľa kľúča v HashMap pri kolíziách?

V HashMap je vyhľadávanie prvku podľa kľúča priemerne trvá čas O(1), ale pri kolíziách závisí efektívnosť od spôsobu ich riešenia.

Doteraz sa kolízie riešili pomocou reťazcov (prepojených zoznamov), a v najhoršom prípade (keď všetky kľúče padnú do jednej nádoby) bolo vyhľadávanie O(n).

Od Java 8, ak počet prvkov v jednej nádobe prekročí určitý prah, prepojený zoznam sa premení na vyvážené stromové štruktúry (napríklad červené-čierne stromy). To zlepšuje najhorší prípad vyhľadávania na O(log n) pre túto nádobu.

Takže:

• Pri malom počte kolízií zostáva vyhľadávanie blízko O(1).
• Pri veľkom počte kolízií v jednej nádobe bude vyhľadávanie O(log n).

Toto zlepšenie výrazne zvyšuje výkon HashMap v nepriaznivých scenároch.