Por que as entradas na ordem de adição em um dicionário .net?

Question

Eu só vi esse comportamento e estou um pouco surpreso com isso ...

Se eu adicionar 3 ou 4 elementos para um dicionário, e depois fazer um "For Each" para obter todas as chaves, eles aparecem na mesma ordem que eu adicionei-los.

A razão isto me surpreende é que um dicionário é suposto ser um HashTable internamente, então eu esperava que as coisas saem em qualquer ordem (ordenada pelo hash da chave, certo?)

O que estou ausente aqui? É este um comportamento que posso contar com?

EDIT: OK, eu já de muitas das razões pelas quais este pode acontecem pensado (como a lista separada de entradas, se esta é uma coincidência, etc). A minha pergunta é, será que alguém sabe como isso realmente funciona?

Answer 1

Se você usar o .NET Reflector nas bibliotecas de classe 3.5 você pode ver que a implementação de dicionário na verdade armazena os itens em uma matriz (que é redimensionado conforme necessário), e índices de hashes em que array. Ao receber as chaves, ele ignora completamente o hashtable e itera sobre a matriz de itens. Por esta razão, você vai ver o comportamento que você descreveu uma vez que novos itens são adicionados ao final da matriz. Parece que se você fizer o seguinte:

add 1
add 2
add 3
add 4
remove 2
add 5

você vai voltar 1 5 3 4 porque reutiliza espaços vazios.

É importante notar, como muitos outros tem, você não pode contar com esse comportamento no futuro (ou passado) releases. Se você quer que seu dicionário a ser classificadas, em seguida, há um SortedDictionary classe para esta finalidade.

Answer 2

A Recupera dicionário itens em ordem hash. O fato de que eles saíram, a fim de inserção foi uma coincidência total.

A documentação do MSDN diz:

A ordem das chaves no KeyCollection não é especificado, mas é da mesma ordem que os valores associados no ValueCollection retornado pela propriedade valores.

Answer 3

Você não pode contar com esse comportamento, mas não é surpreendente.

Pense em como você poderia implementar iteração chave para uma tabela hash simples. Você precisará iterar sobre todos os baldes de hash, ou não tinham nada neles. Obtendo um pequeno conjunto de dados de um grande hashtable pode ser ineficiente.

Por isso, pode ser uma boa otimização para manter uma lista separada, duplicado de chaves. Usando uma lista duplamente ligada você ainda receber inserção de tempo constante / delete. (Você iria manter um ponteiro na parte de trás balde hashtable a esta lista.) Dessa forma, a iteração através da lista de chaves depende apenas do número de entradas, e não sobre o número de baldes.

Answer 4

Eu acho que isso vem do velho .NET 1.1 vezes em que você tinha dois tipos de dicionários "ListDictionary" e "HybridDictionary". ListDictionary era um dicionário implementado internamente como um lista ordenada e foi recomendado por "pequenos conjuntos de entradas". Então você tinha HybridDictionary , que foi inicialmente organizada internamente como uma lista, mas se ele cresceu mais do que um limite configurável se tornaria uma tabela hash. Isso foi feito porque dicionários historicamente adequadas à base de hash foram considerados caros. Agora, um dia que não faz muito sentido, mas suponho .NET apenas com base é nova classe genérica Dictionary no velho HybridDictionary.

Nota : De qualquer forma, como alguém já apontou, você deve não contagem na ordem do dicionário para qualquer coisa

Answer 5

A citação de MSDN :

A ordem das chaves no Dictionary <(Of <(TKey, TValue>)>). KeyCollection é não especificado, mas é a mesma ordem como os valores associados no Dictionary <(Of <(TKey, TValue>)>). ValueCollection retornado pelo Dictionary <(Of <(TKey, TValue>)>). Os valores de propriedade.

Answer 6

O que chaves fez você adicionar com em seu teste, e em que ordem?

Answer 7

As entradas podem estar todos no mesmo balde de hash no dicionário. Cada balde é provavelmente uma lista de entradas no balde. Isso explicaria as entradas que vêm em ordem novamente.

Answer 8

Pelo que eu sei que isso não deve ser um comportamento para confiar. Para verificar rapidamente usar os mesmos elementos e alterar a ordem em que você adicioná-los ao dicionário. Você vai ver se você pegá-los de volta na ordem em que foram adicionados, ou era apenas uma coincidência.

Answer 9

Até um certo tamanho da lista é mais barato para apenas verificar todas as entradas em vez de hashing. Isso é provavelmente o que está acontecendo.

Adicionar 100 ou 1000 itens e ver se eles ainda estão na mesma ordem.

Answer 10

Eu odeio esse tipo de "by design" funcionalidades. Eu acho que quando dando sua classe um nome tão genérico como "dicionário", ele também deve se comportar "como geralmente se espera". Por exemplo std :: map sempre mantém seus valores-chave classificadas.

Edit:. Aparentemente solução é usar SortedDictionary, que se comporta de forma semelhante a std :: map

Answer 11

A pergunta e muitas das respostas parecem não entender o propósito de uma tabela hash ou dicionário. Estas estruturas de dados têm comportamentos não especificado em relação à enumeração dos valores (ou de fato as chaves) dos itens contidos na estrutura de dados.

O propósito de um dicionário ou hashtable é ser capaz de pesquisar de forma eficiente um valor específico dada uma chave conhecida. A implementação interna de qualquer dicionário ou Hashtable deve prever essa eficiência em pesquisas, mas não precisa fornecer qualquer comportamento específico em relação à enumerações ou "para cada" tipo iterações sobre os valores ou chaves.

Em suma, a estrutura de dados interna pode armazenar e enumerar estes valores em qualquer forma que se deseje, incluindo a ordem em que foram inseridos.