Home > Articles > Programming > Windows Programming

.NET Reference Guide

Hosted by

Toggle Open Guide Table of ContentsGuide Contents

Close Table of ContentsGuide Contents

Close Table of Contents

Set Operations with IEnumerable and HashSet

Last updated Mar 14, 2003.

The HashSet collection, according to the .NET documentation, "represents a set of values." That sounds like a pretty vague description until you realize that "set" implies that it's a representation of a mathematical set. That implies a considerable amount of functionality. HashSet can make short work of many tasks that, without it, are difficult or tedious to write using other means.

In addition to the HashSet collection type, the generic IEnumerable<T> interface includes set operations. Both groups of set operations make a number of things much easier.

Set Union

The union of two sets results in a set that contains all elements of both sets, although no item is duplicated. That is, if two sets each contain an item with the key "Jim", the resulting set will have only one item with that key.

The IEnumerable interface has a Union method that produces a new collection that contains all the elements of both sets.

The HashSet UnionWith method modifies the collection so that it contains the items from both sets.

A union operation is useful when you want to combine lists and remove duplicates. Suppose, for example, you are running an election and you want to combine lists of voters from multiple precincts:

var AllWhoVoted = Precinct1Voters.Union(Precinct2Voters);

HashSet has its own UnionWith method that modifies the collection. That is, assuming that your collections are both HashSets, then:

AllWhoVoted.UnionWith(Precinct1Voters);

Will add the voters from precinct 1 to the list of all voters.

For me, HashSet is more convenient in this circumstance because I'm building a list that I want modified. Imagine you're combining results from many precincts. With the IEnumerable implementation, you end up building a new list every time:

var AllWhoVoted = Precinct1Voters.Union(Precinct2Voters);
AllWhoVoted = AllWhoVoted.Union(Precinct3Voters);
AllWhoVoted = AllWhoVoted.Union(Precinct4Voters);
// etc.

HashSet, on the other hand, just adds items:

HashSet AllWhoVoted = new HashSet(Precinct1Voters);
AllWhoVoted.UnionWith(Precinct2Voters);
AllWhoVoted.UnionWith(Precinct3Voters);
AllWhoVoted.UnionWith(Precinct4Voters);

The results are the same (they better be!), and they might even be arrived at the same way under the hood. But the code that uses HashSet seems more clear to me.

Set Intersection

Set intersection produces the set of items that exist in both sets. That is, if set A contains {Jim, David, Ron, Joe}, and set B contains {Jim, David, George}, then A.Intersect(B) would return {Jim, David}.

The IEnumerable interface has an Intersect method that will generate the intersection of any two collections that implement IEnumerable.

HashSet has its own IntersectWith method, which operates slightly differently than IEnumerable.Intersect. IEnumerable.Intersect creates a new collection that contains the intersection of the two collections that you passed to it. For example, assuming you have two Lists, list1 and list2:

var listIntersection = list1.Intersect(list2);

HashSet.IntersectWith, on the other hand, modifies the original collection. So if you have two HashSets called hash1 and hash2, then after executing this line of code:

hash1.IntersectWith(hash2);

hash1 contains only those items that existed in both collections.

So what good is Intersect or IntersectWith? Any time you want to see how many items in one list also exist in another, you are doing an intersection. For example, you might have a list of eligible voters and a separate list of people who voted. Assuming you have two collections that implement the generic IEnumerable interface, you could write:

var EligibleVotersWhoVoted = EligibleVoters.Intersect(PeopleWhoVoted);

One would hope that the following would produce the empty set:

var VotedTwice = Precinct1Voters.Intersect(Precinct2Voters);

Of course, if you have multiple precincts and you want to make sure no voter cast a ballot twice, things get a bit more complicated:

HashSet<Voter> VotedTwice = new HashSet<Voter>();
var AllWhoVoted = Precinct1Voters;
VotedTwice.UnionWith(AllWhoVoted.Intersect (Precinct2Voters));
AllWhoVoted = AllWhoVoted.Union(Precinct2Voters);
// etc

Set Difference

Another common operation is to determine which items from one set are not in another. In .NET, the methods that perform this operation are called "Except": IEnumerable<T>.Except and HashSet.ExceptWith.

Unlike union and intersection, with this operation you have to be careful about the order. That is, given two collections, A and B:

A.Union(B) is the same as B.Union(A)

A.Intersect(B) is the same as B.Intersect(A)

A.Except(B) is not the same as B.Except(A)

If A contains the values {Jim, Joe, Ron, David}, and B contains the values {Jim, Sam, George}, then:

A.Except(B) will return {Joe, Ron, David}

B.Except(A) will return {Sam, George}

In the voting analogy, set difference can be pretty interesting. How about a list of eligible voters who did not vote?

var DidNotVote = EligibleVoters.Except(PeopleWhoVoted);

Or, a better one:

var IneligibleVoters = PeopleWhoVoted.Except(EligibleVoters);

One would hope that the last would produce no results.

Perhaps it's just the kind of work that I do, but I find that I use set difference a lot. Very often, I'm trying to determine what things that were supposed to happen didn't actually take place. Typically, I'll have a log file of queued actions, a list of pending actions, and a log file of completed actions. A queued action that's not in the pending list of in the log of completed actions got lost somewhere. Either it wasn't performed or it didn't get logged.

In that case, the union of pending and logged should be equal to queued. Assuming we have three collections, Queued, Pending, and Logged, then the following will tell me which actions got lost:

var LostActions = Queued.Except(Pending.Union(Logged));

Subsets and Supersets

If you recall from your high school math, a set is a subset of another if all of its elements are also contained in the other set. That is, B is a subset of A if every element in B is also in A. B is a proper subset of A if B is a subset of A and it's not equal to A.

For example, say that the set A contains the elements {1,2,3}. The set B, containing {1,3} is a proper subset of A. The set C, containing {0,2,1} is not a subset, because the item '0' does not appear in set A. Set D, containing {1,2,3} is a subset of A, but not a proper subset of A.

Supersets are the inverse of subsets. If B is a subset of A, then A is a superset of B.

HashSet contains methods that determine if one set is a subset or superset of the other. The four methods are: IsProperSubsetOf, IsProperSuperSetOf, IsSubsetOf, and IsSupersetOf. The IEnumerable interface does not have corresponding methods.

These methods are handy when you want to know if the relationship exists, but you don't want to generate a new list. For example, imagine that ElibigleVoters and PeopleWhoVoted are both HashSet collections. You already saw that we could get a list of ineligible voters (i.e. people who voted but weren't supposed to) by writing:

var IneligibleVoters = PeopleWhoVoted.Except(EligibleVoters);

If the resulting collection has any elements, then you know that there's a problem.

But suppose we don't want the list, but just want to know if there are any ineligible voters. If there are no ineligible voters, then PeopleWhoVoted should be a subset of EligibleVoters:

bool votersOk = PeopleWhoVoted.IsSubsetOf(EligibleVoters);

Using the IEnumerable interface only, you could get the same result by writing:

bool votersOK = (PeopleWhoVoted.Except(EligibleVoters).Count() == 0);

SetEquals and SequenceEqual

HashSet.SetEquals determines if the HashSet and the specified collection are the same length and contain all the same elements. So, given these two collections:

var A = new HashSet<int>() {1, 2, 3, 4};
var B = new HashSet<int>() {4, 3, 2, 1};

A.SetEquals(B) returns true, as does B.SetEquals(A). Both collections contain the same items.

The IEnumerable interface has a method called SequenceEqual, which does much the same thing, except that the comparison is order dependent. Given the two collections above, neither A.SequenceEqual(B) nor B.SequenceEqual(A) will return true.

That leads to the rather curious result that A.SetEquals(B) == true and A.SequenceEqual(B) == false.

It looks to me like, if you want to determine if two IEnumerable collections have the same items, you first have to sort the items before calling SequenceEqual.

Or, you can use union or intersection to determine if the sets are equal. If two sequences are the same length, and the union or the intersection of the two sequences also has the same length, then the sets are equal. That is:

bool SetsAreEqual = (A.Count() == B.Count() && A.Intersect(B).Count() == A.Count())

You could replace Intersect with Union in the above code and achieve the same result.

Save To Your Account