C# Set Operations

In this blog, I will cover 2 data structures, namely, HashSet and SortedSet and will create small examples to show how we can achieve mathematical set operations of Union, Intersect, Minus etc with these data structures.
HashSet<T>

• It uses a hashing algorithm to lookup items in a set and therefore is fast. Due to this, it takes up a bit of additional space.
• Dictionary<TKey,TValue> should be used if there is a key available. However, if no such key is available then using HashSet<T> is better. In that sense, HashSet<T> is kind of similar to Dictionary<T,T> that is, where the key and value are the same.
• In general sense, HashSet takes a constant amount of time to do Add, Remove or Contains operations, irrespective of how large or small the size might be. A List<T>, as the size increases, will take more time to perform these operations.
• It implements ISet<T>. ISet<T> is an interface that provides the methods to perform set operations such as UnionWith, IntersectWith, ExceptWith etc.
• HashSet also provides extension methods such as Union, Intersect, Except. The difference between these and methods with "With" is that methods with "With" modify the calling HashSet and return void. Methods without "With" return a separate IEnumerable<T>.

SortedSet<T>

• Is similar to HashSet<T> except that the items are kept in a sorted manner as and when they are added.
• Most of the points mentioned above are true for SortedSet as well.
• Similar to how Dictionary<TKey, TValue> has a SortedDictionary<TKey, TValue>.
• Performs a bit slower than HashSet<T> as it spends some time in sorting.

Set Operations

• Union: {1,2,3,4} union {3,4,5} = {1,2,3,4,5}
• Intersect: {1,2,3,4} intersect {3,4,5} = {3,4}
• Minus (Except): {1,2,3,4} minus {3,4,5} = {1,2}
• Superset: {1,2,3,4} is superset of {3,4}
• Subset: {3,4} is subset of {1,2,3,4}
• ProperSuperSet: 
• {1,2,3,4} is proper superset of {1,2,3,4} - FALSE
• {1,2,3,4} is superset of {1,2,3,4} - TRUE
• {1,2,3,4} is proper superset of {2,3} - TRUE
• {1,2,3,4} is superset of {2,3} - TRUE
• ProperSubSet:
• {1,2,3,4} is proper subset of {1,2,3,4} - FALSE
• {1,2,3,4} is subset of {1,2,3,4} - TRUE
• {2,3} is proper subset of {1,2,3,4} - TRUE
• {2,3} is subset of {1,2,3,4} - TRUE

Let's take a look at the code listing below:

public static class A08DataStructures
    {
        public static void Run()
        {
            HashSetExample();
            SortedSetExample();

            // Set operations
            IntersectExample();
            UnionExample();
            ExceptExample();
            SupersetSubsetExample();
        }

        private static void IntersectExample()
        {
            Console.WriteLine("\nIntersect Example");
            var hs1 = new HashSet<int>() { 1, 2, 3, 4 };
            var hs2 = new HashSet<int>() { 3, 4, 5 };
            hs1.IntersectWith(hs2);

            foreach (var i in hs1)
                Console.WriteLine(i.ToString());
        }

        private static void UnionExample()
        {
            Console.WriteLine("\nUnion Example");
            var hs1 = new HashSet<int>() { 1, 2, 3, 4 };
            var hs2 = new HashSet<int>() { 3, 4, 5 };
            hs1.UnionWith(hs2);

            foreach (var i in hs1)
                Console.WriteLine(i.ToString());
        }

        private static void ExceptExample()
        {
            Console.WriteLine("\nExcept Example");
            var hs1 = new HashSet<int>() { 1, 2, 3, 4 };
            var hs2 = new HashSet<int>() { 3, 4, 5 };
            hs1.ExceptWith(hs2);

            foreach (var i in hs1)
                Console.WriteLine(i.ToString());
        }

        private static void SupersetSubsetExample()
        {
            Console.WriteLine("\nSuperSet SubSet Example");
            var hs1 = new HashSet<int>() { 1, 2, 3, 4 };
            var hs2 = new HashSet<int>() { 2, 3 };

            Console.WriteLine("hs1 is PROPER SUPERSET of hs1: " + hs1.IsProperSupersetOf(hs1));
            Console.WriteLine("hs1 is SUPERSET of hs1: " + hs1.IsSupersetOf(hs1));
            Console.WriteLine("hs1 is PROPER SUPERSET of hs2: " + hs1.IsProperSupersetOf(hs2));
            Console.WriteLine("hs1 is SUPERSET of hs2: " + hs1.IsSupersetOf(hs2));

            Console.WriteLine("hs1 is PROPER SUBSET of hs1: " + hs1.IsProperSubsetOf(hs1));
            Console.WriteLine("hs1 is SUBSET of hs1: " + hs1.IsSubsetOf(hs1));
            Console.WriteLine("hs2 is PROPER SUBSET of hs1: " + hs2.IsProperSubsetOf(hs1));
            Console.WriteLine("hs2 is SUBSET of hs1: " + hs2.IsSubsetOf(hs1));
        }

        private static void SortedSetExample()
        {
            Console.WriteLine("\nSorted Set Example");
            var hs = new HashSet<string>();
            var ss = new SortedSet<string>();

            foreach (var sp in SportsPerson.LoadSportsPerson())
            {
                hs.Add(sp.Name);
                ss.Add(sp.Name);
            }

            Console.WriteLine("\nItems in Hash Set");
            foreach (var s in hs)
                Console.WriteLine(s);

            Console.WriteLine("\nItems in Sorted Set");
            foreach (var s in ss)
                Console.WriteLine(s);
        }

        private static void HashSetExample()
        {
            Console.WriteLine("HashSet Example");
            var hs = new HashSet<string>();
            var list = new List<string>();

            foreach (var sp in SportsPerson.LoadMillionSportsPerson())
            {
                hs.Add(sp.Name);
                list.Add(sp.Name);
            }

            Stopwatch watch = new Stopwatch();
            watch.Start();
            // find something in list
            var contains = list.Contains("Name999999");
            watch.Stop();
            Console.WriteLine("Time taken to search in a list: " + watch.ElapsedMilliseconds);

            watch.Restart();
            //find something in hashset
            contains = hs.Contains("Name999999");
            watch.Stop();
            Console.WriteLine("Time taken to search in a hash set: " + watch.ElapsedMilliseconds);
        }
    }

And here are the results -