В чем разница между HashSet <T>и List <T>? - PullRequest
145 голосов
/ 18 июня 2011

Можете ли вы объяснить, в чем разница между HashSet<T> и List<T> в .NET?

Может быть, вы можете объяснить на примере, в каких случаях HashSet<T> предпочтительнее, чем List<T>?

Спасибо.

Ответы [ 8 ]

192 голосов
/ 18 июня 2011

В отличие от списка <> ...

  1. HashSet - это список без повторяющихся элементов.

  2. Поскольку HashSet ограниченчтобы содержать только уникальные записи, внутренняя структура оптимизирована для поиска (по сравнению со списком) - это значительно быстрее

  3. Добавление в HashSet возвращает логическое значение - false, если добавление не удается из-зауже существует в наборе

  4. Может выполнять математические операции над множествами для набора: объединение / пересечение / IsSubsetOf и т. д.

  5. HashSet не реализует IListonly ICollection

  6. Вы не можете использовать индексы с HashSet, только перечислители.

Основной причиной использования HashSet будет, если вы заинтересованыв выполнении операций Set.

Дано 2 набора: hashSet1 и hashSet2

 //returns a list of distinct items in both sets
 HashSet set3 = set1.Union( set2 );

вылетает по сравнению с эквивалентной операцией с использованием LINQ.Так же аккуратно писать!

49 голосов
/ 18 июня 2011

A HashSet<T> - это класс, предназначенный для O(1) поиска содержимого (т.е. содержит ли эта коллекция конкретный объект и быстро ответит мне).

A List<T> - это класс, разработанный для предоставления вам коллекции с произвольным доступом O(1), которая может динамически расти (представьте динамический массив). Вы можете проверить содержание в O(n) времени (если список не отсортирован, тогда вы можете выполнить бинарный поиск в O(log n) времени).

Может быть, вы можете объяснить на примере, в каких случаях HashSet<T> предпочтительнее, чем List<T>

Если вы хотите проверить содержание в O(1).

47 голосов
/ 24 февраля 2014

Чтобы быть более точным, давайте продемонстрируем на примерах,

Вы не можете использовать HashSet, как в следующем примере.

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"};
for (int i = 0; i < hashSet1.Count; i++)
    Console.WriteLine(hashSet1[i]);

hashSet1[i] выдаст ошибку:

Невозможно применить индексирование с помощью [] к выражению типа 'System.Collections.Generic.HashSet'

Вы можете использовать оператор foreach:

foreach (var item in hashSet1)
    Console.WriteLine(item);

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

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"};
if (hashSet1.Add("1"))
   Console.WriteLine("'1' is successfully added to hashSet1!");
else
   Console.WriteLine("'1' could not be added to hashSet1, because it contains '1'");

HashSet имеет несколько полезных функций, таких как IntersectWith, UnionWith, IsProperSubsetOf, ExceptWith, SymmetricExceptWith и т. Д.

IsProperSubsetOf

HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "4" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" };
HashSet<string> hashSet3 = new HashSet<string>() { "1", "2", "3", "4", "5" };
if (hashSet1.IsProperSubsetOf(hashSet3))
    Console.WriteLine("hashSet3 contains all elements of hashSet1.");
if (!hashSet1.IsProperSubsetOf(hashSet2))
    Console.WriteLine("hashSet2 does not contains all elements of hashSet1.");

UnionWith

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" };
hashSet1.UnionWith(hashSet2); //hashSet1 -> 3, 2, 4, 6, 8

IntersectWith

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" }
hashSet1.IntersectWith(hashSet2);//hashSet1 -> 4, 8

ExceptWith:

 HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" };
 HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" };
 hashSet1.ExceptWith(hashSet2);//hashSet1 -> 5, 6

SymmetricExceptWith:

 HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" };
 HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" };
 hashSet1.SymmetricExceptWith(hashSet2);//hashSet1 -> 4, 5, 6

Кстати, в HashSets порядок не сохраняется. В этом примере мы добавили элемент «2» последним, но он во втором порядке:

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" };
hashSet1.Add("1");    // 3, 4, 8, 1
hashSet1.Remove("4"); // 3, 8, 1
hashSet1.Add("2");    // 3, 2 ,8, 1
18 голосов
/ 18 июня 2011

Используйте List<T>, если хотите:

  • Хранить коллекцию предметов в определенном порядке.

Если вы знаете индекс предмета, который выхочу (а не значение самого элемента) извлечения O(1).Если вы не знаете индекс, поиск элемента занимает больше времени, O(n) для несортированной коллекции.

Используйте Hashset<T>, если хотите:

  • Быстровыясните, содержится ли определенный объект в коллекции.

Если вы знаете название объекта, который хотите найти, Lookup - это O(1) (это часть 'Hash').Он не поддерживает порядок, как List<T>, и вы не можете хранить дубликаты (добавление дубликатов не имеет никакого эффекта, это часть 'Set').

Пример использования Hashset<T> было бы, если вы хотите узнать, является ли слово, играемое в игре Scrabble, допустимым словом на английском (или другом языке).Еще лучше было бы, если бы вы хотели создать веб-сервис, который будет использоваться всеми экземплярами онлайн-версии такой игры.

A List<T> будет хорошей структурой данных для создания табло для отслеживания игрока.баллы.

13 голосов
/ 18 июня 2011

Список - это упорядоченный список.Это

  • , доступ к которому осуществляется целочисленным индексом
  • может содержать дубликаты
  • имеет предсказуемый порядок

HashSet - это набор.Это:

  • Может блокировать повторяющиеся элементы (см. Добавить (T) )
  • Не гарантирует порядок элементов в наборе
  • Имеет операции, которые вы ожидаете с набором, , например , IntersectWith, IsProperSubsetOf, UnionWith.

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

3 голосов
/ 18 июня 2011

Список - это упорядоченная коллекция объектов типа T, которые в отличие от массива можно добавлять и удалять записи.

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

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

Вы бы использовали HashSet, где вы хотите проверить, находится ли объект в коллекции

3 голосов
/ 18 июня 2011

Список не обязательно уникален, в то время как hashset для одного.

1 голос
/ 09 сентября 2014

Если вы решите применить эти структуры данных для фактического использования в разработке, управляемой данными, HashSet ОЧЕНЬ полезен при тестировании репликации на источники адаптера данных, для очистки и переноса данных.

Кроме того, при использованииКласс DataAnnotations: можно реализовать логику Key для свойств класса и эффективно управлять естественным индексом (кластеризованным или нет) с помощью HashSet, где это будет очень сложно в реализации List.

Сильный вариант для использования списказаключается в реализации обобщений для нескольких сред в модели представления, таких как отправка списка классов в представление MVC для помощника DropDownList, а также для отправки в виде конструкции JSON через WebApi.Этот список допускает типичную логику сбора классов и сохраняет гибкость для более «интерфейсного» подхода к вычислению модели одного представления для разных сред.

...