ti-enxame.com

Dicionário vs Lista

Então eu encontrei um Dictionary<int, int> hoje no trabalho. Isso me pareceu estranho, porque eu provavelmente usaria um List<int> em vez de. Existe uma diferença e haveria um caso de uso em que uma estrutura seria preferida à outra?

30
ZeroDivide

Você usaria um Dictionary<int, int> se seus índices tiverem um significado especial além de apenas um posicionamento posicional.

O exemplo imediato que vem à mente é armazenar uma coluna de identificação e uma coluna int em um banco de dados. Por exemplo, se você tiver um [person-id] coluna e uma [personal-pin], então você pode trazê-los para uma Dictionary<int, int>. Por aqui pinDict[person-id] fornece um PIN, mas o índice é significativo e não apenas uma posição em um List<int>.

Mas, realmente, sempre que você tiver duas listas relacionadas de números inteiros, essa pode ser uma estrutura de dados apropriada.

33
Kris Harper

Pense no List como uma matriz e o Dictionary como um tabela de hash . Você usaria apenas Dictionary se precisasse mapear (ou associar) chaves significativas para valores, enquanto um List mapeia (ou associa) apenas posições (ou associados) a valores.

Por exemplo, digamos que você queira armazenar uma associação entre a idade de uma pessoa e sua altura. Você poderia usar um Dictionary<int, int> para mapear a idade da pessoa (um int) para sua altura (um 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;

Não é um exemplo muito útil, mas o ponto é que você não seria capaz de fazer isso de maneira tão elegante com um List, pois seria necessário armazenar esses valores posicionalmente.

28
Bernard

Semanticamente, um Dictionary<int, T> e List<T> são muito semelhantes, ambos são contêineres de acesso aleatório da estrutura .NET. Para usar uma lista como substituta de um dicionário, você precisa de um valor especial no seu tipo T (como null) para representar os espaços vazios na sua lista. Se T não for um tipo anulável como int, você poderá usar int? em vez disso, ou se você apenas espera armazenar valores positivos, também pode usar um valor especial como -1 para representar espaços vazios.

Qual você escolherá depende do intervalo dos valores-chave. Se suas chaves no Dictionary<int, T> estão dentro de um intervalo inteiro, sem muitas lacunas entre eles (por exemplo, 80 valores entre [0, ... 100]) e, em seguida, um List<T> será mais apropriado, pois o acesso por índice é mais rápido e, nesse caso, há menos sobrecarga de memória e tempo em comparação com um dicionário.

Se os seus valores-chave forem 100 int valores de um intervalo como [0, ..., 1000000], um List<T> precisa de memória para armazenar 1000000 valores de T, onde seu dicionário precisará apenas de memória em uma ordem de magnitude em torno de 100 valores de T, 100 valores de int (mais alguma sobrecarga, na realidade, espere cerca de 2 vezes a memória para armazenar esses 100 chaves e valores). Portanto, no último caso, um dicionário será mais apropriado.

15
Doc Brown

Como alguém pode considerá-los equivalentes?

O dicionário é escasso e permite inserções aleatórias, mas torna a travessia em ordem um problema, a Lista não é esparsa e uma inserção fora de ordem é cara, pois fornece inerentemente a travessia em ordem.

Haveria muito poucas situações em que uma não fosse dramaticamente superior à outra.

6
Loren Pechtel

Além: Outras linguagens de programação se referem a esse tipo de estrutura de dados como um Mapa, em vez de um Dicionário.

Se seus dados puderem ser definidos significativamente como pares de chave/valor, um Dicionário fornecerá um acesso muito mais rápido se você precisar encontrar um valor usando sua chave.

Por exemplo, suponha que você tenha uma lista de clientes. Cada cliente inclui detalhes como nome e endereço e um número de cliente exclusivo. Suponha que você também tenha uma lista de pedidos em processamento. Cada pedido conterá detalhes do que está sendo feito e precisará incluir o número do cliente da pessoa que o solicitou.

Quando um pedido está pronto para ser enviado, você precisa encontrar o endereço para o qual ele é enviado. Se os clientes estiverem armazenados como uma lista simples, será necessário pesquisar na lista inteira para encontrar o cliente com o número certo de clientes. Em vez disso, você pode armazenar os clientes em um dicionário, com o número do cliente como a chave. O dicionário agora permite que você obtenha o cliente correto em uma única etapa, sem fazer nenhuma pesquisa.

2
Simon B

O dicionário usa hash para procurar os dados. Um dicionário calculou primeiro um valor de hash para a chave e esse valor de hash leva ao intervalo de dados de destino. Depois disso, cada elemento no bucket precisa ser verificado quanto à igualdade. Mas, na verdade, a lista será mais rápida que o dicionário na primeira pesquisa de itens, porque não há nada para pesquisar na primeira etapa. Mas, na segunda etapa, a lista precisa examinar o primeiro item e depois o segundo item. Portanto, cada etapa da pesquisa leva cada vez mais tempo. Quanto maior a lista, mais tempo leva.

Mais sobre .... Dicionário Vs List com exemplo.

1
Walshregal