Using Collections as Keys in C#

Updated on 2020-02-09

Using IEqualityComparer to allow collections to be keys in dictionaries and hashsets

C#.NETcollections

Introduction

Sometimes when expressing complicated algorithms in C# you may find yourself needing to look up some information based on a set of items rather than a single item. Stock .NET provides a little bit of functionality for doing this via LINQ but it's not generalized such that Dictionary<TKey,TValue> for example can use it.

This little library aims to provide two styles of comparison so that these types of operations are easy.

Using this Mess

A Cautionary Note

Keys should not be mutable, but because of how collections work these ones are mutable when they shouldn't be. Do not modify collections you are using as keys! It will cause you nasty bugs.

This library exposes two classes, OrderedCollectionEqualityComparer and UnorderedCollectionEqualityComparer, which provides ordered and unordered comparisons respectively. They work on anything implementing IList, ICollection, or ISet. Unordered comparisons can be expensive, but using HashSet for your collections can speed that up some. You can use these classes to provide Dictionary<TKey, TValue> and HashSet<TKey, TValue> with a way to compare collections instead of single items. The demo code indicates how to use them:

// create a new hashset that uses ordered collection comparisons
var set = new HashSet<int[]>(OrderedCollectionEqualityComparer<int>.Default);
// add a collection:
set.Add(new int[] { 1, 2, 3, 4, 5 });

// true:
Console.WriteLine("Ordered cmp - contains 1-5: " + set.Contains(new int[] { 1, 2, 3, 4, 5 }));
// false:
Console.WriteLine("Ordered cmp contains 5-1: " + set.Contains(new int[] { 5, 4, 3, 2, 1 }));

// create a new hashset that uses unordered collection comparisons
set = new HashSet<int[]>(UnorderedCollectionEqualityComparer<int>.Default);
set.Add(new int[] { 1, 2, 3, 4, 5 });

// true:
Console.WriteLine("Unordered cmp - contains 1-5: " + set.Contains(new int[] { 1, 2, 3, 4, 5 }));
// true:
Console.WriteLine("Unordered cmp contains 5-1: " + set.Contains(new int[] { 5, 4, 3, 2, 1 }));

History

  • 9th February, 2020 - Initial submission