Сохраняет ли HashSet порядок вставки?

Создает ли HashSet коллекцию, внедренную в .NET 3.5, порядок вставки при повторе с помощью foreach?

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

Ответ 1

Эта страница MSDN HashSet говорит:

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

Ответ 2

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

EDIT: здесь контрпример:

using System;
using System.Collections.Generic;

class Test
{
    static void Main()
    {
        var set = new HashSet<int>();

        set.Add(1);
        set.Add(2);
        set.Add(3);
        set.Remove(2);
        set.Add(4);


        foreach (int x in set)
        {
            Console.WriteLine(x);
        }
    }
}

Отпечатки 1, 4, 3, несмотря на то, что 3 были вставлены до 4.

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

Это не документировано, чтобы работать таким образом, и в документации явно указано, что он не отсортирован.
Я не смотрел на внутренние структуры или исходный код (чего у меня нет, очевидно) - я должен был тщательно изучить их, прежде чем принимать какие-либо такие претензии в твердой манере.
Реализация может очень легко измениться между версиями фреймворка. Опираясь на это было бы похоже на то, что реализация string.GetHashCode не меняется, что некоторые люди вернули в .NET 1.1 дней, а затем они сгорели, когда реализация изменилась в .NET 2.0...

Ответ 3

В документации указано:

Коллекция HashSet < (Of < (T > ) > ) не сортируется и не может содержать повторяющиеся элементы. Если дублирование заказов или элементов более важно, чем производительность для вашего приложения, рассмотрите возможность использования класса List < (Of < (T > ) > ) вместе с методом Сортировка.

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

Вы должны программировать против документированных контрактов, а не детали реализации.

Ответ 4

Нет, хэш-набор не сохранит порядок вставки, по крайней мере, не предсказуемо. Вы можете использовать LinkedHashSet (Java) или эквивалент. LinkedHashSet сохранит порядок.

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

EDIT: звучит так, как будто я проповедую: -/Извините.

Ответ 5

В .NET4 есть специально SortedSet<T>.

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

Ответ 6

Считывая исходный код HashSet.AddIfNotPresent, вы можете видеть, что порядок вставки сохраняется, если не было никаких исключений.

Таким образом, new HashSet<string> { "Tom", "Dick", "Harry" } сохраняет порядок, но если вы затем удалите Dick и добавьте Rick, порядок будет [ "Tom", "Rick", "Harry" ].