14

Стал замечать, что приходится менять тип коллекции с List<T> на HashSet<T> для улучшения производительности. Ну и собственно теперь кажется, что лучше я сразу буду делать HashSet-ы, везде где раньше привык делать List-ы. Или всё-таки есть ситуации, когда List предпочтительнее?

1
  • 7
    HashSet не гарантирует порядок обхода, не имеет доступа по индексу, не может содержать одинаковые элементы.
    – Lyth
    19 дек 2017 в 12:41

3 ответа 3

17

List<T> - упорядоченная коллекция, которая может содержать дубликаты.

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

Не всегда нужно и возможно использовать HashSet. Хотя в случаях когда его получится использовать, будет весомый прирост производительности на больших коллекциях, так как некоторые операции выполняются быстрее (например Contains, Remove, Add выполняются за O(1)).

6
  • Может все-таки выполняются за O(n * log n)? 19 дек 2017 в 12:47
  • А разве List<T>.Add() и List<T>.RemoveAt() выполняются дольше? Весь вопрос в том, нужно ли нам искать элемент в списке? Если да и часто, то HashSet<T> если нет или иногда, то List<T> 19 дек 2017 в 12:49
  • @VictorKhovanskiy какая операция выполняется за O(n log n)?
    – Zergatul
    19 дек 2017 в 13:07
  • @VictorKhovanskiy Add за O(1) / O(n) (в зависимости от того, нужен ресайз или нет), Contains и Remove за O(1). Но только если хэши элементов уникальны :)
    – user177221
    19 дек 2017 в 13:08
  • @AntonShchyrov RemoveAt() - O(n), Add() - O(1). Но, есть еще Insert(), который выполняется на O(n)
    – Zergatul
    19 дек 2017 в 13:08
12

Все зависит от конкретной ситуации. Если заглянуть на MSDN, то там написано следующее:

The HashSet<T> class provides high-performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.

Класс HashSet<T> предоставляет высокопроизводительные операции над множеством(набором). Множество(набор) - это коллекция элементов, которые не дублируются и не упорядочены.

...

HashSet<T> implements the IReadOnlyCollection<T> interface starting with the .NET Framework 4.6; in previous versions of the .NET Framework, the HashSet<T> class did not implement this interface.

Начиная с версии .NET Framework 4.6, класс HashSet<T> реализует интерфейс IReadOnlyCollection<T>. В предыдущих версиях .NET Framework-а, этот класс не реализовывал этот интерфейс.

...

A HashSet<T> collection is not sorted and cannot contain duplicate elements. If order or element duplication is more important than performance for your application, consider using the List class together with the Sort method.

Коллекция HashSet<T> является неупорядоченной и не может содержать дубликаты. В случаях, когда наличие дубликатов или порядок элементов является более важным в вашем приложении, чем производительность, то рассмотрите возможность использования класса List<T> вместе с методом Sort.

0
0

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

2
  • Почему это так?
    – 4per
    1 фев 2023 в 17:54
  • Из-за того, что вычисление хэш-функции занимает некоторое время. Но, насколько я знаю, для всех встроенных типов реализация GetHashCode довольно дешевая, поэтому это актуально только для совсем уж маленьких коллекций.
    – user540538
    2 фев 2023 в 10:38

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.