c# - sort - using system collections generic




Por que o dicionário é preferível ao Hashtable? (12)

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


A Hashtable é uma estrutura de dados fracamente tipada, portanto, você pode adicionar chaves e valores de qualquer tipo à Hashtable . A classe 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.


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 implementação de um dicionário. Um típico, e pode ser o padrão no .NET, mas não é, por definição, o único.

Você poderia igualmente implementar um dicionário com uma lista vinculada ou uma árvore de busca, mas não seria tão eficiente (para alguma métrica eficiente).


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

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


Em .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 memória definido para o boxe.


Mais uma diferença que eu posso descobrir é:

Não podemos usar o Dictionary <KT, VT> (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.


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 classe 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 função 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.


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 sincronização.

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 coleções. Além disso, o design não é totalmente protegido contra condições de corrida.

As classes de coleção do .NET Framework 2.0, como List<T>, Dictionary<TKey, TValue> etc., não fornecem nenhuma sincronização de thread; o código do usuário deve fornecer toda a sincronização 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 classes de coleções simultâneas no .NET Framework. Leia mais here .

Uma diferença adicional é que, quando adicionamos as várias entradas no Dicionário, a ordem em que as entradas 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.


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

Se você quis dizer "por que usamos a classe Dictionary<TKey, TValue> vez da classe Hashtable ?", Então é uma resposta fácil: Dictionary<TKey, TValue> é um tipo genérico, Hashtable não é. Isso significa que você obtém segurança de tipo com Dictionary<TKey, TValue> , porque não é possível inserir qualquer objeto aleatório nele e não é necessário converter os valores obtidos.

Curiosamente, a implementação do Dictionary<TKey, TValue> 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

Source


Um objeto Hashtable consiste em intervalos que contêm os elementos da coleção. Um bucket é um subgrupo virtual de elementos dentro da Hashtable, o que torna a pesquisa e a recuperação mais fáceis e rápidas 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 (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


Collections e Generics são úteis para lidar com grupos de objetos. No .NET, todos os objetos de coleções 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 objeto 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, por isso não há necessidade de 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<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);
        }
    }
}

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

  • Genérico <<< >>> Não Genérico
  • Precisa de sincronização 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 == acesso 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):

  • ConcurrentDictionary - thread safe (pode ser acessado com segurança de vários threads simultaneamente)
  • HybridDictionary - desempenho 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

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<string, string> <NameOfDictionaryVar> = new Dictionary<string, string>();

  • 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 dicionário 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.





data-structures