Πώς καθορίζεται η πολυπλοκότητα της λειτουργίας αναζήτησης ενός στοιχείου με κλειδί σε ένα λεξικό;

Η πολυπλοκότητα της αναζήτησης ενός στοιχείου με κλειδί σε ένα λεξικό θεωρείται γενικά ότι είναι κοντά στο O(1), χάρη στη χρήση κατακερματιστικών πινάκων. Αυτό σημαίνει ότι ο χρόνος αναζήτησης δεν εξαρτάται από τον αριθμό των στοιχείων στο λεξικό.

Ωστόσο, στην χειρότερη περίπτωση (π.χ., σε συγκρούσεις κατακερματισμού), η πολυπλοκότητα μπορεί να αυξηθεί έως και O(n), όπου n είναι ο αριθμός των στοιχείων. Αλλά οι σύγχρονες υλοποιήσεις λεξικών χρησιμοποιούν αποτελεσματικές μεθόδους επίλυσης συγκρούσεων, οπότε στην πράξη η αναζήτηση είναι πολύ γρήγορη.

Παράδειγμα σε C#:

var dict = new Dictionary<int, string>();
dict[1] = "one";
string value = dict[1]; // Αναζήτηση με κλειδί — περίπου O(1)