Using collections as dictionary keys is sometimes necessary, but it can be a performance killer and unsafe. Here's how to make it faster and safer.
When doing functional style programming in C#, you'll probably eventually run into a situation where you need to key a dictionary by an ordered list of items. There are good ways and not so good ways to do this. This article aims to present you with an efficient and relatively safe way to use lists as dictionary keys.
Conceptualizing this Mess
Dictionary keys must be comparable for equality, must present a proper hash code, and must be immutable. These requirements make it a little bit involved to use lists as dictionary keys since lists don't typically provide value semantics - in this case, item by item comparison and a proper hash code. Perhaps worse, lists allow you to modify them at any time.
In summary, there are two major issues here, and one is comparing lists item by item isn't very efficient, and using a standard
IList<T> implementation as a dictionary key is fundamentally unsafe since again it can be modified at any time.
We can solve the latter more or less by requiring the use of
IReadOnlyList<T> which provides list-like access without the methods that modify the list. We're going to take a liberty here though when we declare our
KeyList<T> class - we'll be adding an
Add() method to it. The reason for this is to allow you to fill the list in the first place. If we wanted to be extra safe, we'd nix the
Add() method and force you to pass the items as an array into the constructor of the
KeyList<T>. The reason this was not done was for performance.
KeyList<T>'s primary purpose is performance, and passing in the data to the constructor would require a copy. Copies aren't horribly slow necessarily, but we don't need it here - we're okay here since anything that takes
IReadOnlyList<T> will not see our
Add() method anyway and this way, we avoid spurious copies.
The former requires a little more work. We have to implement value equality semantics on our
KeyList<T>. Here, we pull an important trick though: We recompute the hash code as each item is added to the list, that way we don't have to compute it later. We then use that hash code as part of our equality check to short circuit if they aren't equal. Let's take a look at the code for the
KeyList<T> class next.
Coding this Mess
sealed class KeyList<T> : IReadOnlyList<T>, IEquatable<KeyList<T>>
_items = new List<T>();
_hashCode = 0;
public KeyList(int capacity)
_items = new List<T>(capacity);
_hashCode = 0;
public T this[int index] => _items[index];
public int Count => _items.Count;
public IEnumerator<T> GetEnumerator()
public void Add(T item)
if (null != item)
_hashCode ^= item.GetHashCode();
public override int GetHashCode()
public bool Equals(KeyList<T> rhs)
if (ReferenceEquals(this, rhs))
if (ReferenceEquals(rhs, null))
if (rhs._hashCode != _hashCode)
var ic = _items.Count;
if (ic != rhs._items.Count)
for(var i = 0;i<ic;++i)
if (!Equals(_items[i], rhs._items[i]))
public override bool Equals(object obj)
return Equals(obj as KeyList<T>);
The important methods here are
Add() and the main
Equals() method. You can see in
Add() we're modifying the
_hashCode field for each item added. You can see in the
Equals() method we short circuit if the hash codes are not equal, before finally doing an item by item comparison. This can vastly improve performance. The other performance gain is in the
GetHashCode() method which doesn't have to compute anything. Since these methods are typically called by the
IDictionary<TKey,TValue> implementation, we want them to be as quick as possible, especially the
GetHashCode() method which is called a lot by
If you run the code in Release mode, you'll get accurate performance metrics. In Debug not so much, so the program will warn you if you're running in Debug. You can see we work the dictionaries, one filled with standard lists, the other filled with our special
KeyList<T> instances. You should see a 5x+ performance increase with the
KeyList<T> compared to using
List<T> and since it only implements
IReadOnlyList<T> for list access it's safer, too. Now both of our initial problems are solved. Enjoy.
It has been pointed out that this is not correct if the
T type is mutable. This is true. However, the same is true of
Dictionary<TKey, TValue> and
HashSet<T> so the same caveat applies there as here - do not change the values of items that are added to these lists, just like you should not change key values added to dictionaries and hashsets.
Using Other Containers
It is possible to adapt this technique to other collections if you need to. You can adapt it to a
HashSet<T> if you need (relatively) efficient unordered comparisons. I've done this in some of my projects. Just make sure to use
SetEquals() in your
Equals() method to do the item by item comparison, because it's faster.
- 24th February, 2020 - Initial submission
Just a shiny lil monster. Casts spells in C++. Mostly harmless.