Почему записи добавляются в словаре .Net?

Я только видел это поведение, и я немного удивлен этим...

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

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

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

EDIT: Хорошо, я уже думал о многих причинах, почему это может произойти (например, отдельный список записей, независимо от того, является ли это совпадением и т.д.). Мой вопрос: кто-нибудь знает, как это работает?

Ответ 1

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

Цитата из MSDN:

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

Ответ 10

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

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

Ответ 11

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

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

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