Opaque dictionary key pattern in C#

Question

I've run across a number of cases where a pattern for accessing items in a keyed collection (like a dictionary) is encumbered by the fact that the type of the key is not a simple type (string, int, double, etc) and isn't something that you would want to promote to an actual named class.

C# 3.0 introduces the concept of anonymous types which the compiler automatically generates. Unlike struct's, these dynamically generated classes provide an implementation of both Equals() and GetHashCode() - which are designed to work well with dictionary and hashtable implementation in .NET.

I've hijacked this feature to create an opaque key - essentially a generic class that allows you to create keys on the fly by providing the types that are part of the key - and using an anonymous class to actually provide the Equals/GetHashCode behavior. The intent of this class is to ONLY provide a easy means to use several values together as a key into a dictionary or hashtable. It's not intended as a class to provide meaningful application logic or data manipulation.

The benefit of the pattern is that it makes it easy to implement composite keys that always provide appropriate equality and hashing behavior. It's also easily extensible to keys of any number of dimensions (however many C# can parse as template parameters at least). We can even make improvements by allowing the OpaqueKey<> class to be inherited from so that it's properties and constructor parameters can be given more instructive names.

I am worried that this pattern may have some unintended consequences or hidden pitfalls that I'm not considering.

Are there any reasons why the following OpaqueKey code may by undesirable?

Are there any edge cases that I haven't considered in the implementation?

Is there a simpler way to achieve the same functionality?

public class OpaqueKey<A,B>
{
    private readonly object m_Key;

    // Not strictly necessary, but possibly convenient...
    public A First { get; private set; }
    public B Second { get; private set; }

    public OpaqueKey( A k1, B k2 )
    {
        m_Key = new { K1 = k1, K2 = k2 };
        First = k1;
        Second = k2;
    }

    public override bool Equals(object obj)
    {
        var otherKey = obj as OpaqueKey<A, B>;
        return otherKey == null ? false : m_Key.Equals( otherKey.m_Key );
    }

    public override int GetHashCode()
    {
        return m_Key.GetHashCode();
    }
}


public static void TrivialTestCase()
{
    var dict = new Dictionary<OpaqueKey<string,string>, string>();

    dict.Add(new OpaqueKey<string, string>("A", "B"), "AB");
    dict.Add(new OpaqueKey<string, string>("A", "C"), "AC");
    dict.Add(new OpaqueKey<string, string>("A", "D"), "AD");
    dict.Add(new OpaqueKey<string, string>("A", "E"), "AE");

    var value = dict[new OpaqueKey<string,string>("A","D")];

    Debug.Assert( value == "AD" ); // trivial test case...
}

Answer 1

Are there any reasons why the following OpaqueKey code may by undesirable?

-> You are storing two times your strings.

Is there a simpler way to achieve the same functionality?

-> Use a struct you will avoid anonymous type and storing two times your strings. The Equals/GetHashcode will be fine.

Answer 2

From what I can tell, you can use a generic Tuple class, and you have no need of the inner anonymous class. A Tuple class could be useful elsewhere in your solution (which is why .NET 4.0 will have built-in generic Tuple classes). Equals can compare the values of First and Second, while GetHashCode would combine the hashcodes of the Tuple's members.

        //4.0 Beta1 GetHashCode implementation
        int a = 5; int b = 10;
        Tuple<int, int> t = new Tuple<int, int>(a, b);

        Console.WriteLine(t.GetHashCode() == (((a << 5) + a) ^ b));

Answer 3

Have you considered the edge case of (de)serializing the dictionary to/from XML?

Answer 4

Wouldn't using KeyValuePair<TKey, TValue> as the type of the key have the same affect?

Answer 5

I've done the same thing myself with no adverse consequences. My opinion is: go for it. I've seens such a class often called a "Tuple" in other languages and in microsoft internal classes, but I've always called such a thing a CompositeKey<T1, T2> myself. I've never implemented it the way you do though, relying on the anonymous type system to do the comparison and hashing.

Have you considered whether your OpaqueKey will ever need to be serialized? Is it worth worrying that the default implementation of GetHashcode on anonymous types will change between versions of .net?

You've done the right thing in ensuring that your values are effectively readonly.

There's no simpler way to do this yet. I've seen Dictionaries of Dictionaries used to the same effect, but it's a lot more hassle because you have to create the child dictionary if it doesn't exist..

Answer 6

The drawbacks I see are:

1. Storing the key data twice (once in fields First and Second and once again in m_Key) as Guillaume pointed out.
2. Arguably, the code readability decreases. (Keys are rather verbose and new developers will need to familiarize themselves with the OpaqueKey class and concepts.)
3. Future versions of the C# compiler may change the default GetHashCode implementation for anonymous types. Although you're satisfied with the current results, I don't think that logic is guaranteed to never change.

I suppose it's not simpler, but I think in most cases it's better to just create a specific class (or struct) for each type of key you'll need. That way:

1. You're not wasting memory like you do with OpaqueKey.
2. It's more explicit, so the code readability is better and you're not taking a dependency on the C# compilers anonymous type creation logic for the important Equals and GetHashCode methods.
3. You can optimize for each type of composite key. (For example, some composite keys might have fields that are case insensitive for the purposes of equality and other composite keys might lend themselves to more optimal hash code algorithm than whatever the compiler chooses for anonymous types).

Answer 7

Why not:

public class OpaqueKey<A,B>
{
    private readonly object m_Key;

    public A First 
    { 
        get 
        {
            return m_Key.GetType().GetProperty("K1").GetValue(m_key, null);
        }
    }
    public B Second
    { 
        get 
        {
            return m_Key.GetType().GetProperty("K2").GetValue(m_key, null);
        }
    }

    public OpaqueKey( A k1, B k2 )
    {
        m_Key = new { K1 = k1, K2 = k2 };
    }

    public override bool Equals(object obj)
    {
        var otherKey = obj as OpaqueKey<A, B>;
        return otherKey == null ? false : m_Key.Equals( otherKey.m_Key );
    }

    public override int GetHashCode()
    {
           return m_Key.GetHashCode();
    }
}

PS: just a thought, not tested....

Answer 8

I'd ensure that GetHashCode for anonymous types is performant (i.e. doesn't use reflection and generates a good spread).

It may also be worth having constraints on what types could be passed. Perhaps certain types would cause problems?

Answer 9

Something like:

public class OpaqueKey
{
   objects[] values;

   public OpaqueKey(params object[] values)
   {
      this.values = values;
   }

   //implement equals and GetHashCode()
}