Чӣ гуна мураккабии алгоритмики ҷустуҷӯ дар List ва Dictionary аст? Dictionary дар дохили чӣ гуна сохта шудааст?

Пешгирии алгоритмикӣ:

• Дар List (масалан, List<T> дар C#) — одатан, ин ҷустуҷӯи хаттӣ аст, бо мураккабии O(n), зеро бояд элементҳоро ба тартиб гузоред.

• Дар Dictionary — мураккабии миёна O(1), зеро истифодаи ҷадвали хеш.

Тартиби Dictionary:

Dictionary<TKey, TValue> дар C# асосан бар асоси ҷадвали хеш сохта шудааст. Калид бо истифода аз функсияи хеш хеш мешавад, ки калидро ба индекс дар массиви бакетҳо табдил медиҳад. Ҳар як бакет дорои рӯйхати пайваст ё дигар сохтор барои ҳал кардани коллизияҳо мебошад. Вақте ки элемент илова ё ҷустуҷӯ мешавад:

1. Ҳисоб кардани хеши калид.
2. Таҳия кардани бакет бо асоси хеш.
3. Ҷустуҷӯ дар бакет бо калид (бо истифода аз Equals).

Ин имкон медиҳад, ки ба арзишҳо тавассути калид зуд дастрасӣ пайдо шавад, агар тақсимоти хешҳо хуб бошад.

Масалан:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int арзиш = dict["apple"]; // Дастрасии зуд