Когда я перебираю словарь (общая структура данных .NET), будет ли он в том же порядке, в котором я их добавил?
У меня есть словарь, к которому я обычно обращаюсь с помощью ключа, поэтому мне нужно быстрое чтение произвольного доступа. Однако для одной функции мне нужно обработать каждый элемент в словаре, где важен порядок. В тестах вроде нормально работает. Можно ли зависеть от порядка элементов в словаре?
Ответы 5
Нет. Вам лучше использовать SortedDictionary, если вы хотите хранить ключи в порядке.
Редактировать: Либо так, либо добавьте свои ключи в связанный список, если вы хотите отслеживать порядок добавления элементов.
Нет. Если вам нужно вести заказ, у вас также должен быть список товаров. Вы можете инкапсулировать все необходимые операции в свой собственный класс коллекции, который будет обновлять и словарь, и список одновременно.
К сожалению, .NET не имеет словаря, который сам поддерживает это - это довольно распространенный запрос - в Java есть, как LinkedHashMap.
tpower, Dictionary и SortedDictionary очень похожи тем, что оба содержат набор объектов, доступных по ключу. Они отличаются тем, как устроены изнутри.
Насколько мне известно, Dictionary быстрее вставляется, тогда как SortedDictionary построен на основе алгоритма поиска по двоичному дереву и быстрее читается.
Однако в обеих ситуациях внутренний порядок поддерживается ключевым порядком. Нет ничего, что могло бы гарантировать, что порядок, в котором вы перебираете всю коллекцию, будет таким же, как и при вставке элементов.
В этом случае вам может потребоваться сохранить как список, так и словарь для ваших различных требований.
Для словаря порядок просто не определен (и может меняться при изменении размера); он не зависит от ключа приказ, но явно зависит от значений ключа, их хэшей, количества сегментов и т. д.
Re перформанс; SortedDictionary - это помедленнее для чтения; O (log n) для SortedList <,> и SortedDictionary <,> и O (1) для Dictionary <,>. Из двух отсортированных SortedList <,> занимает меньше памяти и быстрее вставляет данные предварительно отсортированный (для несортированных данных SortedDictionary <,> вставляет быстрее).
В документации четко указано, что «В целях перечисления каждый элемент в словаре рассматривается как структура KeyValuePair <(Of <(TKey, TValue>)>), представляющая значение и его ключ. Порядок возврата товаров не определен.». но я не уверен.
Во всех проведенных мною тестах элементы всегда упорядочены по вставке.
Мне это показалось странным, потому что я также тестировал HashMap и LinkedHashMap (на Java) и порядок в HashMap не является правильным, как и ожидалось, но, как сказал Джон Скит, порядок в LinkedHashMap такой.
Может ли кто-нибудь указать на провал теста со словарем?
Вот код, который я использую для тестирования:
IDictionary<string, int> dic = new Dictionary<string, int>(10);
Console.WriteLine("Adding ...");
for (int i = 0; i < 1000000; i++)
{
Guid guid = Guid.NewGuid();
dic.Add(guid.ToString(), i);
}
Console.WriteLine("Testing ...");
bool first = true;
int lastItem = 0;
foreach (var item in dic.Values)
{
if (first)
{
first = false;
}
else
{
if (lastItem != item - 1)
{
Console.WriteLine("Test Failed !");
break;
}
}
lastItem = item;
}
Console.WriteLine("Done.");
Хмммм ... очень интересно! Даже если я принудительно удаляю много файлов и т. д., Он остается довольно стабильным. Тем не менее, если в документации написано «undefined», было бы неплохо игнорировать их ... даже если сегодня он стабилен, это не обязательно.
Вы определенно не можете полагаться на этот тест, чтобы доказать, что словарь останется отсортированным навсегда. Может случиться так, что другие изменения в памяти или даже время между вставками / удалениями могут повлиять на порядок, и единственный способ узнать наверняка - узнать, как словарь работает за кулисами, что непростая задача. .
Вы определенно не можете полагаться на то, что Dictionary <> возвращает результаты в том порядке, в котором вы их добавляли - как указано в документации.
При тестировании Dictionary <>, кажется, всегда перечисляет KeyValuePairs <> в том же порядке, в котором они были добавлены. Однако реализация Dictionary <> в Mono этого не делает. Mono следует документации при реализации поведения, и я предполагаю, что они увидели эту часть документации, а затем реализовали каким-то образом, который не поддерживал порядок.
Другой вариант - использовать OrderedDictionary, в котором воля поддерживает порядок.
использование отсортированного словаря не имеет прямой связи с перебором элементов в том порядке, в котором они были добавлены (см. тему)