8

Não sabia da existência da KeyedCollection até ver essa resposta de Cigano.

Daí me vieram dúvidas de como e quando utilizar uma KeyedCollection, já que existe o Dictionary que aparentemente tem o mesmo objetivo.

2 Respostas 2

7

Você deve usar na situação que você precisa acessar os elementos dessa coleção em O(1) (encontra o que deseja essencialmente no mesmo tempo, não importa o tamanho da coleção) tanto pela posição do elemento, quanto pela chave. Ou se precisa tanto da coleção enumerada pela ordem que ela foi sendo adicionada ou achar um elemento dentro dela de forma rápida.

Lista

Em uma List é fácil manter a ordem de entrada dos dados e acessá-los de acordo com sua posição. Uma lista é como se fosse um array. Basta o índice e você chega no elemento de forma muito rápida apenas com um cálculo rápido da posição da memória. De uma certa forma podemos dizer que o índice é a chave desta coleção. Se você tentar achar um valor nesta lista terá uma complexidade O(n), ou seja, terá que, potencialmente, percorrer toda a lista para achar o que quer.

Dicionário

Em um Dictionary o armazenamento é feito através de funções de hash, ou seja, a chave é calculada e obtém um número que será usado para posicionar o elemento em uma estrutura interna que irá armazenar a coleção. Então é muito rápido achar um elemento pela sua chave em quase todos casos. Basta fazer o cálculo da chave para achar seu "número mágico" (hashcode) e ali você posiciona onde está o elemento, não precisa percorrer os outros elementos (há casos que precisa percorrer alguns elementos porque pode haver colisão mas este é outro assunto e não vou entrar em detalhes, em funções hash boas isto quase não acontece). O problema é que se você quiser enumerar sequencialmente esses elementos, nada garante como vem, não tem ordem. E por não ter ordem definida, você não pode pegar um elemento pela posição que foi adicionada. Você não pode pegar o primeiro ou o último elemento adicionado na coleção.

Melhor dos mundos

A KeydCollection resolve isso, você pode fazer ambos.

Mas como ele consegue fazer isso?

Em computação tudo é tradeoff. Você tem que escolher o que vai abrir mão para ter uma vantagem. Neste caso vai abrir mão da memória. Esta coleção mantém, grosso modo, uma List e um Dictionary internamente. Por isto consegue ter as duas características. Claro que consome mais espaço.

Uma forma de alcançar isso é ter uma lista que é adicionada na ordem e ter uma tabela hash que tem como chave o que foi definida na KeydCollection e o seu valor (lembre-se que um dicionário usa um par de chave e valor) é a posição na lista onde este elemento está. Assim não precisa duplicar o conteúdo nas duas estruturas.

Claro que estou falando de uma implementação hipotética, isso é detalhe de implementação (se quiser ver como realmente é implementada, o fonte está disponível). Em uma situação ideal deveria ter uma otimização maior, principalmente no caso do tamanho do valor ser menor que o tamanho do índice da lista. Mas duvido que isto seja feito.

Usando a classe

Como pode ser visto na documentação dessa coleção, ela é abstrata, você não pode usá-la de fato. Deve-se criar uma derivada e sobrescrever um método abstrato para achar uma chave no meio de um valor definido. Por ser abstrato, ele precisa de uma implementação concreta.

Um exemplo de implementação concreta da classe permitindo que ela seja usada de forma genérica, ou seja, a chave é definida por uma função anônima e evita ter que ficar derivando a classe sempre que precisar de um critério diferente, que deve ser bem comum ser diferente em cada caso quando se usa a KeyedCollection.

Note que nesta classe você não especifica a chave e o valor, como ocorre na Dictionary. Você específica o valor do elemento. A chave será obtida por um cálculo qualquer definido dentro da classe no método GetKeyForItem(). Este cálculo pode pegar o valor como um todo, pode pegar um membro do valor, ou pode fazer uma composição complexa do que é encontrado no valor.

Coloquei no GitHub para referência futura.

7

Na verdade a KeyedCollection é um Dictionary em que você escolhe como montar o índice.

Repare que no exemplo da resposta mencionada eu uso algo assim:

public class MortoCollection : KeyedCollection<String, Morto>
{
    protected override string GetKeyForItem(Morto item)
    {
        return item.NrCpf.ToString();
    }
}

O uso é praticamente igual a um Dictionary:

var morto = minhaCollection['12345678901'];

Usando assim, eu devolvo em morto o objeto cuja propriedade Cpf seja igual a 12345678901.

Quando Usar?

Quando você quiser montar um dicionário de objetos indexado por alguma propriedade do objeto. Diferentemente de uma List, em que você precisa usar extensões para obter objetos por valor (portanto, mais lento, visto que é preciso iterar os itens um a um para obter o valor), a KeyedCollection torna essa obtenção de elemento muito mais simples.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .