Tipos de Coleção Tabela de Hash e Dicionário

Artigo
08/01/2011

O System.Collections.Hashtable classe e o System.Collections.Generic.Dictionary<TKey, TValue> e System.Collections.Concurrent.ConcurrentDictionary<TKey, TValue> classes genéricas, implementar a System.Collections.IDictionary interface. A classe genérica Dictionary<TKey, TValue> também implementa a interface genérica IDictionary<TKey, TValue>. Portanto, cada elemento nessas coleções é um par chave-e-valor.

Um objeto Hashtable consiste de compartimentos de memória que contêm os elementos da coleção. Um compartimento de memória é um subgrupo virtual de elementos dentro do Hashtable, o que torna a pesquisa e a recuperação mais fácil e rápida do que na maioria das coleções. Cada compartimento é associado um código de hash, que é gerado usando uma função de hash e baseia-se na chave do elemento.

Genérico HashSet<T> classe é uma coleção não-ordenada contendo elementos exclusivos. Para obter mais informações sobre essa coleção, consulte Coleção do Tipo HashSet.

Um função de hash é um algoritmo que retorna um código hash numérico com base em uma chave. A chave é o valor da alguma propriedade do objeto sendo armazenado. Uma função de hash deve sempre retornar o mesmo código hash para a mesma chave. É possível para uma função de hash gerar o mesmo código hash para duas chaves diferentes, mas uma função de hash que gera um código hash exclusivo para cada chave específica resulta em melhor desempenho ao recuperar os elementos da tabela de hash.

Cada objeto que é usado como um elemento em um Hashtable deve ser capaz de gerar um código hash para si mesma usando uma implementação da GetHashCode método. No entanto, você também pode especificar uma função de hash para todos os elementos em um Hashtable usando um construtor Hashtable que aceite uma implementação IHashCodeProvider como um dos seus parâmetros.

Quando um objeto é adicionado a um Hashtable, ele é armazenado no compartimento de memória que está associado ao código hash que corresponde ao código hash do objeto. Quando um valor está sendo procurado no Hashtable, o código hash é gerado para esse valor, e o compartimento de memória associado a esse código hash é pesquisado.

Por exemplo, um função de hash para uma sequência de caracteres pode tirar os códigos ASCII de cada caractere na sequência e agrupá-los para gerar um código hash. A sequência de caracteres "piquenique" teria um código hash diferente de código hash para a sequência de caracteres "cesta"; portanto, as sequências de caracteres "piquenique" e "cesta" ficariam em compartimentos de memória diferentes. Por outro lado, as palavras em inglês "stressed" e "dessert" teriam o mesmo código hash e ficariam no mesmo compartimento de memória.

O Dictionary<TKey, TValue> e ConcurrentDictionary<TKey, TValue>classes têm a mesma funcionalidade que o Hashtable classe. A Dictionary<TKey, TValue> de um tipo específico (diferente de Object) fornece um desempenho melhor do que uma Hashtable para tipos de valor. Isso ocorre porque os elementos de Hashtable são do tipo Object; Portanto, boxing e unboxing normalmente ocorrem quando você armazena ou recuperar um tipo de valor. O ConcurrentDictionary<TKey, TValue>deve ser usada quando vários segmentos podem estar acessando a coleção simultaneamente.