HashSet в C#: критически важные вещи для понимания

Сегодня мы поговорим о такой вещи как HashSet в C# — расскажем о том, где она используется, для чего нужна и в чем ее особенности. И в качестве первой такой особенности сразу отметим, что структура данных HashSet (и вообще set) — это довольно редкая структура, которая присутствует не во всех стандартных библиотеках .NET, тем не менее она весьма полезна и практична. И вот почему.

1. Что такое HashSet в C#

Как можно догадаться по названию, HashSet — это коллекция в пространстве имен System.Collections.Generic. Это — неупорядоченная структура, то есть элементы этой коллекции могут быть неупорядоченными — например 2, 14, 4, 55, 53 и т.д. Другая особенность данной коллекции состоит в том, что она динамическая — то есть автоматически увеличивается при добавлении новых элементов.

И, наконец, самое главное свойство коллекции HashSet — в ней хранятся только уникальные элементы. Если в структуру данных попадает второй одинаковый элемент, он автоматически удаляется. Данная коллекция не может содержать одинаковых элементов.

2. Отличие HashSet от массива и словаря

HashSet, как и Dictionary, представляет собой коллекцию на основе хэшей, благодаря чему поиск выполняется очень быстро. Но в отличие от словаря, данная структура не хранит пары ключ/значение; она содержит только значения.

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

Коллекция HashSet не имеет строго заданного размера и может увеличиваться, причем размер ее ограничен лишь стеком. В HashSet невозможна сортировка структуры данных — порядок элементов в этой коллекции не определен. Овладеть полезными знаниями по этой теме, можно на курсах от наших друзей Hillel.

Еще одна важная особенность HashSet — в этой коллекции можно хранить элементы только одного типа.

3. Пример использования HashSet

Давайте посмотрим, как выглядит пример использования структуры HashSet:

using System.Collections.Generic;

namespace Learning_hashset
{
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<string> spisok = new HashSet<string>()
        {
            "Николай",
            "Дмитрий",
            "Highload_Today",
            "Валерий",
            "Сергей",
            "Highload_Today",
            "Сергей"
        };
            foreach (var item in spisok)
            {
                Console.WriteLine(item);
            }
        }
    }

}

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

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

using System.Collections.Generic;

namespace Learning_hashset
{
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<string> spisok = new HashSet<string>()
        {
            "Николай",
            "Дмитрий",
            "Highload_Today",
            "Валерий",
            "Сергей",
            "Highload_Today",
            "Сергей"
        };
            foreach (var item in spisok)
            {
                Console.WriteLine(item);
            }
        }
    }

}

4. Добавление элементов

Наша структура данных может использовать метод Add для добавления новых элементов. Например, если мы хотим добавить в структуру данных шестой элемент «Александр», мы используем следующий код:

using System;
using System.Collections.Generic;

namespace Learning_hashset
{
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<string> spisok = new HashSet<string>()
        {
            "Николай",
            "Дмитрий",
            "Highload_Today",
            "Валерий",
            "Сергей",
            "Highload_Today",
            "Сергей"
        };
            spisok.Add("Александр");
            foreach (var item in spisok)
            {
                Console.WriteLine(item);
            }
        }
    }

}

5. Удаление элементов

Для удаления элементов из коллекции используются методы Removeи RemoveWhere. Предположим, мы хотим удалить из структуры элемент «Дмитрий».

Для этого используем следующий метод:

spisok.Remove(“Дмитрий”);

Метод RemoveWhere применяется в тех случаях, когда необходимо определить условие для удаления. Предположим, мы хотим удалить из структуры элемент, который содержит 14 символов (Highload_Today).

В этом случае мы пишем:

using System;
using System.Collections.Generic;

namespace Learning_hashset
{
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<string> spisok = new HashSet<string>()
        {
            "Николай",
            "Дмитрий",
            "Highload_Today",
            "Валерий",
            "Сергей",
            "Highload_Today",
            "Сергей"
        };
            spisok.Add("Александр");
            spisok.RemoveWhere(x => x.Length == 14);
            foreach (var item in spisok)
            {
                Console.WriteLine(item);
            }
        }
    }

}

Для данной структуры можно также использовать свойство Count, которое покажет количество элементов (разумеется, без учета повторов):

Console.Writeline(spisok.Count);

Метод Clear() стирает нашу коллекцию, удаляя элементы.

6. Объединение и вычитание коллекций

Метод UnionWith() объединяет коллекции HashSet.

using System.Collections.Generic; 

namespace Learning_hashset
{
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<string> spisok = new HashSet<string>()
        {
            "Николай",
            "Дмитрий",
            "Highload_Today",
            "Валерий",
            "Сергей",

        };
            HashSet<string> spisok2 = new HashSet<string>()
            {
                "Валентина",
                "Виктория"
            };
            spisok.UnionWith(spisok2);
            


            foreach (var item in spisok)
            {
                Console.WriteLine(item);
            }
        }
    }

}

ExceptWith() — позволяет удалить из первой коллекции элементы второй.

7. Пересечение коллекций

Еще одна операция, которая известна из дискретной математики — пересечение множеств (в нашем случае — коллекций). Используя метод IntersectWith() можно получить коллекцию, состоящую из элементов, общих для наборов элементов HashSet:

using System;
using System.Collections.Generic;

namespace HS
{
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<string> names = new HashSet<string> {
                "Динамо",
                "Спартак",
                "Зенит"
            };
            HashSet<string> names1 = new HashSet<string> {
                "Торпедо",
                "Динамо",
                "Локомотив",
                "Спартак",
                "Шахтер"
            };
            names.IntersectWith(names1);
            foreach (var name in names)
            {
                Console.WriteLine(name);
            }
            Console.ReadKey();
        }
    }
}

Для списка "Динамо", "Спартак", "Зенит" и списка "Торпедо", "Динамо", "Локомотив", "Спартак", "Шахтер" общими элементами являются  "Динамо", "Спартак"

8. Коллекции с конструктором пользователей

Предположим, мы будем хранить в коллекции HashSet пользователей. Это может выглядеть следующим образом:

using System.Collections.Generic;
namespace Learning_hashset
{
   
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<User> spisok = new HashSet<User>();
            spisok.Add(new User { Name = "Alex" });
            spisok.Add(new User { Name = "John" });
            spisok.Add(new User { Name = "Jack" });
            spisok.Add(new User { Name = "Alex" });
            bool exists = spisok.Contains(new User { Name = "Alex" });
        }
             
    }
  
    class User
    {
        public string Name { get; set; }

    }

}

В данном примере мы видим, что первый и четвертый пользователь одинаковы. Однако наша коллекция об этом не знает и общее число элементов считает равным четырем. Кроме того, если делать проверку на наличие пользователя Alex, мы получим ответ, что такого пользователя нет.

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

Давайте научим программу сравнивать объекты HashSet с помощью классов. Поскольку User наследует базовый класс Object, он может прямо отсюда переопределять его основные методы. К таким методам относится Equals. Equalsпозволяет текущий объект сравнить с объектом obj и определить, будет ли он таким же или нет.

Вот как это выглядит в коде:

using System;
using System.Collections.Generic;

namespace Learning_hashset
{
   
    class Program
    {
        static void Main(string[] args)
        {
            HashSet<User> spisok = new HashSet<User>();
            spisok.Add(new User { Name = "Alex" });
            spisok.Add(new User { Name = "john" });
            spisok.Add(new User { Name = "Jack" });
            spisok.Add(new User { Name = "Alex" });
            bool exists = spisok.Contains(new User { Name = "Alex" });
        }
   
    
        
    }
  
    class User
    {
        public string Name { get; set; }
       
        public int Age { get; set; }
       
        public override bool Equals(object obj)
        {
            return this.Equals(obj as User);
        }
       
        public override int GetHashCode()
        {
            return HashCode.Combine(this.Name, this.Age);
        }
        private bool Equals(User that)
        {
            if (that == null)
            {
                return false;
            }
            return object.Equals(this.Name, that.Name) && this.Age == that.Age;
        }
    }

}

Итак, у нас есть две функции — GetHashCode и Equals. Они работают всегда в паре. Когда наша коллекция проверяет, есть ли среди существующих элементов элемент, который мы собираемся добавить, вначале запускается проверка по хеш-коду. То есть ищется такой элемент, с которым совпадает хеш-код добавляемого элемента.

Если такие элементы найдены, то это означает одно из двух — либо такие элементы действительно найдены, либо произошел случай коллизии. На тот случай, если у нас произошла коллизия, берется объект с которым совпали хеш-коды и вызывается метод Equals.

Если же по хеш-кодам не найдено совпадений, это точно означает, что такого элемента в коллекции еще нет и сравнивать через Equals не имеет никакого смысла. GetHashCode должен всегда возвращать одинаковые значения для одинаковых объектов, при этом одинаковые значения не всегда говорят о тождественности элементов — может произойти коллизия хеш-кодов.

Заключение

Теперь вы знаете про все особенности структуры HashSet (Hash-Set) и можете использовать их в своих проектах.

Работая с HashSet важно понимать, что он позволяет более оптимально реализовать операции над множествами-коллекциями (такими как пересечение, вычитание и объединение). При этом нужно помнить об их избыточности — они резервируют значительно больше памяти, чем нужно для хранения самих элементов, поэтому их имеет смысл использовать только для множеств средних размеров (оптимален диапазон 100-10000 элементов).

Для закрепления теоретических сведений рекомендуем вам посмотреть видео, в котором автор подробно описывает коллизии при работе с памятью HashSet. Но если у вас есть желание получить новые знания, то рекомендуем записаться на курсы от Mate Academy.