Одинаков ли порядок словаря, если он имеет одинаковое содержание?

Question

Я знаю, что порядок словаря не определен, MSDN говорит так:

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

Это хорошо, но если у меня есть два экземпляра словаря, каждый с одинаковым содержанием, будет ли порядок одинаковым?

Я так думаю, потому что, как я понимаю, порядок определяется хешем ключей, и если два словаря имеют одинаковые ключи, они имеют одинаковые хеши и, следовательно, одинаковый порядок ...

... Верно?

Спасибо!

Энди.

Answer 1

Нет, это не гарантирует, что будет тот же заказ. Представьте себе сценарий, в котором у вас было несколько элементов в Dictionary<TKey, TValue> с одинаковым хеш-кодом. Если они будут добавлены в два словаря в разных порядках, это приведет к разным порядкам при перечислении.

Рассмотрим, например, следующий (соответствующий равенству) код

class Example
{
    public char Value;
    public override int GetHashCode()
    {
        return 1;
    }
    public override bool Equals(object obj)
    {
        return obj is Example && ((Example)obj).Value == Value;
    }
    public override string ToString()
    {
        return Value.ToString();
    }
}

class Program
{
    static void Main(string[] args)
    {
        var e1 = new Example() { Value = 'a' };
        var e2 = new Example() { Value = 'b' };
        var map1 = new Dictionary<Example, string>();
        map1.Add(e1, "1");
        map1.Add(e2, "2");

        var map2 = new Dictionary<Example, string>();
        map2.Add(e2, "2");
        map2.Add(e1, "1");

        Console.WriteLine(map1.Values.Aggregate((x, y) => x + y));
        Console.WriteLine(map2.Values.Aggregate((x, y) => x + y));
    }
}

Результат запуска этой программы:

12
21

Answer 2

Короткая версия: №

Длинная версия:

    [TestMethod]
    public void TestDictionary()
    {
        Dictionary<String, Int32> d1 = new Dictionary<string, int>();
        Dictionary<String, Int32> d2 = new Dictionary<string, int>();

        d1.Add("555", 1);
        d1.Add("abc2", 2);
        d1.Add("abc3", 3);
        d1.Remove("abc2");
        d1.Add("abc2", 2);
        d1.Add("556", 1);

        d2.Add("555", 1);
        d2.Add("556", 1);
        d2.Add("abc2", 2);
        d2.Add("abc3", 3);

        foreach (var i in d1)
        {
            Console.WriteLine(i);
        }
        Console.WriteLine();
        foreach (var i in d2)
        {
            Console.WriteLine(i);
        }
    }

Выход:

[555, 1]
[abc2, 2]
[abc3, 3]
[556, 1]

[555, 1]
[556, 1]
[abc2, 2]
[abc3, 3]

Answer 3

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

Answer 4

Если спецификация говорит, что заказ "неопределен", вы не можете зависеть от заказа без явного заказа. Базовая реализация может быть изменена в любое время с помощью новой версии или пакета обновления, только для начинающих. Ваш словарь может быть отклонен от любого количества конкретных реализаций.

А базовая реализация может зависеть от порядка применяемых операций. Добавление ключей «a», «b» и «c» в таком порядке может привести к иной структуре данных, чем добавление одного и того же набора ключей в другом порядке (скажем, «b», «c» и «a»). ). Удаление также может повлиять на структуру данных.

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

И некоторые структуры данных изменяются по мере выполнения операций. Если, например, словарь реализован с базовой структурой данных, представляющей собой красное / черное дерево, узлы дерева будут разделены / повернуты, чтобы сохранить баланс дерева при вставках и удалениях. Таким образом, фактическая структура данных в значительной степени зависит от порядка операций, даже если конечное содержимое одинаково.

Answer 5

"если два словаря имеют одинаковые ключи, они имеют одинаковые хеши и, следовательно, одинаковый порядок ..."

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

Реализация словаря Microsoft немного сложна, но из рассмотрениякод в течение 5 минут, я готов угадать, что последовательность перечисления будет основана на как словарь попал в его текущее состояние, включая количество изменений размера и порядок вставки.

Answer 6

Я не знаю специфики реализации Microsoft, но в целом ваше предположение верно только в том случае, если в словаре нет двух элементов, хэширующих одно и то же значение, или если эти записи, которые сталкиваются, добавляются в том же порядке.