Возвращает ли перечислитель Dictionary <TKey, TValue> пары ключ-значение в том порядке, в котором они были добавлены?

Question

Я понимаю, что словарь не является упорядоченной коллекцией и не должен зависеть от порядка вставки и поиска в словаре.

Однако вот что я заметил:

• Добавлено 20 пар ключевых значений в словарь
• Получил их, выполнив foreach (KeyValuePair ...)

Порядок поиска был такой же, как порядок их добавления. Протестировано около 16 пар ключевых значений.

Это задумано?

Answer 1

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

Это довольно сложно воспроизвести, но мне удалось это сделать некоторое время назад для другого вопроса :

using System;
using System.Collections.Generic;

class Test
{
    static void Main(string[] args)
    {
        var dict = new Dictionary<int, int>();        
        dict.Add(0, 0);
        dict.Add(1, 1);
        dict.Add(2, 2);
        dict.Remove(0);
        dict.Add(10, 10);

        foreach (var entry in dict)
        {
            Console.WriteLine(entry.Key);
        }
    }
}

Результаты показывают 10, 1, 2, а не 1, 2, 10.

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

Answer 2

С MSDN :

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

[Акцент добавлен]

Answer 3

Если вы хотите перебирать словарь в фиксированном порядке, вы можете попробовать OrderedDictionary

Answer 4

Предполагается, что Dictionary<TKey,TValue> не является упорядоченной структурой, так как она предназначена в основном для доступа на основе ключей.

Если вам нужно получить предметы в определенном порядке, вы должны взглянуть на Sorted Dictionary<TKey, TValue>, который принимает Comparer<T>, который будет использоваться для сортировать ключи в Sorted Dictionary<TKey, TValue>.

Answer 5

Это по замыслу? Вероятно, этого не было в оригинальной .Net Framework 2.0, но теперь существует неявный контракт, что они будут упорядочены в том же порядке, что и добавленные, потому что изменение этого параметра приведет к поломке настолько большого количества кода, который зависит от поведения исходного универсального толковый словарь. Сравните с языком Go, где их карта преднамеренно возвращает случайный порядок, чтобы пользователи карт не полагались на любой порядок [1].

Любые улучшения или изменения, которые авторы структуры вносят в Словарь <T,V>, должны будут сохранять этот неявный контракт.

[1] «После выпуска Go 1.0 среда выполнения имеет рандомизированный порядок итераций карты.», https://blog.golang.org/go-maps-in-action.

Answer 6

Я полагаю, что перечисление Dictionary<K,V> вернет ключи в том же порядке, в котором они были вставлены , если все ключи хешируют с одинаковым значением . Это связано с тем, что реализация Dictionary<K,V> использует хеш-код объекта ключа для вставки пар ключ / значение в сегменты, а значения (как правило) хранятся в сегментах в порядке их вставки. Если вы постоянно наблюдаете это поведение с вашими пользовательскими объектами, то, возможно, вы не (правильно) переопределили метод GetHashCode()?

Answer 7

Я так не думаю, словарь не обеспечивает внутреннее упорядочение элементов внутри него. Если вам необходимо сохранить порядок, используйте дополнительную структуру данных (массив или список) вместе со словарем.