Dictionary маалыматтар түзүмүндө элементтерди издөө ылдамдыгынын өзгөчөлүгү кандай?

Маалыматтар түзүмү Dictionary (мисалы, C#да) элементти ачкыч боюнча издөө адатта амортизделген O(1) татаалдыгы менен иштейт, башкача айтканда, өтө тез жана практикалык түрдө убакыт боюнча туруктуу.

Бул хеш-таблица колдонуу аркылуу жетишилет, анда ачкыч хеш-кодго айлантылат, ал тез арада массивдеги көрсөткүчтү табууга мүмкүндүк берет.

Бирок, эң жаман учурда (мисалы, көптөгөн кагылышуулар болсо), издөө убактысы O(n) га чейин төмөндөйт, анда n — элементтердин саны, бирок мындай учурлар жакшы бөлүштүрүлгөн хеш-функция менен сейрек кездешет.

C#да Dictionary аркылуу издөө мисалы:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // O(1) издөө