estruturas de dados NET: ArrayList, lista, HashTable, Dicionário, SortedList, SortedDictionary - Velocidade, a memória, e quando usar cada um?

StackOverflow https://stackoverflow.com/questions/128636

Pergunta

.NET tem um monte de estruturas de dados complexas. Infelizmente, alguns deles são bastante semelhantes, e eu nem sempre tenho certeza de quando usar um e quando usar outro. A maioria do meu C # e Visual Basic livros falar sobre eles, até certo ponto, mas eles nunca realmente entrar em detalhes real.

Qual é a diferença entre Array, ArrayList, List, Hashtable, Dicionário, SortedList, e SortedDictionary?

Quais são enumeráveis ??(IList - pode fazer 'foreach' Loops)? Quais os que usam pares de valor / chave (IDICT)?

E sobre consumo de memória? velocidade de inserção? velocidade de recuperação?

Existem outras estruturas de dados vale a pena mencionar?

Eu ainda estou procurando mais detalhes sobre o uso de memória e velocidade (notação Big-O).

Foi útil?

Solução

Em cima da minha cabeça:

  • Array * - representa uma matriz de memória da velha escola - como uma espécie de apelido para uma matriz type[] normal. Pode enumerar. não pode crescer automaticamente. Eu diria muito rápido inserir e velocidade retrival.

  • ArrayList - crescendo automaticamente matriz. Adiciona mais sobrecarga. Pode enum., Provavelmente, mais lento do que uma matriz normal, mas ainda bastante rápido. Estes são usados ??muito em .NET

  • List - um dos meus favs - pode ser usado com os genéricos, para que possa ter uma matriz fortemente digitado, por exemplo, List<string>. Fora isso, funciona muito parecido com ArrayList

  • Hashtable - plain hashtable de idade. O (1) para o (n) pior caso. Pode enumerar as propriedades de valor e as teclas, e fazer pares chave / val

  • Dictionary - o mesmo que acima só fortemente digitado via genéricos, tais como Dictionary<string, string>

  • SortedList - uma ordenados lista genérica. Desacelerou na inserção, uma vez que tem que descobrir onde colocar as coisas. Pode enum., Provavelmente o mesmo em recuperação uma vez que não têm de recorrer, mas a eliminação será mais lenta do que uma simples lista de idade.

I tendem a usar List e Dictionary todo o tempo -. Uma vez que você começar a usá-los fortemente tipado com os genéricos, a sua realmente difícil voltar aos padrões não-genéricos

Existem muitas outras estruturas de dados também - há KeyValuePair que você pode usar para fazer algumas coisas interessantes, há um SortedDictionary que pode ser útil também

.

Outras dicas

Se possível, use genéricos Isto inclui:.

  • Lista em vez de ArrayList
  • dicionário em vez de HashTable

Em primeiro lugar, todas as coleções em .NET implementar IEnumerable.

Em segundo lugar, um monte de coleções são duplicados porque os genéricos foram adicionados na versão 2.0 do quadro.

Assim, embora as coleções genéricas provável adicionar recursos, na sua maior parte:

  • Lista é uma implementação genérica do ArrayList.
  • dicionário é uma implementação genérica do Hashtable

As matrizes são uma coleção tamanho fixo que você pode alterar o valor armazenado em um determinado índice.

SortedDictionary é um IDictionary que é classificado com base nas teclas. SortedList é um IDictionary que é classificado com base em um IComparer necessário.

Assim, as implementações IDictionary (aqueles KeyValuePairs de apoio) são: * Hashtable * Dicionário * SortedList * SortedDictionary

Outra recolha que foi adicionado em NET 3.5 é o Hashset. É uma coleção que suporta operações definido.

Além disso, o LinkedList é uma implementação de lista encadeada padrão (a lista é uma lista de matriz para mais rápida recuperação).

A folha de fraude bom mencionar as complexidades para estruturas de dados, algoritmos, etc.

Aqui estão algumas dicas gerais para você:

  • Você pode usar foreach em tipos que implementam IEnumerable. IList é essencialmente um IEnumberable com (itens acesso utilizando um índice de base zero) Count e Item propriedades. IDictionary sobre os outros meios mão você pode acessar itens por qualquer-Hashable índice.

  • Array, ArrayList e List tudo implementar IList. Dictionary, SortedDictionary e Hashtable implementar IDictionary.

  • Se você estiver usando .NET 2.0 ou superior, é recomendável que você use contrapartes genéricas de tipos mencionados.

  • Por tempo ea complexidade do espaço de várias operações sobre esses tipos, você deve consultar sua documentação.

  • .NET estruturas de dados estão no namespace System.Collections. Existem bibliotecas de tipos como PowerCollections que oferecem estruturas de dados adicionais.

  • Para obter uma compreensão completa de estruturas de dados, consultar recursos como CLRS .

.NET estruturas de dados:

Mais de conversa sobre o porquê de ArrayList e List são realmente diferentes

Arrays

Como um estados de usuário, matrizes são a coleção "old school" (sim, as matrizes são considerados uma coleção embora não parte de System.Collections). Mas, o que é "old school" sobre matrizes em comparação com outras coleções, ou seja os que você listou em seu título (aqui, ArrayList e List (Of T))? Vamos começar com o básico, olhando para Arrays.

Para começar, Arrays no Microsoft .NET são " mecanismos que permitem tratar vários [logicamente relacionada com] itens como uma única coleção,"(ver artigo ligado). O que isso significa? Matrizes armazenar membros individuais (elementos) sequencialmente, um após o outro na memória com um endereço de partida. Ao usar a matriz, podemos facilmente acessar os elementos sequencialmente armazenados começando nesse endereço.

Além disso, e contrariamente à programação 101 concepções comuns, Arrays realmente pode ser bastante complexo:

Arrays pode ser única dimensão, multidimensional, ou jadded (matrizes irregulares são vale a pena ler sobre). próprias matrizes não são dinâmicas: uma vez inicializada, um conjunto de n reservas de tamanho espaço suficiente para armazenar n número de objetos. O número de elementos na matriz não pode aumentar ou diminuir. reservas Dim _array As Int32() = New Int32(100) espaço suficiente sobre o bloco de memória para a matriz para conter 100 Int32 tipo primitivo objectos (neste caso, a matriz é inicializada para conter 0s). O endereço do bloco é devolvido ao _array.

De acordo com o artigo, Especificação Common Language (CLS) exige que todos os arrays ser zero-based. As matrizes em matrizes diferente de zero com base de apoio NET; no entanto, isso é menos comum. Como resultado da "common-ness" de zero baseadas em matrizes, a Microsoft passou um monte de tempo para otimizar seu desempenho ; portanto, a dimensão única, baseada em zero (ENS) matrizes são "especiais" - e realmente a melhor implementação de uma matriz (em oposição a multidimensional, etc.) - porque ENS têm instruções em linguagem de intermediários específicos para manipulá-los.

Arrays são sempre passados ??por referência (como um endereço de memória) - uma peça importante do quebra-cabeça de matriz de saber. Enquanto eles fazem verificação de limites (irá lançar um erro), verificação de limites também pode ser desactivada em arrays.

Novamente, o maior obstáculo para matrizes é que eles não são re-considerável. Eles têm uma capacidade de "fixo". Apresentando ArrayList e List (Of T) para a nossa história:

ArrayList - não genérico lista

O ArrayList (junto com List(Of T) - embora existam algumas diferenças importantes, aqui, explicado mais tarde) - é talvez melhor ideia de como a próxima adição às coleções (em sentido amplo). ArrayList herdar do IList (um descendente de 'ICollection') interface. ArrayLists, eles mesmos, são mais volumoso - exigindo mais sobrecarga - de Listas.

IList faz permitir a implementação de ArrayLists tratar como listas de tamanho fixo (como matrizes); no entanto, para além do functionallity adicional adicionado por ArrayLists, não existem vantagens de se utilizar ArrayLists que são de tamanho fixo como ArrayLists (mais de Arrays) neste caso são marcadamente mais lenta.

De minha leitura, ArrayLists pode não ser irregular: "Usando multidimensional matrizes como elementos ... não é suportado".. Mais uma vez, mais um prego no caixão do ArrayLists ArrayLists também não são 'digitado' - o que significa que, por baixo de tudo, um ArrayList é simplesmente uma matriz dinâmica de Objetos: Object[] Isso requer. um monte de boxe (implícita) e unboxing (explícito) ao implementar ArrayLists, novamente adicionando a sua sobrecarga.

Infundadas pensou: Acho que me lembro leitura ou de ter ouvido de um dos meus professores que ArrayLists são uma espécie da criança conceitual bastardo da tentativa de passar de matrizes para a Lista do tipo coleções, ou seja, enquanto uma vez tendo sido uma grande melhoria para Arrays, eles já não são a melhor opção como maior desenvolvimento foi feito com respeito às coleções

List (Of T): O que ArrayList tornou-se (e esperava ser)

A diferença na utilização da memória é suficientemente significativa para onde um List (Of Int32) consumido 56% menos memória do que um ArrayList contendo o mesmo tipo primitivo (8 MB vs 19 MB na demonstração ligada do senhor acima: novamente, ligada < a href = "http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx" rel = "nofollow noreferrer"> aqui ) - embora este é um resultado combinado pela máquina de 64 bits. Esta diferença realmente demonstra duas coisas: primeiro (1), um Int32 tipo encaixotado "objeto" (ArrayList) é muito maior do que um tipo puro Int32 primitiva (Lista); segundo (2), a diferença é exponencial, como resultado do funcionamento interno de um computador de 64 bits.

Então, qual é a diferença eo que é um List (Of T) ? MSDN define um List(Of T) como" ... uma lista com rigidez de tipos de objetos que podem ser acessados pelo índice." A importância aqui é o "tipo forte" bit: um List (Of T) 'reconhece' tipos e armazena os objetos como seu tipo. Assim, um Int32 é armazenado como um Int32 e não um tipo de Object. Isso elimina os problemas causados ??por boxing e unboxing.

MSDN especifica essa diferença só entra em jogo quando armazenar tipos primitivos e não tipos de referência Too, a diferença realmente ocorre em grande escala:. Mais de 500 elementos. O que é mais interessante é que a documentação MSDN diz: "É a sua vantagem para usar a implementação específica do tipo do List (Of T) classe em vez de usar a classe ArrayList ...."

Essencialmente, List (Of T) é ArrayList, mas melhor. É o "equivalente genérico" de ArrayList. Como ArrayList, não é garantido para ser resolvido até classificadas (figura go). List (Of T) também tem algumas funcionalidades adicionais.

Eu simpatizo com a questão - (? Achado) Eu também encontrado a escolha desconcertante, por isso me propus cientificamente para ver qual estrutura de dados é o mais rápido (eu fiz o teste usando VB, mas imagino C # seria o mesmo, desde que ambas as línguas fazer a mesma coisa no nível CLR). Você pode ver alguns resultados de benchmarking realizado por mim aqui (há também alguma discussão sobre qual o tipo de dados é melhor para uso em quais circunstâncias).

Eles estão enunciados muito bem em intellisense. Basta digitar System.Collections. ou System.Collections.Generics (preferencial) e você terá uma lista e uma breve descrição do que está disponível.

Hashtables / dicionários são O (1) o desempenho, o que significa que o desempenho não é uma função do tamanho. Isso é importante saber.

EDIT:. Na prática, a complexidade de tempo médio para Hashtable / Dictionary <> pesquisas é O (1)

As coleções genéricas terá um desempenho melhor do que suas contrapartes não-genéricos, especialmente quando a iteração através de muitos itens. Isso ocorre porque o boxe e já não unboxing ocorre.

Uma nota importante sobre Hashtable vs Dictionary em alta frequência de engenharia negociação sistemática: Linha Issue Segurança

Hashtable é segmento seguro para uso por vários segmentos. Dicionário membros estáticos públicos são thread-safe, mas quaisquer membros de instância não são garantidos para ser assim.

Assim Hashtable continua sendo a escolha 'standard' a este respeito.

Há diferenças sutis e não tão sutis entre coleções genéricas e não genéricas. Eles simplesmente usar diferentes estruturas de dados subjacentes. Por exemplo, Hashtable garante um escritor-muitos leitores sem sincronia. Dicionário não.

Na verdade, acho MSDN ajuda a fornecer muito boas respostas para todas essas perguntas. Basta olhar para cima .NET coleções.

Estruturas e coleções mais popular C # Dados

  • array
  • ArrayList
  • Lista
  • LinkedList
  • dicionário
  • HashSet
  • Stack
  • Queue
  • SortedList

C # .NET tem um monte de diferentes estruturas de dados, por exemplo, um dos mais comuns é um Array. No entanto C # vem com muitas estruturas de dados mais básicos. Escolher a estrutura de dados correto para uso faz parte de escrever um programa bem estruturado e eficiente.

Neste artigo vou falar sobre o # estruturas de dados embutidos C, incluindo as novas introduz queridos em C # .NET 3.5. Note-se que muitas dessas estruturas de dados aplica para outras linguagens de programação.

array

A estrutura de dados, talvez, mais simples e mais comum é a matriz. A C # matriz é basicamente uma lista de objectos. Seus traços definidores são de que todos os objetos são do mesmo tipo (na maioria dos casos) e há um número específico deles. A natureza de uma disposição permite um acesso muito rápido aos elementos com base na sua posição na lista de (de outro modo conhecido como o índice). A C # matriz é definido como este: 

[object type][] myArray = new [object type][number of elements]

Alguns exemplos: 

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Como você pode ver no exemplo acima, uma matriz pode ser intialized sem elementos ou a partir de um conjunto de valores existentes. Inserindo valores em uma matriz é simples, desde que eles se encaixam. A operação torna-se dispendiosa quando existem mais elementos que o tamanho da matriz, no ponto em que as necessidades da matriz para ser expandidas. Isso leva mais tempo porque todos os elementos existentes devem ser copiados para a nova matriz, maior.

ArrayList

A estrutura de dados C #, ArrayList, é uma matriz dinâmica. O que isto significa é um ArrayList pode ter qualquer quantidade de objetos e de qualquer tipo. Esta estrutura de dados foi desenvolvido para simplificar os processos de adição de novos elementos para uma matriz. Sob o capô, uma ArrayList é uma matriz cujo tamanho é dobrado de cada vez que corre para fora do espaço. A duplicação do tamanho da matriz interna é uma estratégia muito eficaz que reduz a quantidade de elemento de-cópia, a longo prazo. Não vamos entrar na prova disso aqui. A estrutura de dados é muito simples de usar: 

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

A desvantagem para a estrutura de dados ArrayList é um deve converter os valores retrived de volta para seu tipo de original: 

int arrayListValue = (int)myArrayList[0]

Fontes e mais informações você pode encontrar aqui :

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top