Alternate Lookup For Dictionary And HashSet With The IAlternateEqualityComparer

Introduction

Starting with .NET 9, we now have a new interface for comparisons, IAlternateEqualityComparer<TAlternate, T>, as well as a new method in hash-based types called GetAlternateLookup. These, together with the new struct AlternateLookup<TAlternateKey>, enable us to perform operations on hash-based types using an alternative key.

At first glance, using an alternative key might seem unnecessary since we can always convert our alternative type to the type used as the key. However, such conversions can come with drawbacks. For example, converting a Span<char> to a string involves creating a new string object, which generates unnecessary garbage. This overhead occurs solely for the purpose of using the generated string as a key in a hash-based collection.

With this new feature, we can now use an alternate key directly in existing hash-based types. Let’s explore how it works.

IAlternateEqualityComparer

The IAlternateEqualityComparer<TAlternate,T> interface, is essentially like having an IEqualityComparer<TAlternative,T>. It is an interface that is used for comparing two different types for equality, and its implementation needs three methods:

1. Create(TAlternate) This method creates an instance of type T that is considered equal to the provided instance of type TAlternate. It is used when adding new entries to hash-based collections. During such operations, the runtime needs a way to produce a T instance from the TAlternate instance, so it can be used as a key.
2. Equals(TAlternate, T) This method checks for equality between instances of TAlternate and T. It is primarily used for looking up values using the alternate key.
3. GetHashCode(TAlternate) This method computes a hash code for the alternate key type. It is used in the same way as the GetHashCode method for the primary key type in hash-based collections.

Currently, C# provides a built-in implementation of this interface for string and Span<char>.

The AlternateLookup Struct And The GetAlternateLookup Method

The AlternateLookup Structs, are structs that exist nested inside the various hash based types, like the dictionary and offer methods that allow operations that this hash based type supports but with the usage of an alternative key.

The GetAlternateLookup Method, is the method that will give us an instance of that type.

Here’s an example in code:

var dict = new Dictionary<string, int> {
   { "One", 1 },
   { "Two", 2 },
   { "Three", 3 }
};

var altLookup = dict.GetAlternateLookup<ReadOnlySpan<char>>();

ReadOnlySpan<char> one = "One";
ReadOnlySpan<char> two = "Two";
ReadOnlySpan<char> three = "Three";
ReadOnlySpan<char> four = "Four";

Console.WriteLine(altLookup[one]); // Retrieve value

altLookup[four] = 4; // Add new value

Console.WriteLine(dict["Four"]);

Here our altLookup variable is of type Dictionary<string, int>.AlternateLookup<ReadOnlySpan<char>>.

Along with the GetAlternateLookup, we have the TryGetAlternateLookup that can be used like this:

if(dict.TryGetAlternateLookup<ReadOnlySpan<char>>(out  var altLookup))
   Console.WriteLine("Alternative lookup with the type ReadOnlySpan<char> is supported");

An Example Of Our Own Alternate Lookup

Let’s explore how to implement our own alternative lookup between two types. Suppose we have a Person type with a unique ID, and we want to use a dictionary where the keys are Person objects, but we also want to perform lookups using their IDs as alternative keys.

Since we don’t want to create a new Person object when an ID doesn’t exist, we will skip implementing the Create method of the IAlternateEqualityComparer. In this case, our alternative keys will be used exclusively for lookups.

Here’s our Person class:

public record Person(string firstName, string lastName, int id)
{
   public string FirstName => firstName;
   public string LastName => lastName;
   public int Id => id;
}

And here’s a dictionary:

Person john = new("John", "Doe", 123);
Person bob = new("Bob", "Smith", 987);

Dictionary<Person, string> dict = new(new PersonEqualityComparer())
{
   { john, "Big street 11" },
   { bob, "Small street 99" }
};

Now we need to create a PersonEqualityComparer class that will be used for our alternative lookups:

public class PersonEqualityComparer : IEqualityComparer<Person>, IAlternateEqualityComparer<int, Person> 
{
   public bool Equals(Person? x, Person? y) => x != null && y != null && x.Id == y.Id;

   public int GetHashCode(Person person) => person.Id.GetHashCode();
   
   public bool Equals(int id, Person person) => id == person.Id;

   public int GetHashCode(int id) => id.GetHashCode();

   public Person Create(int id) => throw new NotImplementedException();
}

Our comparer type must also implement the IEqualityComparer interface. The first two methods are the required implementations of the IEqualityComparer interface, while the last three methods belong to the IAlternateEqualityComparer interface.

As mentioned earlier, we chose not to implement the Create method because we don’t intend to create a new object each time. Additionally, we lack all the necessary information (such as the first and last name) to construct a complete Person object. Our alternate lookup is designed exclusively for retrieving values, not for adding new ones.

The Equals method is straightforward in this case, as our int maps directly to the int id field of the Person record. Now, we can perform operations like this:

var altLookup = dict.GetAlternateLookup<int>();

Console.WriteLine(altLookup[123]); // Big street 11

Conclusion

The alternate lookup in our example isn’t strictly necessary, as we can retrieve the desired Person directly using its ID. It might be useful in scenarios where we don’t want to load multiple Person records into memory but still need to locate a specific record’s address using its ID. However, in such cases, it would be more efficient to design the dictionary with IDs as the primary keys from the start.

Starting with .NET 9, alternate lookups provide a convenient option. In particular, they are highly beneficial for scenarios involving Span<char> and string. By using alternate lookups, we avoid the performance cost of creating heap-allocated strings solely to retrieve values from a dictionary of strings.

As always, thank you for reading, and if you have any questions or comments you can use the comments section, or contact me directly via the contact form or by email. Also, if you don’t want to miss any of the new blog posts, you can subscribe to my newsletter or the RSS feed.