Хусусияти суръати ҷустуҷӯи унсурҳо дар сохтори додаҳои Dictionary чӣ гуна аст?

Дар структураи додаҳо Dictionary (масалан, дар C#) ҷустуҷӯи унсур бо калид одатан дорои мураккабии амортизатсияшудаи O(1) мебошад, яъне хеле зуд ва дар амалан доимӣ дар вақт.

Ин тавассути истифодаи ҷадвали хеш, ки дар он калид ба код хеш табдил дода мешавад, ки имкон медиҳад суръатбахшии ёфтани индекс дар массив.

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

Масалан барои ҷустуҷӯ дар Dictionary дар C#:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // Ҷустуҷӯ дар O(1)