Dictionary ma'lumotlar tuzilmasida elementlarni qidirish tezligining xususiyati qanday?

Ma'lumotlar tuzilmasi Dictionary (masalan, C# da) elementni kalit bo'yicha qidirish odatda amortizatsiya qilingan murakkablikka ega bo'lib, O(1), ya'ni juda tez va deyarli doimiy vaqt ichida amalga oshiriladi.

Bu, kalitni hash-kodga aylantirish uchun hash-jadvalidan foydalanish orqali erishiladi, bu esa indeksni tezda topishga imkon beradi.

Ammo, eng yomon holatda (masalan, ko'p koliziyalar bo'lsa), qidiruv vaqti O(n) ga pasayishi mumkin, bu yerda n elementlar soni, lekin bunday holatlar yaxshi taqsimlangan hash-funksiyalarda kamdan-kam uchraydi.

C# da Dictionary uchun qidiruv misoli:

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