Dictionary məlumatlar strukturlarında elementlərin axtarış sürətinin xüsusiyyəti nədir?

Məlumatlar strukturu Dictionary (məsələn, C#-da) elementin açar üzrə axtarışı adətən amortizasiya olunmuş O(1) mürəkkəbliyə malikdir, yəni çox sürətli və praktiki olaraq zaman baxımından sabitdir.

Bu, hash cədvəlindən istifadə etməklə əldə edilir; burada açar hash koduna çevrilir və bu, indeksin sürətlə tapılmasına imkan verir.

Lakin, ən pis halda (məsələn, çox sayda toqquşma olduqda), axtarış vaxtı O(n)-ə qədər pisləşə bilər, burada n elementlərin sayıdır, amma belə hallar yaxşı hash funksiyası paylanması ilə nadirdir.

C#-da Dictionary-də axtarış nümunəsi:

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