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>
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:
And here are the results -