Dictionary with a Custom Key

Introduction

Generic dictionaries are great, but sometimes the built-in data types just doesn't suffice as keys. Perhaps you want to use more than one value as key, or a data type that doesn't support comparing by default.

Expandability

Luckily, the .NET Framework is built in a way that easily allows expansion. By creating a class to use as key, and a comparer that the dictionary uses to compare the key values, you can put anything you like in the key.

The Key Class

First, let's create a class to use as key in a dictionary. As an example I will use a dictionary that will keep track of cars parked in a parking garage. The parking spaces are identified by a floor number and and parking space number for that floor, so the key will have two integer properties; floor and parkingSpace:

public class ParkingSpaceKey {

    private int _floor, _parkingSpace;

    public ParkingSpaceKey(int floor, int parkingSpace) {
        _floor = floor;
        _parkingSpace = parkingSpace;
    }

}

So far all you can do with the class is to create instances of it, but we will add a comparer to it so that we can use it with a dictionary.

The Comparer

The IEqualityComparer<T> interface is used to implement a comparer for a dictionary. It has two methods that you need to implement: Equals and GetHashCode.

The Equals method is used to compare two key values. It simply returns true if the values are equal.

The GetHashCode method returns a hash code value for a specific key value. The hash code is what the dictionary uses to divide all the items in the dictionary into buckets. That is what gives speed to the dictionary.

There is a lot you can read about how you create good hash keys, but there are just two things that you need to know to make a hash code that works reasonably well in most situations:

1. The method must always return the same hash code for a specific key value.
2. The hash codes should be evenly distributed, so that you get as many buckets as possible in the dictionary.

Let's look at two examples of implementations. The first just returns the same value all the time:

public int GetHashCode() { return 0; }

This fulfills the rule that a specific key value always gets the same hash code, so the hash code actually works. The distribution of the hash codes is terrible, though. The dictionary would only get a single bucket to store all items in.

The second implementation is the actual implementation of the GetHashCode method for the System.Int32 structure:

public int GetHashCode() { return this; }

The hash code for an integer is actually the integer itself, which satisfies the rule that the hash code is always the same for a value. When it comes to distribution, it does not only work, it's actually the ideal implementation. Every key value will get it's own bucket in the dictionary, so you will always have as many buckets as possible. (It's of course only possible to make an ideal implementation if the key doesn't contain more than 32 bits of data, as the hash code contains 32 bits of data. If you have more data in the key, some key values have to share the same hash code.)

Implementing the Comparer

For our parking space example, we will just take the two integer values and do an exclusive or between them to create a hash code. Perhaps not the best implementation possible, but certainly good enough for this example.

Now, let's create a class that implements the IEqualityComparer<T> interface, and put it in the ParkingSpaceKey class. By putting the comparer inside the key class, you get two advantages. It's obvious what the class does, and you have access to the private variables in the key class from the comparer class.

public class ParkingSpaceKey {

    private int _floor, _parkingSpace;

    public ParkingSpaceKey(int floor, int parkingSpace) {
        _floor = floor;
        _parkingSpace = parkingSpace;
    }

    public class EqualityComparer : IEqualityComparer<ParkingSpaceKey> {

        public bool Equals(ParkingSpaceKey x, ParkingSpaceKey y) {
            return x._floor == y._floor && x._parkingSpace == y._parkingSpace;
        }

        public int GetHasCode(ParkingSpaceKey x) {
            return x._floor ^ x._parkingSpace;
        }

    }

}

That's all it takes to make a custom key for a dictionary. There are no properties for reading the values that are stored in the key. You can add them if you like, but that isn't needed to use the class as a key. The comparer doesn't care what the key contains, it only needs to be able to compare key values and to get a hash code for a key.

Use the Custom Key Class

Now you can use the comparer when you create a dictionary:

Dictionary<ParkingSpaceKey, Car> garage = new Dictionary<ParkingSpaceKey, Car>(
    new ParkingSpaceKey.EqualityComparer());

It's crucial that you actually remember to create an instance of the comparer for the dictionary. Otherwise the dictionary will use the default way of comparing the key objects, which will be comparing the references. (That means that even if you create a key with the same values as a key in the dictionary, it can't be used to find it as they are separete object so they doesn't have the same reference.)

To use the dictionary, you simply create a key object with the values you need to access. Example:

ParkingSpaceKey key = new ParkingSpaceKey(4, 42);
if (garage.ContainsKey(key)) {
    Console.WriteLine("Parking space occupied.");
} else {
    Console.WriteLine("Parking space available.");
}

That all, folks.

Resources

Wikipedia: hash table
MSDN Library: IEqualityComparer interface
MSDN Library: Dictionary class

Points of Interest

I learned about this when I needed dictionaries to cache data for a web application. Some of the data is depending on several different variables, so I needed dictionaries with custom keys.