Por que o dictionary é preferível ao Hashtable?

Na maioria das linguagens de programação, os dictionarys são preferidos a hashtables. Quais são as razões por trás disso?

Por que vale a pena, um Dicionário é (conceitualmente) uma tabela de hash.

Se você quis dizer “por que usamos a class Dictionary vez da class Hashtable ?”, Então é uma resposta fácil: Dictionary é um tipo genérico, Hashtable não é. Isso significa que você obtém segurança de tipo com Dictionary , porque não é possível inserir qualquer object random nela e não é necessário converter os valores obtidos.

Curiosamente, a implementação do Dictionary no .NET Framework é baseada no Hashtable , como você pode dizer a partir deste comentário em seu código-fonte:

O Dicionário genérico foi copiado da fonte do Hashtable

Fonte

Dictionary <<< >>> Hashtable diferenças:

  • Genérico <<< >>> Não Genérico
  • Precisa de synchronization própria de threads <<< >>> Oferece versão segura de thread através do método Synchronized()
  • Item KeyValuePair : KeyValuePair <<< >>> Item enumerado: DictionaryEntry
  • Mais recente (> .NET 2.0 ) <<< >>> Mais antigo (desde o .NET 1.0 )
  • está em System.Collections.Generic <<< >>> está em System.Collections
  • Pedido para chave inexistente lança exceção <<< >>> Pedido para retornos de chaves não existentes null
  • potencialmente um pouco mais rápido para tipos de valor <<< >>> bit mais lento (precisa de boxe / unboxing) para tipos de valor

Similaridades de Dictionary / Hashtable :

  • Ambos são internamente hashtables == access rápido a muitos dados de itens de acordo com chave
  • Ambos precisam de chaves imutáveis ​​e únicas
  • Chaves de ambos precisam do próprio método GetHashCode()

Coleções .NET semelhantes (candidatos a usar em vez de Dictionary e Hashtable):

  • ConcurrentDictionarythread safe (pode ser acessado com segurança de vários threads simultaneamente)
  • HybridDictionarydesempenho otimizado (para alguns itens e também para muitos itens)
  • OrderedDictionary – os valores podem ser acessados ​​via int index (por ordem em que os itens foram adicionados)
  • SortedDictionary – itens classificados automaticamente
  • StringDictionary – fortemente tipado e otimizado para strings

Porque o Dictionary é uma class genérica ( Dictionary ), de modo que o access ao seu conteúdo é seguro para o tipo (ou seja, você não precisa converter de Object , como faz com uma Hashtable ).

Comparar

 var customers = new Dictionary(); ... Customer customer = customers["Ali G"]; 

para

 var customers = new Hashtable(); ... Customer customer = customers["Ali G"] as Customer; 

No entanto, o Dictionary é implementado como Hashtable dentro, portanto, tecnicamente funciona da mesma maneira.

FYI: No .net, Hashtable é thread-safe para uso por vários segmentos de leitor e um único segmento de gravação, enquanto no Dictionary público estático membros estáticos são thread-safe, mas membros de instância não são garantidos para ser thread-safe.

Nós tivemos que mudar todos os nossos Dicionários de volta para o Hashtable por causa disso.

No .NET, a diferença entre Dictionary<,> e HashTable é primariamente que o primeiro é um tipo genérico, então você obtém todos os benefícios dos genéricos em termos de verificação de tipo estático (e redução do boxe, mas isso não é tão grande quanto as pessoas tendem a pensar em termos de desempenho – no entanto, há um custo de memory definido para o boxe.

As pessoas estão dizendo que um dictionary é o mesmo que uma tabela de hash.

Isto não é necessariamente verdade. Uma tabela de hash é uma implementação de um dictionary. Um típico, e pode ser o padrão no .NET, mas não é, por definição, o único.

Você poderia igualmente implementar um dictionary com uma linked list ou uma tree de busca, mas não seria tão eficiente (para alguma métrica eficiente).

Collections e Generics são úteis para lidar com grupos de objects. No .NET, todos os objects de collections vêm sob a interface IEnumerable , que por sua vez tem ArrayList(Index-Value)) e HashTable(Key-Value) . Após o .NET framework 2.0, ArrayList & HashTable foram substituídos por List & Dictionary . Agora, o Arraylist & HashTable não são mais usados ​​nos projetos atuais.

Chegando à diferença entre HashTable & Dictionary , Dictionary é genérico onde como Hastable não é genérico. Podemos adicionar qualquer tipo de object ao HashTable , mas ao recuperar precisamos convertê-lo para o tipo requerido. Então, não é tipo seguro. Mas, para o dictionary , enquanto se declara, podemos especificar o tipo de chave e valor, para que não seja necessário converter durante a recuperação.

Vamos ver um exemplo:

HashTable

 class HashTableProgram { static void Main(string[] args) { Hashtable ht = new Hashtable(); ht.Add(1, "One"); ht.Add(2, "Two"); ht.Add(3, "Three"); foreach (DictionaryEntry de in ht) { int Key = (int)de.Key; //Casting string value = de.Value.ToString(); //Casting Console.WriteLine(Key + " " + value); } } } 

Dicionário,

 class DictionaryProgram { static void Main(string[] args) { Dictionary dt = new Dictionary(); dt.Add(1, "One"); dt.Add(2, "Two"); dt.Add(3, "Three"); foreach (KeyValuePair kv in dt) { Console.WriteLine(kv.Key + " " + kv.Value); } } } 

Dicionário:

  • Ele retorna / lança a Exceção se tentarmos encontrar uma chave que não existe.

  • É mais rápido que um Hashtable porque não há boxe nem unboxing.

  • Somente membros estáticos públicos são thread-safe.

  • Dicionário é um tipo genérico que significa que podemos usá-lo com qualquer tipo de dados (ao criar, deve especificar os tipos de dados para chaves e valores).

    Exemplo: Dictionary = new Dictionary();

  • Dictionay é uma implementação segura de Hashtable, Keys e Values são fortemente tipados.

Hashtable:

  • Ele retorna null se tentarmos encontrar uma chave que não existe.

  • É mais lento que o dictionary porque requer boxe e unboxing.

  • Todos os membros em uma Hashtable são thread-safe,

  • Hashtable não é um tipo genérico,

  • Hashtable é uma estrutura de dados com poucas letras, podemos adicionar chaves e valores de qualquer tipo.

Desde o .NET Framework 3.5, há também um HashSet que fornece todas as vantagens do Dictionary se você precisar apenas das chaves e nenhum valor.

Portanto, se você usar um Dictionary e sempre definir o valor como null para simular a tabela hash de segurança de tipos, talvez considere trocar para o HashSet .

O extenso exame de estruturas de dados usando o artigo do C # no MSDN afirma que há também uma diferença na estratégia de resolução de colisão :

A class Hashtable usa uma técnica conhecida como rehashing .

Rehashing funciona da seguinte maneira: há um conjunto de funções diferentes hash, H 1 … H n , e ao inserir ou recuperar um item da tabela de hash, inicialmente é usada a function hash H 1 . Se isto levar a uma colisão, H 2 é tentado em vez disso, e em diante até H n, se necessário.

O Dicionário usa uma técnica conhecida como encadeamento .

Com rehashing, no caso de uma colisão, o hash é recomputado, e o novo slot correspondente a um hash é testado. Com o encadeamento, no entanto, uma estrutura de dados secundária é utilizada para conter qualquer colisão . Especificamente, cada slot no Dicionário possui uma matriz de elementos que mapeiam para esse intervalo. No caso de uma colisão, o elemento de colisão é anexado à lista do bucket.

A Hashtable é uma estrutura de dados fracamente tipada, portanto, você pode adicionar chaves e valores de qualquer tipo à Hashtable . A class Dictionary é uma implementação Hashtable segura para o tipo, e as chaves e valores são fortemente tipados. Ao criar uma instância do Dictionary , você deve especificar os tipos de dados para a chave e o valor.

Observe que o MSDN diz: “Classe de dictionary <(Of <(TKey, TValue>)>) é implementada como uma tabela de hash “, não “Dictionary <(Of <(TKey, TValue>)>) class é implementada como uma HashTable

O dictionary NÃO é implementado como um HashTable, mas é implementado seguindo o conceito de uma tabela de hash. A implementação não está relacionada à class HashTable devido ao uso de Generics, embora internamente a Microsoft possa ter usado o mesmo código e substituído os símbolos do tipo Object por TKey e TValue.

Em .NET 1.0 Generics não existia; é aqui que o HashTable e o ArrayList começaram originalmente.

Um object Hashtable consiste em intervalos que contêm os elementos da coleção. Um bucket é um subgrupo virtual de elementos dentro da Hashtable, que torna a pesquisa e a recuperação mais fáceis e rápidas do que na maioria das collections .

A class Dictionary tem a mesma funcionalidade que a class Hashtable. Um dictionary de um tipo específico (diferente de Object) tem melhor desempenho do que uma Hashtable para tipos de valor, porque os elementos de Hashtable são do tipo Object e, portanto, boxe e unboxing normalmente ocorrem ao armazenar ou recuperar um tipo de valor.

Para ler mais: Tipos de Coleção de Hashtable e Dicionário

HashTable:

A chave / valor será convertida em um tipo de object (boxe) ao ser armazenado no heap.

Chave / valor precisa ser convertido no tipo desejado durante a leitura do heap.

Essas operações são muito caras. Precisamos evitar o boxe / unboxing o máximo possível.

Dicionário: Variante genérica de HashTable.

Não há boxe / unboxing. Nenhuma conversão é necessária.

Mais uma diferença que eu posso descobrir é:

Não podemos usar o Dictionary (genéricos) com serviços da web. A razão é que nenhum padrão de serviço da web suporta o padrão genérico.

Dictionary<> é um tipo genérico e, portanto, é seguro para o tipo.

Você pode inserir qualquer tipo de valor no HashTable e isso pode, às vezes, lançar uma exceção. Mas o Dictionary só aceita valores inteiros e similarmente o Dictionary aceitará apenas strings.

Portanto, é melhor usar Dictionary<> vez de HashTable .

Outra diferença importante é que o Hashtable é thread-safe. O Hashtable possui segurança embutida de múltiplos leitores / gravadores individuais (MR / SW), o que significa que o Hashtable permite um gravador em conjunto com vários leitores sem bloqueio.

No caso do Dictionary, não há segurança de thread; Se você precisar de segurança de thread, você deve implementar sua própria synchronization.

Para elaborar mais:

Hashtable fornece alguma segurança de thread através da propriedade Synchronized , que retorna um wrapper thread-safe em torno da coleção. O wrapper funciona bloqueando a coleção inteira em cada operação de adição ou remoção. Portanto, cada thread que está tentando acessar a coleção deve aguardar sua vez para obter o bloqueio de um. Isso não é escalonável e pode causar degradação de desempenho significativa para grandes collections. Além disso, o design não é totalmente protegido contra condições de corrida.

As classs de coleção do .NET Framework 2.0, como List, Dictionary etc., não fornecem nenhuma synchronization de thread; o código do usuário deve fornecer toda a synchronization quando os itens são adicionados ou removidos em vários encadeamentos simultaneamente

Se você precisar de segurança de tipo, bem como segurança de thread, use classs de collections simultâneas no .NET Framework. Leia mais aqui .

Uma diferença adicional é que, quando adicionamos as várias inputs no Dicionário, a ordem em que as inputs são adicionadas é mantida. Quando recuperarmos os itens do Dicionário, obteremos os registros na mesma ordem em que os inserimos. Considerando que Hashtable não preserva a ordem de inserção.

De acordo com o que vejo usando o .NET Reflector :

 [Serializable, ComVisible(true)] public abstract class DictionaryBase : IDictionary, ICollection, IEnumerable { // Fields private Hashtable hashtable; // Methods protected DictionaryBase(); public void Clear(); . . . } Take note of these lines // Fields private Hashtable hashtable; 

Portanto, podemos ter certeza de que o DictionaryBase usa um HashTable internamente.