Kako se procenjuje efikasnost pretraživanja elementa po ključu u HashMap-u pri kolizijama?

U HashMap pretraživanje elementa po ključevi obično se vrši u proseku za vreme O(1), ali u slučaju kolizija, efikasnost zavisi od načina njihovog rešavanja.

Ranije, kolizije su se rešavale pomoću lanaca (povezanih lista), i u najgorem slučaju (kada svi ključevi padnu u istu korpu) pretraživanje je bilo O(n).

Od Java 8, ako broj elemenata u jednoj korpi pređe određeni prag, povezana lista se pretvara u uravnoteženo stablo (npr. crveno-crno stablo). Ovo poboljšava najgori slučaj pretraživanja na O(log n) za tu korpu.

Dakle:

• Sa malim brojem kolizija, pretraživanje ostaje blizu O(1).
• Sa velikim brojem kolizija u jednoj korpi, pretraživanje će biti O(log n).

Ovo poboljšanje značajno povećava performanse HashMap u nepovoljnim scenarijima.