Почему словарь "не упорядочен"?

Ответ 1

Ну, с одной стороны, неясно, ожидаете ли вы, что это будет порядок вставки или порядок клавиш. Например, что бы вы ожидали результата, если бы вы написали:

var test = new Dictionary<int, string>();
test.Add(3, "three");
test.Add(2, "two");
test.Add(1, "one");
test.Add(0, "zero");

Console.WriteLine(test.ElementAt(0).Value);

Ожидаете ли вы "три" или "нуль"?

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

Исключения также влияют на это. Например, что бы вы ожидали от результата этой программы?

using System;
using System.Collections.Generic;

class Test
{ 
    static void Main() 
    {
        var test = new Dictionary<int, string>();
        test.Add(3, "three");
        test.Add(2, "two");
        test.Add(1, "one");
        test.Add(0, "zero");

        test.Remove(2);
        test.Add(5, "five");

        foreach (var pair in test)
        {
            Console.WriteLine(pair.Key);
        }
    }     
}

На самом деле (на моем ящике) 3, 5, 1, 0. В новой записи для 5 используется освобожденная запись, ранее использовавшаяся в 2. Это не будет гарантировано, хотя.

Повторная обработка (когда словарь, лежащий в основе хранилища, должен быть расширен) может повлиять на вещи... всевозможные вещи.

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

Ответ 2

A Dictionary<TKey, TValue> представляет Hash Table, а в хэш-таблице нет понятия порядка.

Документация объясняет это довольно хорошо:

Для целей перечисления каждый элемент в словаре рассматривается как Структура KeyValuePair представляя значение и его ключ. порядок возврата предметов undefined.

Ответ 3

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

Во-первых, у Словаря нет гарантированного заказа, поэтому вы используете его только для быстрого поиска ключа и поиска соответствующего значения, или вы перечисляете все пары ключ-значение, не заботясь о том, что такое заказ.

Если вы хотите заказать, вы используете OrderedDictionary, но компромисс заключается в том, что поиск выполняется медленнее, поэтому, если вам не нужен заказ, не просите его.

Словари (и HashMap на Java) используют хеширование. Это O (1) раз, независимо от размера вашей таблицы. В упорядоченных словарях обычно используется какое-то сбалансированное дерево, которое является O (log2 (n)), так как ваши данные растут, доступ становится медленнее. Чтобы сравнить, для 1 миллиона элементов, что порядка 2 ^ 20, так что вам нужно будет сделать порядка 20 поисков для дерева, но 1 для хэш-карты. Это намного быстрее.

Хеширование является детерминированным. Недетерминизм означает, что когда вы хэш (5) в первый раз, а вы хеш (5) в следующий раз, вы получите другое место. Это было бы совершенно бесполезно.

То, что люди хотели сказать, заключается в том, что если вы добавляете вещи в словарь, порядок сложный и может быть изменен в любое время, когда вы добавляете (или потенциально удаляете) элемент. Например, представьте, что хеш-таблица содержит в себе 500 тыс. Элементов, и у вас есть значения 400 тыс. Когда вы добавляете еще один, вы достигаете критического порога, потому что для его эффективности требуется около 20% свободного пространства, поэтому он выделяет большую таблицу (скажем, 1 миллион записей) и повторно хеширует все значения. Теперь они все в разных местах, чем раньше.

Если вы построите тот же словарь дважды (внимательно прочитайте мое выражение, ТО ЖЕ), вы получите тот же порядок. Но, как правильно говорит Джон, не рассчитывайте на это. Слишком много вещей может сделать это не одно и то же, даже изначально выделенного размера.

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

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

Когда вы говорите:

new Foo();

вы создаете новый объект в новом месте в памяти.

Если вы используете значение Foo как ключ в словаре, без какой-либо другой информации, единственное, что они могут сделать, это использовать адрес объекта в качестве ключа.

Это означает, что

var f1 = new Foo(1);
var f2 = new Foo(1);

f1 и f2 не являются одним и тем же объектом, даже если они имеют одинаковые значения.

Итак, если вы должны помещать их в словари:

var test = new Dictionary<Foo, string>();
test.Add(f1, "zero");

не ожидайте, что он будет таким же, как:

var test = new Dictionary<Foo, string>();
test.Add(f2, "zero");

даже если оба f1 и f2 имеют одинаковые значения. Это не имеет ничего общего с детерминированным поведением Словаря.

Хэширование - удивительная тема в информатике, мой любимый преподавать в структурах данных.

Отъезд Кормен и Лейсерсон для книги высокого уровня о красно-черных деревьях против хеширования Этот парень по имени Боб имеет отличный сайт о хэшировании и оптимальных хэшах: http://burtleburtle.net/bob

Ответ 4

Порядок не детерминирован.

Из здесь

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

Возможно, для ваших нужд OrderedDictionary является обязательным.

Ответ 5

Я не знаю С# или какой-либо из .NET, но общая концепция словаря заключается в том, что он представляет собой набор пар ключ-значение.
Вы не получаете доступ к последовательному словарю так же, как если бы, например, итерации списка или массива.
Вы получаете доступ с помощью ключа, а затем находите, есть ли значение для этого ключа в словаре и что это такое.
В вашем примере вы разместили словарь с числовыми ключами, которые являются последовательными, без пробелов и в порядке возрастания вставки.
Но независимо от того, в каком порядке вы вставляете значение для ключа "2", вы всегда будете получать одинаковое значение при запросе на ключ "2".
Я не знаю, разрешает ли С#, я думаю, да, иметь ключи, отличные от чисел, но в этом случае то же самое, нет явного порядка на клавишах.
Аналогия с реальным словарем может быть запутанной, поскольку ключи, которые являются словами, упорядочены по алфавиту, поэтому мы можем найти их быстрее, но если бы они не были, словарь работал бы так или иначе, потому что определение слова "Aardvark" имел бы то же значение, даже если бы это произошло после "Зебры". Подумайте о романе, с другой стороны, изменение порядка страниц не имеет никакого смысла, поскольку они являются упорядоченной коллекцией по существу.

Ответ 6

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

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

В качестве альтернативы было бы полезно иметь AddOnlyDictionary, который был бы потокобезопасным для одного писателя одновременно с любым количеством читателей и гарантировал бы сохранение элементов в последовательности (обратите внимание, что если элементы только добавлены - никогда не удаляются или не изменяются иным образом - можно сделать "снимок", просто отметив количество элементов, которые он содержит в настоящее время). Создание универсального словарного нитебезопасного дорогостоящее, но добавление выше уровня безопасности потоков будет дешевым. Обратите внимание, что эффективное использование многозадачного многопользовательского устройства не потребует использования блокировки чтения-записи, но может быть просто обработано путем блокировки писателей и отсутствия чтения читателей.

Microsoft не реализовала AddOnlyDictionary, как описано выше, конечно, но интересно отметить, что в потокобезопасном ConditionalWeakTable есть семантика только для добавления, вероятно, потому что, как отмечено, это намного проще добавьте concurrency в коллекции только для добавления, а не в коллекции, которые разрешают удаление.

Ответ 7

Словарь < string, Obj > , not SortedDictionary < string, Obj > , по умолчанию - по порядку вставки. Достаточно странно вам нужно специально объявить SortedDictionary, чтобы иметь словарь, отсортированный по строкам строки:

public SortedDictionary<string, Row> forecastMTX = new SortedDictionary<string, Row>();