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

Question

Я прочитал это в ответ на многие вопросы здесь. Но что именно это означает?

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

Assert(test.ElementAt(2).Value == "two");

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

Answer 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. Это также не будет гарантировано.

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

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

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

Это поднимает превосходную точку.Это очень, очень дорого, чтобы изменить размер хеш-карты.Это означает, что вы должны выделить большую таблицу и заново вставить каждую пару ключ-значение.Так что стоит выделить в 10 раз больше памяти, чем нужно, чтобы не происходило даже одного увеличения.Знайте свой размер 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

Answer 4

Заказ недетерминирован.

С здесь

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

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

Answer 5

Словарь , а не SortedDictionary , по умолчанию для последовательности по порядку вставки.Как ни странно, вам нужно специально объявить SortedDictionary, чтобы иметь словарь, отсортированный по порядку строк ключей:

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

Answer 6

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

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

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

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

Answer 7

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