Почему записи в порядке добавления в словаре .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, потому что он использует пустые слоты.

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

Answer 2

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

Документация MSDN гласит:

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

Answer 3

Вы не можете рассчитывать на это поведение, но это не удивительно.

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

Цитата из MSDN :

Порядок ключей в Словарь <(Of <(TKey, TValue>)>). KeyCollection - это не указано, но это тот же порядок в качестве связанных значений в Словарь <(Of <(TKey, TValue>)>). ValueCollection возвращается словарем <(Of <(TKey, TValue>)>). Значения свойства.

Answer 8

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

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

Answer 9

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

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

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

Answer 10

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

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