Dizionario vs elenco

Utilizzeresti un Dictionary<int, int> se i tuoi indici hanno un significato speciale oltre al posizionamento posizionale.

L'esempio immediato che viene in mente è l'archiviazione di una colonna id e una colonna int in un database. Ad esempio, se hai una colonna [person-id] e una colonna [personal-pin] , potresti portarli in Dictionary<int, int> . In questo modo pinDict[person-id] ti fornisce un PIN, ma l'indice è significativo e non solo una posizione in List<int> .

Ma davvero, ogni volta che hai due elenchi correlati di numeri interi, questa potrebbe essere una struttura dati appropriata.

Pensa al List come a un array e al Dictionary come a una tabella hash . Utilizzerai solo Dictionary se hai bisogno di mappare (o associare) chiavi significative ai valori, mentre un List mappa (o associa) solo posizioni (o indici) a valori.

Ad esempio, supponi di voler memorizzare un'associazione tra l'età di una persona e la sua altezza. Puoi utilizzare un Dictionary<int, int> per mappare l'età della persona (un int ) alla loro altezza (un int ):

Dictionary<int, int> personHeightMap = new Dictionary<int, int>();

personHeightMap.Add(21, 185);
personHeightMap.Add(31, 174);

int height = personHeightMap.ContainsKey(21) ? personHeightMap[21] : -1;

Non è un esempio molto utile, ma il punto è che non si sarebbe in grado di farlo in modo elegante con un List perché sarebbe necessario memorizzare questi valori in posizione.

Semanticamente, Dictionary<int, T> e List<T> sono molto simili, entrambi sono contenitori ad accesso casuale del framework .NET. Per utilizzare un elenco in sostituzione di un dizionario, è necessario un valore speciale nel tipo T (come null ) per rappresentare gli spazi vuoti nell'elenco. Se T non è un tipo nullable come int , potresti invece utilizzare int? , oppure se ti aspetti di memorizzare valori positivi, potresti anche usare un valore speciale come -1 per rappresentare spazi vuoti.

Quale sceglierai dovrebbe dipendere dall'intervallo dei valori chiave. Se le tue chiavi in Dictionary<int, T> rientrano in un intervallo intero, senza molti spazi tra di esse (ad esempio, 80 valori su [0, ... 100]), un List<T> sarà più appropriato, poiché l'accesso per indice è più veloce e in questo caso c'è un sovraccarico di memoria e tempo inferiore rispetto a un dizionario.

Se i tuoi valori chiave sono 100 int valori da un intervallo come [0, ..., 1000000], quindi List<T> ha bisogno di memoria per contenere 1000000 valori di T, dove il tuo dizionario avrà solo bisogno di memoria in un dell'ordine di grandezza attorno a 100 valori di T, 100 valori di int (più un po 'di overhead, in realtà aspettiamo circa 2 volte la memoria per memorizzare quei 100 tasti e valori). Quindi in quest'ultimo caso un dizionario sarà più appropriato.

Come possono qualcuno considerarli equivalenti?

Il dizionario è sparse e consente inserimenti casuali ma fa un attraversamento in-order un problema, List non è sparsa e un inserimento fuori-ordine è costoso, fornisce intrinsecamente un traversal in-order.

Ci sarebbero pochissime situazioni in cui uno non era drammaticamente superiore all'altro.

A parte: altri linguaggi di programmazione si riferiscono a questo tipo di struttura dati come una mappa, piuttosto che un dizionario.

Se i tuoi dati possono essere definiti in modo significativo come coppie chiave / valore, allora un dizionario fornirà un accesso molto più veloce se devi trovare un valore usando la sua chiave.

Ad esempio, supponiamo di avere un elenco di clienti. Ogni cliente include dettagli come nome e indirizzo e un numero cliente unico. Supponiamo che tu abbia anche una lista di ordini in fase di elaborazione. Ogni ordine conterrà i dettagli di ciò che viene fatto e dovrà includere il numero cliente della persona che lo ha ordinato.

Quando un ordine è pronto per la spedizione, devi trovare l'indirizzo a cui spedirlo. Se i clienti sono archiviati come Elenco semplice, è necessario cercare l'intero elenco per trovare il cliente con il giusto numero di cliente. Invece, è possibile memorizzare i clienti in un dizionario, con il numero cliente come chiave. Il dizionario ti consentirà ora di estrarre il cliente corretto in un solo passaggio senza alcuna ricerca.

Il dizionario usa l'hashing per cercare i dati. Un dizionario ha prima calcolato un valore hash per la chiave e questo valore hash porta al bucket di dati di destinazione. Dopodiché, ogni elemento nel bucket deve essere controllato per l'uguaglianza. Ma in realtà la lista sarà più veloce del dizionario sul primo elemento di ricerca perché nulla da cercare nel primo passaggio. Ma nella seconda fase, l'elenco deve guardare attraverso il primo elemento e quindi il secondo elemento. Quindi ogni passo della ricerca richiede sempre più tempo. Più grande è l'elenco, più tempo è necessario.

Maggiori informazioni su .... Lista dei dizionari V con esempio.

Se il codice in questione sta memorizzando due serie di valori correlati, la classe Dictionary fornisce un modo indicizzato per cercare valori con una chiave. Se esiste un solo insieme di valori, ma è necessario accedere a tale insieme in modo casuale (forse per verificare l'esistenza di una chiave in un set), e i valori sono univoci, un HashSet potrebbe essere il miglior set di classe da usare.

Queste sono ottime risposte che sembrano coprire le basi.

Un'altra considerazione che offrirò è che i dizionari (in C #) sono più complessi da una prospettiva di codifica. Avere sia liste che dizionari nella stessa base di codice rende più difficile mantenere il codice in quanto entrambi i metodi hanno sottili differenze nel modo di eseguire operazioni di base come la ricerca e il marshalling dei dati degli oggetti. La mia prospettiva è che, a meno che non si abbia bisogno di un dizionario per qualche motivo giustificabile, utilizzare una lista.