List va Dictionary'da qidiruvning algoritmik murakkabligi qanday? Dictionary ichki tuzilishi qanday?

Algoritmik murakkablik:

• List ichida qidirish (masalan, List<T> C# da) — odatda, bu chiziqli qidirish bo‘lib, murakkabligi O(n), chunki elementlarni tartib bilan ko‘rib chiqish kerak.

• Dictionary ichida qidirish — o‘rtacha murakkabligi O(1), chunki hash-jadvaldan foydalaniladi.

Dictionary tuzilishi:

C# da Dictionary<TKey, TValue> hash-jadval asosida amalga oshirilgan. Kalit hash-funksiyadan foydalanib hash qilinadi, bu kalitni bucketlar massivida indeksga aylantiradi. Har bir bucket zanjirli ro‘yxat yoki boshqa tuzilmani o‘z ichiga oladi. Element qo‘shishda yoki qidirishda:

1. Kalitning hash qiymati hisoblanadi.
2. Hashga asoslangan bucket aniqlanadi.
3. Bucket ichida kalit bo‘yicha qidiriladi (Equals yordamida solishtiriladi).

Bu kalit bo‘yicha tezkor kirishni ta’minlaydi, agar hash taqsimoti yaxshi bo‘lsa.

Misol:

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