Por que um dictionary “não é encomendado”?

Eu li isso em resposta a muitas perguntas aqui. Mas o que exatamente isso significa?

var test = new Dictionary(); test.Add(0, "zero"); test.Add(1, "one"); test.Add(2, "two"); test.Add(3, "three"); Assert(test.ElementAt(2).Value == "two"); 

O código acima parece funcionar como esperado. Então, de que maneira um dictionary é considerado desordenado? Em que circunstâncias o código acima poderia falhar?

   

    Bem, por um lado, não está claro se você espera que isso seja ordem de inserção ou ordem-chave . Por exemplo, o que você esperaria que o resultado fosse se você escrevesse:

     var test = new Dictionary(); test.Add(3, "three"); test.Add(2, "two"); test.Add(1, "one"); test.Add(0, "zero"); Console.WriteLine(test.ElementAt(0).Value); 

    Você esperaria “três” ou “zero”?

    Acontece que a implementação atual preserva a ordenação de inserção desde que você nunca exclua nada – mas você não deve confiar nisto . É um detalhe de implementação e isso pode mudar no futuro.

    Deleções também afetam isso. Por exemplo, o que você esperaria que o resultado desse programa fosse?

     using System; using System.Collections.Generic; class Test { static void Main() { var test = new Dictionary(); test.Add(3, "three"); test.Add(2, "two"); test.Add(1, "one"); test.Add(0, "zero"); test.Remove(2); test.Add(5, "five"); foreach (var pair in test) { Console.WriteLine(pair.Key); } } } 

    Na verdade, é (na minha checkbox) 3, 5, 1, 0. A nova input para 5 usou a input desocupada usada anteriormente por 2. Isso também não será garantido.

    Rehashing (quando o armazenamento subjacente do dictionary precisa ser expandido) pode afetar as coisas … todos os tipos de coisas.

    Apenas não o trate como uma coleção ordenada. Não é projetado para isso. Mesmo que isso aconteça agora, você está confiando em um comportamento não documentado que vai contra o propósito da aula.

    Um Dictionary representa uma tabela de hash e, em uma hashtable, não há noção de ordem.

    A documentação explica isso muito bem:

    Para fins de enumeração, cada item no dictionary é tratado como uma estrutura KeyValuePair que representa um valor e sua chave. A ordem em que os itens são retornados é indefinida.

    Há muitas boas ideias aqui, mas espalhadas, então vou tentar criar uma resposta que apresente melhor, mesmo que o problema tenha sido respondido.

    Primeiro, um dictionary não tem uma ordem garantida, portanto, você o usa apenas para procurar rapidamente uma chave e encontrar um valor correspondente, ou enumerar todos os pares de valores-chave sem se preocupar com o pedido.

    Se você quiser ordem, use um OrderedDictionary, mas a desvantagem é que a pesquisa é mais lenta, portanto, se você não precisa de um pedido, não o solicite.

    Dicionários (e HashMap em Java) usam hashing. Isso é O (1) tempo, independentemente do tamanho da sua tabela. Os dictionarys ordenados normalmente usam algum tipo de tree balanceada, que é O (log2 (n)), de modo que, quando seus dados crescem, o access fica mais lento. Para comparar, para 1 milhão de elementos, isso é da ordem de 2 ^ 20, então você teria que fazer na ordem de 20 pesquisas para uma tree, mas 1 para um mapa de hash. Isso é muito mais rápido.

    O hash é determinista. Não-determinismo significa que quando você hash (5) pela primeira vez, e você hash (5) na próxima vez, você ganha um lugar diferente. Isso seria completamente inútil.

    O que as pessoas queriam dizer é que, se você adicionar coisas a um dictionary, o pedido será complicado e estará sujeito a alterações sempre que você adicionar (ou possivelmente remover) um elemento. Por exemplo, imagine que a tabela hash possui 500k elementos e você tem 400k valores. Quando você adiciona mais um, você atinge o limite crítico porque precisa de cerca de 20% de espaço vazio para ser eficiente, por isso aloca uma tabela maior (digamos, 1 milhão de inputs) e re-hashes todos os valores. Agora eles estão todos em locais diferentes do que eram antes.

    Se você construir o mesmo dictionary duas vezes (leia minha declaração com atenção, THE SAME), receberá o mesmo pedido. Mas como Jon diz corretamente, não conte com isso. Muitas coisas podem fazer com que não seja o mesmo, mesmo o tamanho inicialmente alocado.

    Isso traz um excelente ponto. É muito, muito caro ter que resize um hashmap. Isso significa que você precisa alocar uma tabela maior e reinserir cada par de valores-chave. Portanto, vale a pena alocar 10x a memory de que ela precisa, em vez de ter que ocorrer um único crescimento. Conheça o seu tamanho de hashmap, e pré-aloque o suficiente se for possível, é uma grande vitória no desempenho. E se você tiver uma implementação ruim que não seja redimensionada, pode ser um desastre se você escolher um tamanho muito pequeno.

    Agora, o que Jon discutiu comigo em meu comentário em sua resposta foi que, se você adicionar objects a um Dicionário em duas execuções diferentes, obterá duas ordenações diferentes. É verdade, mas isso não é culpa do dictionary.

    Quando voce diz:

     new Foo(); 

    você está criando um novo object em um novo local na memory.

    Se você usar o valor Foo como a chave em um dictionary, sem outras informações, a única coisa que eles podem fazer é usar o endereço do object como a chave.

    Isso significa que

     var f1 = new Foo(1); var f2 = new Foo(1); 

    f1 e f2 não são o mesmo object, mesmo que tenham os mesmos valores.

    Então, se você fosse colocá-los em dictionarys:

     var test = new Dictionary(); test.Add(f1, "zero"); 

    não espere que seja o mesmo que:

     var test = new Dictionary(); test.Add(f2, "zero"); 

    mesmo se ambos f1 e f2 tiverem os mesmos valores. Isso não tem nada a ver com o comportamento determinista do Dicionário.

    Hashing é um tópico incrível em ciência da computação, meu favorito para ensinar em estruturas de dados.

    Confira Cormen e Leiserson para um livro de ponta em trees vermelho-preto vs. hashing Esse cara chamado Bob tem um ótimo site sobre hashing e hashes ideais: http://burtleburtle.net/bob

    A ordem não é determinista.

    Daqui

    Para fins de enumeração, cada item no dictionary é tratado como uma estrutura KeyValuePair que representa um valor e sua chave. A ordem em que os itens são retornados é indefinida.

    Talvez para as suas necessidades OrderedDictionary é o necessário.

    Eu não sei c # ou qualquer um dos .net, mas o conceito geral de um dictionary é que é uma coleção de pares de valor-chave.
    Você não acessa sequencialmente um dictionary como faria quando, por exemplo, iterava uma lista ou matriz.
    Você acessa tendo uma chave e depois descobre se há um valor para essa chave no dictionary e o que é.
    No seu exemplo, você publicou um dictionary com chaves numéricas que são seqüenciais, sem lacunas e em ordem crescente de inserção.
    Mas não importa em qual ordem você insere um valor para a chave ‘2’, você sempre obterá o mesmo valor ao consultar a chave ‘2’.
    Eu não sei se C # permite, eu acho que sim, ter tipos de chaves que não sejam números, mas, nesse caso, é o mesmo, não há nenhuma ordem explícita sobre as chaves.
    A analogia com um dictionary da vida real pode ser confusa, pois as chaves, que são as palavras, são ordenadas alfabeticamente para que possamos encontrá-las mais rapidamente, mas se não fossem, o dictionary funcionaria de qualquer maneira, porque a definição da palavra “Aardvark”. “teria o mesmo significado, mesmo que fosse depois de” Zebra “. Pense em um romance, por outro lado, mudar a ordem das páginas não faria sentido, já que elas são uma coleção ordenada em essência.

    A class Dictionary é implementada usando uma linked list por índice com matriz. Se nenhum item for removido, o armazenamento de apoio armazenará os itens em ordem. Quando um item é removido, no entanto, o espaço será marcado para reutilização antes da matriz ser expandida. Como conseqüência, se, por exemplo, dez itens forem adicionados a um novo dictionary, o quarto item for excluído, um novo item for adicionado e o dictionary for enumerado, o novo item provavelmente aparecerá em quarto lugar em vez de décimo, mas não há garantia de que diferentes versões do Dictionary irão lidar com as coisas da mesma maneira.

    IMHO, teria sido útil para a Microsoft documentar que um dictionary a partir do qual nenhum item é excluído irá enumerar itens na ordem original, mas que uma vez que qualquer item seja deletado, qualquer mudança futura no dictionary pode permutar arbitrariamente os itens. Manter tal garantia, desde que nenhum item seja excluído, seria relativamente barato para a maioria das implementações razoáveis ​​de dictionary; continuar a manter a garantia após os itens serem excluídos seria muito mais caro.

    Como alternativa, pode ser útil ter um AddOnlyDictionary que seja thread-safe para um único gravador simultaneamente com qualquer número de leitores e garantir a retenção de itens em sequência (observe que se itens forem adicionados apenas – nunca excluídos ou modificados de outra forma – Alguém pode tirar uma “foto” apenas observando quantos itens ela contém atualmente. Tornar um dictionary de uso geral seguro para thread é caro, mas adicionar o nível acima de segurança de thread seria barato. Observe que o uso eficiente de vários leitores de vários leitores não exigiria o uso de um bloqueio de leitor-gravador, mas poderia simplesmente ser tratado com o bloqueio de escritores e com o fato de os leitores não se incomodarem.

    A Microsoft não implementou um AddOnlyDictionary como descrito acima, é claro, mas é interessante notar que o ConditionalWeakTable thread-safe tem semânticas somente de adição, provavelmente porque – como notado – é muito mais fácil adicionar concorrência a collections apenas de add-ons do que para collections que permitem a exclusão.

    O dictionary , não SortedDictionary , é padronizado para sequência pelo pedido de inserção. Estranho o suficiente, você precisa declarar especificamente um SortedDictionary para ter um dictionary ordenado por ordem de string de chave:

     public SortedDictionary forecastMTX = new SortedDictionary();