Порядок элементов в словаре

107

Мой вопрос касается перечисления элементов словаря

// 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));
}

В каком порядке будут перечислены элементы? Могу ли я сделать порядок в алфавитном порядке?

c# .net dictionary ienumerable Капитан Комикс
источник
1
возможный дубликат. Возвращает ли перечислитель словаря <TKey, TValue> пары значений ключа в том порядке, в котором они были добавлены? .Net
nawfal

Ответы:

125

Порядок элементов в словаре недетерминированный. Для хэш-таблиц понятие порядка просто не определено. Поэтому не полагайтесь на перечисление в том же порядке, в котором элементы были добавлены в словарь. Это не гарантировано.

Цитата из документа :

В целях перечисления каждый элемент в словаре рассматривается как KeyValuePair<TKey, TValue>структура, представляющая значение и его ключ. Порядок возврата товаров не определен.

Дарин Димитров
источник
1
Но есть OrderedDictionary .
Питер Мортенсен
28

Если вы хотите, чтобы элементы были упорядочены, используйте OrderedDictionary . Обычный hastable / словарь заказывается только в некотором смысле схемы хранения.

Митч Уит
источник
10
OrderedDictionary в большинстве случаев неверен. Он не упорядочен по ключу или значению, а по внутреннему индексу. SortedDictionary - это тот, который упорядочен таким образом, чтобы пользователь мог манипулировать (ключ по умолчанию)
Offler
3
Вопрос задает порядок в алфавитном порядке (при условии, что спрашивающий говорит о ключе). Упорядоченный словарь, если я правильно понимаю документацию, будет выдавать элементы в том порядке, в котором они вставлены, то есть не в алфавитном порядке, а с использованием внутреннего индекса. SortedDictionary, вероятно, лучше всего подходит для вопроса пользователя.
mattpm
28

Вы всегда можете использовать SortedDictionaryдля этого. Обратите внимание, что словарь по умолчанию упорядочен по ключу, если не указан компаратор.

Я скептически отношусь к использованию того, OrderedDictionaryчто вы хотите, поскольку в документации говорится, что:

Элементы OrderedDictionary не сортируются по ключу, в отличие от элементов класса SortedDictionary.

Адриано Карнейро
источник
Важно отметить, что SortedDictionary<K,V>оно реализовано в виде двоичного дерева поиска, что придает его операциям разную временную и пространственную сложность по сравнению с хеш-таблицей Dictionary<K,V>. Если пользователям нужна O(1)структура хэш-таблицы вставки / удаления, а также они хотят перебирать элементы в порядке ключей, тогда они должны dict.Keys.OrderBy( k => k ).Select( k => dict[k] )вместо этого (за счет O(n)пространства и O( n log n )времени) для OrderBy()(что потребуется для буферизации всей коллекции ключей во внутреннем списке ).
Дай
12

Элементы будут возвращены в том порядке, в котором они физически хранятся в словаре, который зависит от хэш-кода и порядка добавления элементов. Таким образом, порядок будет казаться случайным, и при изменении реализаций вы никогда не должны зависеть от порядка, оставшегося неизменным.

Вы можете упорядочить позиции при их перечислении:

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

В framework 2.0 вам сначала нужно будет поместить элементы в список, чтобы отсортировать их:

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) {
  ...
}
Гуффа
источник
11

Для упорядоченного словаря:

 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;
}

Элементы возвращаются в том порядке, в котором они были добавлены.

Бартон
источник
5

Ассоциативные массивы (также известные как хеш-таблицы) неупорядочены, что означает, что элементы можно упорядочивать любым возможным способом.

ОДНАКО, вы можете получить ключи массива (только ключи), упорядочить их в алфавитном порядке (с помощью функции сортировки), а затем работать над этим.

Я не могу дать вам образец C #, потому что я не знаю языка, но этого должно быть достаточно, чтобы вы могли продолжить.

Тим Час
источник