Best approach to multi-part int dictionary key?

Question

Say my dictionary needs to be keyed by a combination of ItemId and RegionId, both int. And say the type of the value side is "Data". I could do this a couple of ways:

Way 1: multi-level dictionary, like this:

Dictionary<int, Dictionary<int, Data>>  myData;

so a lookup could be coded like this:

Data data1  = myData[itemId][regionId];

Not bad, but a drawback is that I would need to check for key existence at the first level, so safer code would be

Data data1 = null;
if (myData.ContainsKey(itemId)) data1 =  myData[itemId][regionId];

Way 2: use a multi-part key. In this approach I would create a struct to represent the parts, and use a struct as the dictionary key:

private struct MultiPartKey
{
    public int ItemId;
    public int RegionId;
}

Dictionary<MultiPartKey, Data>  myData;

and a lookup would be like:

MultiPartKey mpk;
mpk.ItemId = itemId;
mpk.RegionId = regionId;
Data data1 = myData[mpk];

A possible disadvantage here is that it only works if my struct is composed entirely of simple value types, so that a bitwise comparison of two instances will be equal. (Right?)

What do you think?

Answer 1

Rather than make your struct "dumb" like that (and mutable) you can make it immutable and give it appropriate equality methods, e.g.

private struct MultiPartKey : IEquatable<MultiPartKey>
{
    private readonly int itemId;
    private readonly int regionId;

    public int ItemId { get { return itemId; } }
    public int RegionId { get { return regionId; } }

    public MultiPartKey(int itemId, int regionId)
    {
        this.itemId = itemId;
        this.regionId = regionId;
    }

    public override int GetHashCode()
    {
        int hash = 17;
        hash = hash * 31 + itemId;
        hash = hash * 31 + regionId;
        return hash;
    }

    public override bool Equals(object other)
    {
        return other is MultiPartKey ? Equals((MultiPartKey)other) : false;
    }

    public bool Equals(MultiPartKey other)
    {
        return itemId == other.itemId &&
               regionId == other.regionId;
    }
}

You can expand that to use whatever types you want, so long as you implement equality and hash code properly. Implementing IEquatable<MultiPartKey> means the dictionary won't need to box the keys in order to compare them.

The downside of using this approach instead of the Dictionary<int, Dictionary<int, Data>> is that you can't easily find all entries for a given item ID.

Answer 2

Yet another way would be to use the Tuple class:

Dictionary<Tuple<int, int>, Data>  myData;

This works with up to eight values, provided they implement Equals and GetHashCode.