A ordem dos elementos no Dicionário

107

Minha pergunta é sobre enumerar os elementos do Dicionário

// Dictionary definition
private Dictionary<string, string> _Dictionary = new Dictionary<string, string>();

// add values using add

_Dictionary.Add("orange", "1");
_Dictionary.Add("apple", "4");
_Dictionary.Add("cucumber", "6");

// add values using []

_Dictionary["banana"] = 7;
_Dictionary["pineapple"] = 7;

// Now lets see how elements are returned by IEnumerator
foreach (KeyValuePair<string, string> kvp in _Dictionary)
{
  Trace.Write(String.Format("{0}={1}", kvp.Key, kvp.Value));
}

Em que ordem os elementos serão enumerados? Posso forçar a ordem em ordem alfabética?

Capitão Comic
fonte

Respostas:

125

A ordem dos elementos em um dicionário não é determinística. A noção de ordem simplesmente não é definida para hashtables. Portanto, não conte com a enumeração na mesma ordem em que os elementos foram adicionados ao dicionário. Isso não é garantido.

Citação do doc :

Para fins de enumeração, cada item no dicionário é tratado como uma KeyValuePair<TKey, TValue>estrutura que representa um valor e sua chave. A ordem em que os itens são devolvidos é indefinida.

Darin Dimitrov
fonte
1
Mas existe OrderedDictionary .
Peter Mortensen de
28

Se você quiser que os elementos sejam ordenados, use um OrderedDictionary . Um dicionário / hastable comum é ordenado apenas em algum sentido do layout de armazenamento.

Trigo mitch
fonte
10
OrderedDictionary está errado na maioria dos casos. Não é ordenado por chave ou valor, mas por um índice interno. SortedDictionary é aquele que é ordenado de uma forma que o usuário possa manipular (tecla padrão)
Offler
2
A pergunta é sobre a ordenação em ordem alfabética (assumindo que o questionador está falando sobre a chave). Um dicionário ordenado, se eu entendi a documentação corretamente, cuspirá os elementos na ordem em que foram inseridos, ou seja, não em ordem alfabética, mas usando o índice interno. Um SortedDictionary é provavelmente o mais adequado para a pergunta do usuário.
mattpm
28

Você sempre pode usar SortedDictionary para isso. Observe que o dicionário é ordenado por chave, por padrão, a menos que um comparador tenha sido especificado.

Estou cético quanto ao uso de OrderedDictionarypara o que você deseja, pois a documentação diz que:

Os elementos de um OrderedDictionary não são classificados pela chave, ao contrário dos elementos de uma classe SortedDictionary.

Adriano Carneiro
fonte
É importante notar que SortedDictionary<K,V>é implementado como uma árvore de busca binária, o que dá às suas operações complexidade de tempo e espaço diferente em comparação com a baseada em hashtable Dictionary<K,V>. Se os usuários precisam de uma estrutura de O(1)inserção / exclusão de hashtable e também desejam iterar sobre os elementos na ordem das chaves, então eles deveriam dict.Keys.OrderBy( k => k ).Select( k => dict[k] )(ao custo de O(n)espaço e O( n log n )tempo) para o OrderBy()(que precisará armazenar toda a coleção de chaves em uma lista interna )
Dai
12

Os itens serão devolvidos na ordem em que foram armazenados fisicamente no dicionário, o que depende do código hash e da ordem em que os itens foram adicionados. Portanto, a ordem parecerá aleatória e, à medida que as implementações mudam, você nunca deve depender de que a ordem permaneça a mesma.

Você pode pedir os itens ao enumerá-los:

foreach (KeyValuePair<string, string> kvp in _Dictionary.OrderBy(k => k.Value)) {
  ...
}

No framework 2.0, você primeiro teria que colocar os itens em uma lista para classificá-los:

List<KeyValuePair<string, string>> items = new List<KeyValuePair<string, string>>(_Dictionary);
items.Sort(delegate(KeyValuePair<string, string> x, KeyValuePair<string, string> y) { return x.Value.CompareTo(y.Value); });
foreach (KeyValuePair<string,string> kvp in items) {
  ...
}
Guffa
fonte
11

Para um OrderedDictionary:

 var _OrderedDictionary = new System.Collections.Specialized.OrderedDictionary();

_OrderedDictionary.Add("testKey1", "testValue1");
_OrderedDictionary.Add("testKey2", "testValue2");
_OrderedDictionary.Add("testKey3", "testValue3");

var k = _OrderedDictionary.Keys.GetEnumerator();
var v = _OrderedDictionary.Values.GetEnumerator();

while (k.MoveNext() && v.MoveNext()) {
    var key = k.Current; var value = v.Current;
}

Os itens são devolvidos na ordem em que são adicionados.

Barton
fonte
5

Matrizes associativas (também conhecidas como tabelas de hash) não são ordenadas, o que significa que os elementos podem ser ordenados de qualquer maneira imaginável.

NO ENTANTO, você pode obter as chaves do array (apenas as chaves), ordená-las alfabeticamente (por meio de uma função de classificação) e depois trabalhar nisso.

Não posso fornecer um exemplo de C # porque não conheço a linguagem, mas isso deve ser o suficiente para que você continue.

Tim Čas
fonte