Kuidas hinnata HashMapis võtme järgi elemendi otsimise tõhusust kolisjonide korral?

HashMap-is otsing elementide järgi võtme alusel toimub keskmiselt ajal O(1), kuid kokkupõrgete korral sõltub tõhusus nende töötlemise meetodist.

Varasemalt käsitleti kokkupõrkeid seotud listidega (lülitatud nimekirjad), ja halvimates tingimustes (kui kõik võtmed satuvad ühte korvi) muutus otsing O(n)-ks.

Java 8-st alates, kui ühe korvi elementide arv ületab teatud läve, muudetakse seotud nimekiri tasakaalustatud puuks (näiteks punane-must puu). See parandab selle korvi halvimat otsingut O(log n)-ks.

Seega:

• Väikese kokkupõrke korral jääb otsing O(1)-le lähedale.
• Suure kokkupõrke korral ühes korvis on otsing O(log n).

See täiendus suurendab HashMap-i jõudlust oludes, kus olukord on ebasoodne.