Чӣ тавр арзёбӣ мешавад самаранокии ҷустуҷӯи унсур бо калид дар HashMap дар мавриди коллизияҳо?

Дар HashMap ҷустуҷӯи унсур бо калид одатан дар вақти O(1) сурат мегирад, аммо дар ҳолати коллизияҳо, самаранокӣ аз усули ҳалли онҳо вобаста аст.

Пештар, коллизияҳо бо истифода аз занҷирҳо (листҳои пайвастшуда) ҳалли мекарданд, ва дар ҳолати бадтарин (ҳангоми ҳама калидҳо ба як коса афтодан) ҷустуҷӯ O(n) мешуд.

Аз Java 8, агар шумораи унсурҳо дар як коса аз ҳадди муайян гузарад, листи пайвастшуда ба дарахти мувозинатёфтар (масалан, дарахти сурх-сурх) табдил меёбад. Ин беҳбудӣ ҳолати бадтаринро барои ҷустуҷӯ ба O(log n) барои он коса такмил медиҳад.

Бинобар ин:

• Бо камтар коллизияҳо, ҷустуҷӯ наздик ба O(1) мемонад.
• Бо зиёд шудани коллизияҳо дар як коса, ҷустуҷӯ O(log n) мешавад.

Ин беҳбудӣ самаранокии HashMap-ро дар сценарияҳои бадтар ба таври назаррас баланд мебардорад.