.NET HashTable Vs Dictionary - O dicionário pode ser tão rápido?

276

Estou tentando descobrir quando e por que usar um dicionário ou um HashTable. Pesquisei um pouco aqui e encontrei pessoas falando sobre as vantagens genéricas do Dicionário com as quais concordo totalmente, o que leva a vantagem do boxe e do unboxing para um pequeno ganho de desempenho.

Mas eu também li que o Dicionário nem sempre retornará os objetos na ordem em que foram inseridos, coisa que está classificada. Onde, como um HashTable. Pelo que entendi, isso faz com que o HashTable seja muito mais rápido em algumas situações.

Minha pergunta é realmente, quais seriam essas situações? Estou errado nas minhas suposições acima? Quais situações você pode usar para escolher uma acima da outra (sim, a última é um pouco ambígua).

Jon
fonte
5
Eu não quero voto isso, mas seu carma é 7.777 e eu não quero ser o cara que estraga tudo isso para você.
CaptainMarvel

Respostas:

298

System.Collections.Generic.Dictionary<TKey, TValue>e as System.Collections.Hashtableclasses mantêm uma estrutura de dados da tabela de hash internamente. Nenhum deles garante a preservação da ordem dos itens.

Deixando de lado os problemas de boxe / unboxing, na maioria das vezes, eles devem ter desempenho muito semelhante.

A principal diferença estrutural entre eles é que Dictionarydepende do encadeamento (manutenção de uma lista de itens para cada depósito de tabela de hash) para resolver colisões, enquanto Hashtableusa o rehashing para resolução de colisão (quando ocorre uma colisão, tenta outra função de hash para mapear a chave para um depósito) .

Há pouco benefício em usar a Hashtableclasse se você estiver direcionando para o .NET Framework 2.0+. É efetivamente tornado obsoleto por Dictionary<TKey, TValue>.

Mehrdad Afshari
fonte
21
@ Jon- O encadeamento e rehashing é discutido em profundidade aqui- msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx
RichardOD
Obrigado a ambos. Acabei de encontrar essa página como Richard a publicou ... Iria perguntar sobre encadeamento, mas o site do MSDN é realmente útil!
Jon
6
@ Mehrdad - O que não está claro para mim sobre como as colisões são resolvidas é o seguinte: se várias chaves podem resultar no mesmo hash, como garantir que você obtenha o valor certo nas pesquisas, ou seja, como a função sabe qual elemento Retorna? No arquivo msdn.microsoft.com/pt-br/library/ms379571%28VS.80%29.aspx , diz: "Em vez de reprovar em caso de colisão, como é feito com a classe Hashtable, o Dicionário simplesmente encadeia qualquer colisão. na lista do balde ". Isso significa que, ao usar o Dictionary, as colisões não devem ser motivo de preocupação para o desenvolvedor?
Howiecamp
6
@ Howiecamp: Isso não é realmente muito diferente Hashtable. As tabelas de hash armazenam três informações em uma entrada: hash da chave, a própria chave e o valor. Para itens com hash igual, será necessário percorrer a lista para encontrar o item com chave igual e retornar seu valor. Isso também é verdade Hashtabletambém. Como desenvolvedor, usando Dictionarynormalmente, você não precisa se preocupar com isso.
Mehrdad Afshari
@Mehrdad Apenas para esclarecer, os objetos Hashtable e Dictionary armazenam a chave em si e ambos ocultam colisões do desenvolvedor?
precisa saber é o seguinte
111

Eu acho que isso não significa nada para você agora. Mas apenas para referência para pessoas que param por

Teste de desempenho - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable

Alocação de memória:

Teste de desempenho de uso de memória

Tempo usado para inserir:

Tempo usado para inserir

Tempo para pesquisar um item:

Tempo para pesquisar um item

Abdul Munim
fonte
Muito interessante que a lista classificada tenha uma pesquisa MAIS RÁPIDA que a hashtable. Eu pensei que hashtable é O (1) vs lista classificada O (logn). Aparentemente hashtable é uma merda. Eu nunca vou usá-lo.
John Henckel
@JohnHenckel não, a lista classificada tem uma pesquisa mais lenta. Maior coeficiente de desempenho significa melhor desempenho e melhor uso de memória. Portanto, a lista classificada tem o melhor uso de memória de acordo com os gráficos, mas é uma droga em outras áreas, como inserção e pesquisa.
C0DEF52
31

Diferenças entre Hashtable e Dicionário

Dicionário:

  • Dicionário retorna erro se tentarmos encontrar uma chave que não existe.
  • Dicionário mais rápido que um Hashtable, porque não há boxe e unboxing.
  • Dicionário é um tipo genérico, o que significa que podemos usá-lo com qualquer tipo de dados.

Hashtable:

  • Hashtable retorna null se tentarmos encontrar uma chave que não existe.
  • Hashtable mais lento que o dicionário, porque requer boxe e unboxing.
  • Hashtable não é um tipo genérico,
user2771704
fonte
24

Outra diferença importante é que o tipo Hashtable suporta vários leitores sem bloqueio e um único gravador ao mesmo tempo, enquanto o Dictionary não.

Steven
fonte
8
O Dicionário Concorrente suportará (.Net 4.0)
Tamilmaran 6/2
1
Não tenho certeza se entendi esta resposta. Olhando aqui msdn.microsoft.com/en-us/library/…, ele diz "Para oferecer suporte a vários gravadores , todas as operações no Hashtable devem ser feitas através do wrapper retornado pelo método Synchronized, desde que não haja threads lendo o objeto Hashtable. " Isso parece tornar o recurso "vários leitores sem bloqueio" bastante inútil, então voltamos a ter que bloquear todo o acesso ao Hashtable, assim como no Dictionary.
RenniePet
16

Artigo do MSDN: "A Dictionary<TKey, TValue>classe tem a mesma funcionalidade que a Hashtableclasse. A Dictionary<TKey, TValue> de um tipo específico (diferente de Object) tem melhor desempenho que um Hashtablepara tipos de valor porque os elementos de Hashtablesão do tipo Objecte, portanto, o boxe e o unboxing geralmente ocorrem se o armazenamento ou recuperando um tipo de valor ".

Link: http://msdn.microsoft.com/en-us/library/4yh14awz(v=vs.90).aspx

Juan Camilo Caro J.
fonte
11

Ambos são efetivamente da mesma classe (você pode ver a desmontagem). O HashTable foi criado primeiro antes do .Net possuir genéricos. Dicionário, no entanto, é uma classe genérica e oferece fortes benefícios de digitação. Eu nunca usaria o HashTable, pois o Dictionary não custa nada para você usar.

Adam Luter
fonte
8

Outra diferença importante é que Hashtableé seguro para threads. Hashtableintegrou segurança de encadeamento de vários leitores / gravador único (MR / SW), o que significa que Hashtablepermite UM gravador junto com vários leitores sem travar. No caso de Dictionarynão haver segurança de encadeamento, se você precisar de segurança de encadeamento, deverá implementar sua própria sincronização.

Para elaborar mais:

Hashtable, forneça alguma segurança de thread através da propriedade Synchronized, que retorna um wrapper seguro de thread 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 coleções grandes. Além disso, o design não está completamente protegido das condições da corrida.

As classes de recolha Framework 2,0 gosto List<T>, Dictionary<TKey, TValue>etc não fornecem qualquer sincronização de segmento; 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 digitar também segurança de thread, use classes de coleções simultâneas no .NET Framework. Leia mais aqui.

NullReference
fonte
3

Os dicionários têm a vantagem de ser do tipo genérico, o que o torna seguro e um pouco mais rápido devido à falta de boxe. A tabela de comparação a seguir (construída usando as respostas encontradas em uma postagem de pergunta do SO semelhante ) ilustra alguns dos outros motivos que suportam dicionários sobre tabelas de hash (ou vice-versa).

janeon
fonte
1

Se você se preocupa com a leitura, que sempre retornará os objetos na ordem em que são inseridos em um dicionário, consulte

OrderedDictionary - os valores podem ser acessados ​​por meio de um índice inteiro (por ordem em que os itens foram adicionados) SortedDictionary - os itens são classificados automaticamente

ToXinE
fonte
0

O dicionário é mais rápido que o hashtable, pois o dicionário é um tipo forte genérico. O Hashtable é mais lento, pois leva o objeto como tipo de dados, o que leva ao boxe e ao unboxing.

jitendra mahaapatro
fonte
2
phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx plz ler os comentários abaixo do artigo
Arvand
4
@Arvand Link quebrado - domínio à venda.
RenniePet