Чӣ тавр вақти дастрасӣ ба унсури дар сохтори додаҳои HashMap муайян карда мешавад?

Вақти дастрасӣ ба унсури дар сохтори додаҳои HashMap дар Java одатан ҳамчун констант — O(1) — ҳисоб карда мешавад. Ин тавассути истифодаи функсияи хеш, ки калидро ба индекс дар массив табдил медиҳад, ба даст меояд.

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

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

Аз ин рӯ, вақти миёнаи дастрасӣ тақрибан ба O(1) баробар аст, аммо дар ҳолатҳои бадтарин метавонад ба O(log n) ё O(n) расад.