Devi scavare un po 'per vedere come il dizionario è implementato in C # - Non è ovvio come HashMap (una tabella hash) o < a href="https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html"> TreeMap (un albero ordinato) (o ConcurrentSkipListMap - a skip list ).
Se scorri verso il basso nella sezione "Osservazioni":
The Dictionary generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table.
E ce l'abbiamo. È una tabella hash . Nota che ho collegato l'articolo di Wikipedia lì - è una lettura abbastanza buona. Potresti voler leggere la sezione sulla risoluzione delle collisioni. È possibile ottenere un set di dati patologici in cui la ricerca passa a O (N) (per esempio tutto ciò che si inserisce scende per lo stesso valore hash o indice nella tabella hash per qualche motivo e si rimane con indagine lineare ).
Sebbene il dizionario sia una soluzione generica, non dovresti passare in rassegna tipi concreti (come il dizionario) - dovresti passare attorno alle interfacce. In questo caso, tale interfaccia è IDictionary ( documenti ) . Per questo, sei perfettamente in grado di scrivere la tua implementazione del dizionario che fa le cose in modo ottimale per i dati che hai.
Per quanto riguarda l'efficienza di varie ricerche / contiene?
- Percorrere un elenco non ordinato: O (N)
- Ricerca binaria di un array ordinato: O (log N)
- Albero ordinato: O (log N)
- Tabella hash: O (1)
Per la maggior parte delle persone, la tabella hash è ciò che vogliono.
Potresti scoprire che SortedDictionary è ciò che desideri invece:
The SortedDictionary<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval.
Anche se, ancora una volta, se la struttura dati non è quella che funziona idealmente con i tuoi dati, ti vengono forniti gli strumenti (le interfacce) per poterne scrivere uno che funzioni meglio per i tuoi dati.
Il dizionario stesso è un tipo di dati astratto . Tu mi dai un Dizionario e so cosa posso fare con esso e tutti gli strumenti che sono lì per me da usare per la natura di essere un Dizionario. Se mi hai dato un ArrayList, mi troverei a scrivere il mio codice per cercare, inserire o eliminare elementi dalla lista. Questo spreca il mio tempo e significa anche che c'è più probabilità di un bug mentre copio il codice ancora e ancora da un posto all'altro.