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?

Your key-class should override `Equals` and `GetHashCode` to allow comparison. http://msdn.microsoft.com/en-us/library/kw5aaea4%28VS.80%29.aspx — Tim Schmelter, Feb 11 '11 at 22:03
possible duplicate of [Tuples( or arrays ) as Dictionary keys in C#](http://stackoverflow.com/questions/955982/tuples-or-arrays-as-dictionary-keys-in-c-sharp). **Also** [is-there-a-benefit-to-tuple-based-or-nested-dictionaries](http://stackoverflow.com/questions/11908991/is-there-a-benefit-to-tuple-based-or-nested-dictionaries) — nawfal, May 19 '14 at 13:31

score 19 · Accepted Answer · answered Feb 11 '11 at 22:06

19

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.

answered Feb 11 '11 at 22:06

Jon Skeet

1,421,763
867
9,128
9,194

1

thank you Jon and others for your responses, but within the constraint I stated (struct with only value-type members) I would not need to override equals or gethashcode would I? .Net equality on value types (such as struct) would be a bitwise comparison. – Elroy Flynn Feb 11 '11 at 22:13
@Elroy: While you don't *have* to, I personally would. Aside from anything else, it will prevent boxing. – Jon Skeet Feb 11 '11 at 22:15
@Elroy: The other point is that then you *aren't* constrained to simple value types. Oh, and I seem to remember that the hash code generated by default for structs only uses the first field, which would be pretty rubbish in terms of hash collisions in your case. – Jon Skeet Feb 11 '11 at 22:21
Thanks for the `IEquatable` tip. And yes, you remember correctly, from [ValueType.GetHashCode](http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx): "One or more fields of the derived type is used to calculate the return value. If you call the derived type's GetHashCode method, the return value is not likely to be suitable for use as a key in a hash table." – Allon Guralnek Feb 11 '11 at 22:48
It is OK to throw a `NullReferenceException` in `IEquatable.Equals` method? – astef Jan 14 '16 at 15:12
1

@astef: That isn't possible here - because `MultiPartKey` is a struct. – Jon Skeet Jan 14 '16 at 21:16

Codo · Answer 2 · 2013-06-13T09:21:42.367

11

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.

edited Jun 13 '13 at 09:21

answered Feb 11 '11 at 22:07

Codo

75,595
17
168
206

Best approach to multi-part int dictionary key?

2 Answers2