Масъулияти ҷустуҷӯи унсур бо калид дар HashMap чӣ гуна аст?

Маъруф мураккабият — O(1), дар бадтарин ҳолат — O(n).

• Маслиҳат (O(1)): Бо функсияи хуби хеш ва тақсимоти баробаронаи унсурҳо дар контейнерҳо (buckets), ҷустуҷӯ ба ҳисоб кардани хеши калид ва дастрасии мустақим ба контейнери мувофиқ дар массив маҳдуд мешавад. Дар дохили контейнер, агар ягон коллизия набошад, унсур дар вақти доимӣ пайдо мешавад.
• Бадтарин ҳолат (O(n)): Вақте ки ҳамаи унсурҳо дар як контейнер хеш мешаванд. Дар ин ҳолат, ҷустуҷӯ ба ҷустуҷӯи хаттӣ дар рӯйхати пайвастшавӣ табдил меёбад (ё дар дарахти мувозанатёфта дар Java 8+ барои контейнерҳо бо шумораи зиёди унсурҳо, аммо ҳатто гузариш дар дарахт метавонад O(log n) вақт гирад, ки дар ҳолатҳои зиёд шудани коллизияҳо дар як контейнер, ба O(n) наздик мешавад).

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