Почему записи в словаре .Net упорядочены?

Question

Я только что увидел такое поведение и немного удивлён...

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

Причина, по которой это меня удивляет, заключается в том, что словарь внутри должен быть HashTable, поэтому я ожидал, что все будет выводиться в ЛЮБОМ порядке (по хешу ключа, верно?)

Что мне здесь не хватает?Могу ли я рассчитывать на такое поведение?

РЕДАКТИРОВАТЬ:Хорошо, я уже подумал о многих причинах, почему это мощь произойти (например, отдельный список записей, совпадение ли это и т. д.).Мой вопрос в том, кто-нибудь знать как это на самом деле работает?

Answer 1

Если вы используете .NET Reflector в библиотеках классов 3.5, вы можете увидеть, что реализация Dictionary фактически сохраняет элементы в массиве (размер которого изменяется по мере необходимости) и хэширует индексы в этот массив.При получении ключей он полностью игнорирует хеш-таблицу и перебирает массив элементов.По этой причине вы увидите описанное вами поведение, поскольку новые элементы добавляются в конец массива.Это выглядит так, если вы сделаете следующее:

add 1
add 2
add 3
add 4
remove 2
add 5

вы получите обратно 1 5 3 4, потому что он повторно использует пустые слоты.

Важно отметить, что, как и многие другие, вы не можете рассчитывать на такое поведение в будущих (или прошлых) выпусках.Если вы хотите, чтобы ваш словарь был отсортирован, есть Сортированный словарь класс для этой цели.

Answer 2

Словарь извлекает элементы в хешированном порядке.Тот факт, что они появились в порядке вставки, был полным совпадением.

В документации MSDN говорится:

Порядок ключей в KeyCollection не указан, но он совпадает с порядком связанных значений в ValueCollection, возвращаемых свойством Values.

Answer 3

На такое поведение рассчитывать нельзя, но это неудивительно.

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

Поэтому хорошей оптимизацией может быть сохранение отдельного повторяющегося списка ключей.Используя двусвязный список, вы по-прежнему получаете вставку/удаление в постоянное время.(Вы сохраните указатель из сегмента хеш-таблицы обратно на этот список.) Таким образом, итерация по списку ключей зависит только от количества записей, а не от количества сегментов.

Answer 4

Я думаю, это происходит из старых версий .NET 1.1, когда у вас было два типа словарей: «ListDictionary» и «HybridDictionary». СписокСловарь представлял собой словарь, реализованный внутри в виде упорядоченного списка и рекомендованный для «небольших наборов статей».Тогда у тебя был Гибридный словарь, который изначально был организован внутри в виде списка, но если бы он стал больше настраиваемого порога, он превратился бы в хеш-таблицу.Это было сделано потому, что исторически правильные словари на основе хешей считались дорогими.Сегодня это не имеет особого смысла, но я полагаю, что .NET просто основал свой новый универсальный класс Dictionary на основе старого HybridDictionary.

Примечание:В любом случае, как уже заметил кто-то другой, вам следует никогда рассчитывать на порядок словаря для чего угодно

Answer 5

Цитата из MSDN :

Порядок ключей в словаре <(of <(tkey, tvalue>)>). Ключевое объединение не определено, но это тот же порядок, что и соответствующие значения в словаре <(of <(tkey, tvalue>)>) .ValueCollection возвращается словарем <(of <(tkey, tvalue>)>). Значит свойство.

Answer 6

Какие ключи вы добавляли в своем тесте и в каком порядке?

Answer 7

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

Answer 8

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

Answer 9

До определенного размера списка дешевле просто проверять каждую запись вместо хеширования.Вероятно, именно это и происходит.

Добавьте 100 или 1000 элементов и посмотрите, находятся ли они в том же порядке.

Answer 10

Я ненавижу подобные «задуманные» функции.Я думаю, что если дать вашему классу такое общее имя, как «Словарь», он также должен вести себя «как обычно».Например, std::map всегда сохраняет сортировку значений ключа.

Редактировать:очевидно, решение состоит в том, чтобы использовать SortedDictionary, который ведет себя аналогично std::map.

Answer 11

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

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

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