Por que o dicionário prefere o Hashtable em C #?

1396

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

Nakul Chaudhary
fonte
21
> Isso não é necessariamente verdade. Uma tabela de hash é uma implementação de um dicionário. Um exemplo disso, e pode ser o padrão no .NET, mas não é, por definição, o único. Não tenho certeza de que isso seja exigido pelo padrão ECMA, mas a documentação do MSDN claramente o chama de implementada como uma hashtable. Eles ainda fornecem a classe SortedList para momentos em que uma alternativa é mais razoável.
Promit 17/04
15
@ Promit Eu sempre pensei que Dictionaryera uma implementação do Hashtable.
precisa saber é o seguinte
2
Penso que a razão é que, em um dicionário, você pode definir o tipo da chave e o valor para sua própria escolha. o Hashtable pode apenas pegar objetos e salvar os pares com base no hash (de object.GetHashCode ()).
Radinator
2
@ Dan Sua reivindicação está totalmente equivocada ... uma tabela de hash contém apenas uma instância de cada chave e uma pesquisa nunca gera várias entradas; se você deseja associar vários valores a cada chave, torne o valor da tabela de hash uma lista de valores. Não existe uma estrutura de dados como "um dicionário" ... Dicionário é simplesmente o nome que algumas bibliotecas usam para sua tabela de hash. por exemplo, a tabela de hash não genérica do C # é chamada HashTable. Quando eles adicionaram genéricos ao idioma, eles chamaram a versão genérica Dictionary. Ambas são tabelas de hash.
Jim Balter
3
@Dan Sua reivindicação está errada ... uma tabela de hash ( en.wikipedia.org/wiki/Hash_table ) é uma implementação específica de um dicionário, também conhecido como um array associativo ( en.wikipedia.org/wiki/Associative_array ) e, sendo um dicionário, contém apenas uma instância de cada chave e uma pesquisa nunca gera várias entradas; se você deseja associar vários valores a cada chave, torne o valor da tabela de hash uma lista de valores. E as classes .NET Dictionary e Hashtable são ambas tabelas de hash.
Jim Balter

Respostas:

1568

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

Se você quis dizer "por que usamos a Dictionary<TKey, TValue>classe em vez doHashtable classe?", Então é uma resposta fácil: Dictionary<TKey, TValue>é um tipo genérico, Hashtablenão é. Isso significa que você obtém segurança de digitação Dictionary<TKey, TValue>, porque não pode inserir nenhum objeto aleatório nele e não precisa converter os valores que retirar.

Curiosamente, o Dictionary<TKey, TValue> implementação no .NET Framework é baseada em Hashtable, como você pode ver neste comentário em seu código-fonte:

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

Fonte

Michael Madsen
fonte
393
E também coleções genéricas são muito mais rápido porque não há nenhuma boxing / unboxing
Chris S
6
Não tenho certeza sobre um Hashtable com a afirmação acima, mas para ArrayList vs List <T> é verdade
Chris S
36
O Hashtable usa Object para armazenar as coisas internamente (apenas uma maneira não genérica de fazê-lo), portanto, também seria necessário colocar a caixa / unbox.
Guvante 17/04/09
16
@BrianJ: "tabela de hash" (duas palavras) é o termo de ciência da computação para esse tipo de estrutura; Dicionário é uma implementação específica. Uma HashTable corresponde aproximadamente a um Dictionary <objeto, objeto> (embora com interfaces ligeiramente diferentes), mas ambas são implementações do conceito de tabela de hash. E, é claro, apenas para confundir ainda mais as coisas, alguns idiomas chamam suas tabelas de hash de "dicionários" (por exemplo, Python) - mas o termo apropriado para CS ainda é tabela de hash.
Michael Madsen
32
@ BrianJ: Ambos HashTable(classe) e Dictionary(classe) são tabelas de hash (conceito), mas a HashTablenão é um Dictionary, nem é um Dictionarya HashTable. Eles são usados ​​de formas muito semelhantes e Dictionary<Object,Object>podem agir da mesma maneira não digitada que a HashTable, mas não compartilham nenhum código diretamente (embora as partes provavelmente sejam implementadas de maneira muito semelhante).
Michael Madsen
625

Dictionary<<< >>> Hashtablediferenças:

  • Genéricos <<< >>> Não genérico
  • Precisa de sincronização de encadeamento próprio <<< >>> Oferece versão segura de encadeamento através do Synchronized()método
  • Item enumerado: KeyValuePair<<< >>> Item enumerado:DictionaryEntry
  • Mais recente (> .NET 2.0 ) <<< >>> Mais antiga (desde .NET 1.0 )
  • está em System.Collections.Generic <<< >>> está em System.Collections
  • Solicitação para chave não existente gera exceção <<< >>> Solicitação para chave não existente retorna nulo
  • potencialmente um pouco mais rápido para tipos de valor <<< >>> um pouco mais lento (precisa de boxe / unboxing) para tipos de valor

Dictionary/ Hashtablesemelhanças:

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

Coleções .NET similares (candidatas a serem usadas em vez de Dictionary e Hashtable):

  • ConcurrentDictionary- thread safe (pode ser acessado com segurança de vários threads simultaneamente)
  • HybridDictionary- desempenho otimizado (para poucos itens e também para muitos itens)
  • OrderedDictionary- valores podem ser acessados ​​via índice int (por ordem em que os itens foram adicionados)
  • SortedDictionary- itens classificados automaticamente
  • StringDictionary- fortemente tipado e otimizado para strings
Marcel Toth
fonte
11
@ Guillaume86, é por isso que você usa TryGetValue vez msdn.microsoft.com/en-us/library/bb347013.aspx
Trident D'Gao
2
+1 para StringDictionary... btw StringDictionarynão é o mesmo de Dictionary<string, string>quando você usa o construtor padrão.
Cheng Chen
O ParallelExtensionsExtras @ code.msdn.microsoft.com/windowsdesktop/… contém um ObservableConcurrentDictionary, que é uma ótima ligação de firmas e simultaneidade.
precisa saber é o seguinte
3
explicação incrível, é muito bom que você também listou as semelhanças para diminuir as perguntas que podem vem à mente de um
mkb
178

Porque Dictionaryé uma classe genérica ( Dictionary<TKey, TValue>), para que o acesso ao seu conteúdo seja seguro para o tipo (ou seja, você não precisa converter a partir de Object, como faz com a Hashtable).

Comparar

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

para

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

No entanto, Dictionaryé implementado como tabela de hash internamente, portanto tecnicamente funciona da mesma maneira.

gius
fonte
88

FYI: No .NET, o Hashtablethread é seguro para uso por vários threads de leitor e um único thread de escrita, enquanto em Dictionarypúblico membros estáticos são seguros, mas qualquer membro da instância não tem garantia de thread.

Tivemos que mudar todos os nossos dicionários por Hashtablecausa disso.

user38902
fonte
10
Diversão. O código-fonte do Dicionário <T> parece muito mais limpo e rápido. Talvez seja melhor usar o Dictionary e implementar sua própria sincronização. Se as leituras do Dicionário absolutamente precisam estar atualizadas, basta sincronizar o acesso aos métodos de leitura / gravação do Dicionário. Seria muito travamento, mas estaria correto.
Triynko 14/05
10
Como alternativa, se suas leituras não precisarem ser absolutamente atuais, você pode tratar o dicionário como imutável. Você pode pegar uma referência ao Dicionário e obter desempenho sem sincronizar leituras (já que é imutável e inerentemente seguro para threads). Para atualizá-lo, você constrói uma cópia atualizada completa do Dicionário em segundo plano e depois troca a referência com Interlocked.CompareExchange (assumindo um único segmento de gravação; vários segmentos de gravação exigiriam a sincronização das atualizações).
Triynko 14/05
38
O .NET 4.0 adicionou a ConcurrentDictionaryclasse que possui todos os métodos públicos / protegidos implementados para serem seguros para threads. Se você não precisa de plataformas de suporte legado este iria deixá-lo substituir o Hashtableem código multithreaded: msdn.microsoft.com/en-us/library/dd287191.aspx
Dan é Fiddling por Firelight
anônimo ao resgate. Resposta legal.
Unkulunkulu
5
Lembro-me de ler que o HashTable é apenas seguro para threads entre leitor e gravador no cenário em que as informações nunca são excluídas da tabela. Se um leitor estiver solicitando um item que está na tabela enquanto um item diferente estiver sendo excluído e o leitor procurar em mais de um local, é possível que, enquanto o leitor estiver pesquisando, o escritor possa mover o item de um local que não foi examinado para outro, resultando em um relatório falso de que o item não existe.
Supercat 13/11
68

No .NET, a diferença entre Dictionary<,>e HashTableé principalmente 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 boxe reduzido, mas isso não é tão grande quanto as pessoas tendem a pensar) termos de desempenho - existe um custo definido de memória para o boxe).

Marc Gravell
fonte
34

As pessoas estão dizendo que um dicionário é o mesmo que uma tabela de hash.

Isto não é necessariamente verdade. Uma tabela de hash é uma maneira de implementar um dicionário. Um exemplo disso, e pode ser o padrão no .NET na Dictionaryclasse, mas não é, por definição, o único.

Você também pode implementar um dicionário usando uma lista vinculada ou uma árvore de pesquisa, mas não seria tão eficiente (para algumas métricas de eficiência).

rix0rrr
fonte
4
Os documentos da Microsoft dizem: "A recuperação de um valor usando sua chave é muito rápida, próxima a O (1), porque a classe Dictionary <(Of <(TKey, TValue>)>) é implementada como uma tabela de hash." - então você deve ter uma hashtable garantida ao lidar com Dictionary<K,V>. IDictionary<K,V>Poderia ser qualquer coisa, embora :)
snemarch
13
@ rix0rrr - Acho que você entendeu isso de trás para frente, um dicionário usa uma HashTable e não uma HashTable usa um dicionário.
Joseph Hamilton
8
@JosephHamilton - rix0rrr acertou: "Uma tabela de hash é uma implementação de um dicionário ." Ele quer dizer o conceito "dicionário", não a classe (observe as letras minúsculas). Conceitualmente, uma tabela de hash implementa uma interface de dicionário. No .NET, o Dictionary usa uma tabela de hash para implementar o IDictionary. É confuso;)
Robert Hensing
Eu estava falando no .NET, já que foi o que ele mencionou em sua resposta.
Joseph Hamilton
2
@ JosephphHamilton: implementos (ou implementação de ) nem remotamente significam a mesma coisa que usos . Muito pelo contrário. Talvez fosse mais claro se ele o dissesse de maneira um pouco diferente (mas com o mesmo significado): "uma tabela de hash é uma maneira de implementar um dicionário". Ou seja, se você deseja a funcionalidade de um dicionário, uma maneira de fazer isso (para implementar o dicionário) é usar uma hashtable.
Home
21

Collections& Genericssão úteis para manipular grupos de objetos. No .NET, todos os objetos de coleções IEnumerableficam sob a interface , que por sua vez possui ArrayList(Index-Value))& HashTable(Key-Value). Após o .NET framework 2.0, ArrayList& HashTableforam substituídos por List& Dictionary. Agora, o Arraylist& HashTablenão é mais usado nos projetos atuais.

Chegando à diferença entre HashTable& Dictionary, Dictionaryé genérico onde, como Hastablenão é genérico. Podemos adicionar qualquer tipo de objeto HashTable, mas durante a recuperação, precisamos convertê-lo no tipo necessário. Portanto, não é do tipo seguro. Mas dictionary, enquanto se declara, podemos especificar o tipo de chave e valor, portanto, não há necessidade de converter durante a recuperação.

Vejamos 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<int, string> dt = new Dictionary<int, string>();
        dt.Add(1, "One");
        dt.Add(2, "Two");
        dt.Add(3, "Three");
        foreach (KeyValuePair<int, String> kv in dt)
        {
            Console.WriteLine(kv.Key + " " + kv.Value);
        }
    }
}
Sujit
fonte
2
em vez de atribuir explicitamente o tipo de dados para KeyValuePair, poderíamos usar var. Portanto, isso reduziria a digitação - foreach (var kv em dt) ... apenas uma sugestão.
Ron
16

Dicionário:

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

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

  • Somente membros estáticos públicos são seguros para threads.

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

    Exemplo: Dictionary<string, string> <NameOfDictionaryVar> = new Dictionary<string, string>();

  • Dictionay é uma implementação do Hashtable com segurança de tipo Keyse Valuesé fortemente tipada.

Hashtable:

  • Retorna nulo se tentarmos encontrar uma chave que não existe.

  • É mais lento que o dicionário porque requer boxe e unboxing.

  • Todos os membros em um Hashtable são seguros para threads,

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

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

Altaf Patel
fonte
"Ele retorna / lança Exceção se tentarmos encontrar uma chave que não existe." Não se você usarDictionary.TryGetValue
Jim Balter
16

O artigo Exame extensivo de estruturas de dados usando c # no MSDN afirma que também há uma diferença na estratégia de resolução de colisões :

A classe Hashtable usa uma técnica denominada rehashing .

A reformulação funciona da seguinte maneira: existe um conjunto de funções diferentes de hash, H 1 ... H n , e ao inserir ou recuperar um item da tabela de hash, inicialmente a função de hash H 1 é usada. Se isso levar a uma colisão, H 2 é tentado e, em seguida, até H n, se necessário.

O dicionário usa uma técnica chamada encadeamento .

Com o rehashing, no caso de uma colisão, o hash é recalculado e o novo slot correspondente a um hash é tentado. 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 são mapeados para esse intervalo. No caso de uma colisão, o elemento em colisão é anexado à lista do bucket.

alexandrekow
fonte
16

Desde o .NET Framework 3.5, também existe um HashSet<T>que fornece todos os prós do Dictionary<TKey, TValue>se você precisar apenas das chaves e sem valores.

Portanto, se você usar ae Dictionary<MyType, object>sempre definir o valor para nullsimular a tabela de hash do tipo seguro, considere mudar para a HashSet<T>.

Oliver
fonte
14

A Hashtableé uma estrutura de dados de tipo fraco, para que você possa adicionar chaves e valores de qualquer tipo ao Hashtable. A Dictionaryclasse é uma Hashtableimplementação com segurança de tipo e as chaves e valores são fortemente digitados. Ao criar uma Dictionaryinstância, você deve especificar os tipos de dados para a chave e o valor.

carne
fonte
11

Observe que o MSDN diz: "A classe Dictionary <(Of <(TKey, TValue>)>) é implementada como uma tabela de hash ", não a "Dictionary <(Of <(Of <(TKey, TValue>)>)) a classe é implementada como uma HashTable "

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

No .NET 1.0, os genéricos não existiam; é aqui que o HashTable e o ArrayList começaram originalmente.

Brant
fonte
Você pode corrigir essa cotação do MSDN? Algo está faltando ou errado; não é gramatical e um tanto incompreensível.
Peter Mortensen
10

HashTable:

A chave / valor será convertida em um tipo de objeto (boxe) durante o armazenamento no heap.

A chave / valor precisa ser convertida no tipo desejado durante a leitura da pilha.

Essas operações são muito caras. Precisamos evitar o boxe / unboxing, tanto quanto possível.

Dicionário: variante genérica do HashTable.

Sem boxe / unboxing. Não são necessárias conversões.

Siva Sankar Gorantla
fonte
8

Um objeto Hashtable consiste em depósitos que contêm os elementos da coleção. Um bucket é um subgrupo virtual de elementos no Hashtable, o que facilita a pesquisa e a recuperação e a recuperação mais rápida do que na maioria das coleções .

A classe Dictionary tem a mesma funcionalidade que a classe Hashtable. Um dicionário de um tipo específico (que não seja Objeto) tem melhor desempenho que um Hashtable para tipos de valor porque os elementos do Hashtable são do tipo Object e, portanto, o boxe e o unboxing geralmente ocorrem se o armazenamento ou a recuperação de um tipo de valor.

Para leitura adicional: Hashtable e Tipos de coleção de dicionário

mparkuk
fonte
7

Outra diferença importante é que o Hashtable é seguro para threads. O Hashtable possui segurança de encadeamento integrada para vários leitores / gravador único (MR / SW), o que significa que o Hashtable permite UM gravador junto com vários leitores sem travar.

No caso do Dictionary, não há segurança de threads; se você precisar de segurança de encadeamento, deverá implementar sua própria sincronização.

Para elaborar mais:

O Hashtable fornece alguma segurança de thread através do Synchronized propriedade, que retorna um invólucro à prova de encadeamento em torno da coleção. O wrapper funciona bloqueando a coleção inteira em todas as operações de adição ou remoção. Portanto, cada encadeamento que está tentando acessar a coleção deve aguardar sua vez de bloquear o único bloqueio. Isso não é escalável e pode causar degradação significativa no desempenho de grandes coleções. Além disso, o design não está completamente protegido das condições da corrida.

As classes de coleção do .NET Framework 2.0 como List<T>, Dictionary<TKey, TValue>, etc., não fornecem sincronização de threads; o código do usuário deve fornecer toda a sincronização quando itens são adicionados ou removidos em vários threads simultaneamente

Se você precisar de segurança de tipo e segurança de thread, use classes de coleções simultâneas no .NET Framework. Leia mais aqui .

Uma diferença adicional é que, quando adicionamos várias entradas no Dicionário, a ordem na qual as entradas são adicionadas é mantida. Quando recuperamos os itens do Dictionary, obtemos os registros na mesma ordem em que os inserimos. Enquanto o Hashtable não preserva o pedido de inserção.

NullReference
fonte
Pelo que entendi, as Hashsetgarantias de segurança de encadeamento MR / SW em cenários de uso que não envolvem exclusões . Eu acho que pode ter sido planejado para ser totalmente seguro para MR / SW, mas o manuseio de exclusões com segurança aumenta bastante as despesas com segurança de MR / SW. Embora o design de Dictionarypoderia oferecer segurança de MR / SW a um custo mínimo em cenários sem exclusão, acho que a MS queria evitar tratar os cenários sem exclusão como "especiais".
supercat 14/02
5

Mais uma diferença que eu posso descobrir é:

Não podemos usar o Dicionário <KT, VT> (genéricos) com serviços da web. O motivo é que nenhum padrão de serviço da web suporta o padrão de genéricos.

Peter Mortensen
fonte
Podemos usar listas genéricas (List <string>) no serviço da Web baseado em sabão. Porém, não podemos usar dicionário (ou hashtable) em um serviço da web. Eu acho que a razão para isso é que o .net xmlserializer não pode manipular objetos de dicionário.
Siddharth
5

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

Você pode inserir qualquer tipo de valor no HashTable e, às vezes, isso pode gerar uma exceção. Mas Dictionary<int>só aceitará valores inteiros e da mesma forma Dictionary<string>somente aceitará strings.

Então, é melhor usar em Dictionary<>vez de HashTable.

Kishore Kumar
fonte
0

Na maioria das linguagens de programação, os dicionários são preferidos às hashtables

Eu não acho que isso seja necessariamente verdade, a maioria das línguas possui uma ou outra, dependendo da terminologia preferida .

No C #, no entanto, o motivo claro (para mim) é que o C # HashTables e outros membros do espaço para nome System.Collections são amplamente obsoletos. Eles estavam presentes no c # V1.1. Eles foram substituídos do C # 2.0 pelas classes Generic no espaço para nome System.Collections.Generic.

kristianp
fonte
Uma das vantagens de uma hashtable em relação a um dicionário é que, se uma chave não existir em um dicionário, ela gera um erro. Se uma chave não existir em uma hashtable, ela retornará nulo.
Bill Norman
No C #, eu ainda evitaria usar System.Collections.Hashtable, pois eles não têm a vantagem de genéricos. Você pode usar o TryGetValue ou HasKey do Dictionary se não souber se a chave existe.
22419 kristianp
Opa, não HasKey, deve ser ContainsKey.
22419
-3

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 uma HashTable internamente.

Peter Mortensen
fonte
16
System.Collections.Generic.Dictionary <TKey, TValue> não deriva do DictionaryBase.
Snemarch 23/09/10
"Portanto, podemos ter certeza de que o DictionaryBase usa uma HashTable internamente." - Isso é legal, mas não tem nada a ver com a pergunta.
Jim Balter