...Removing All Doubt

The astute among you realized right away that PolyDictionary does not really avoid a cast, it just hides it. The TryGetValue() has a cast in it, highlighted below,

        public bool TryGetValue<K, V>(Key<K, V> key, out V value) {
            object objValue;
            if (_table.TryGetValue(key, out objValue)) {
                value = (V)objValue;
                return true;
            }
            value = default(V);
            return false;
        }

So, can we get rid of the this cast? Yes, but the results are not very pleasant. One approach is to create one dictionary for each unique value type and then find that dictionary by that type and index into it using the key, instead of storing all the values in the same dictionary. This sounds similar to the original problem! All we need is a PolyDictionary that maps T to Dictionary<Key<T>, T>. We could code this but we couldn't run it because we would be defining PolyDictionary in terms of itself, consuming all of memory in the process. We need something like PolyDictionary but isn't a PolyDictionary.

OK, things will now get ugly. Have your barf bags on the stand-by! And, for the love of God, don't ever put this in a production application!

Now that is off my chest, here is one technique to avoid the cast. You can create a nested class SubDictionary that has a static instance variable which maps PolyDictionaries to Dictionary<Key<T>, T>. We can then parameterize SubDictionary by T which will create a unique dictionary for each T (I warned you it was ugly). This is because the CLR treats every instantiation of SubDictionary<T> as a unique type with unique static variables. Essentially we are tricking the CLR into producing a dictionary of T to Dictionary<PolyDictionary,Dictionary<Key<T>,T>>. Since the variable is static we need to find the version that is for the instance we are using, hence the key of PolyDictionary.

Here is the example,

    /* Never, Never use this code! */
    class PolyDictionary {
        
        class SubDictionaries<T> {
            internal static Dictionary<PolyDictionary, Dictionary<Key<T>, T>> Dictionaries = 
                new Dictionary<PolyDictionary,Dictionary<Key<T>,T>>();
        }

        public PolyDictionary() { }

        public void Add<T>(Key<T> key, T value) {
            Dictionary<Key<T>, T> subDictionary = GetDictionary(key);
            subDictionary.Add(key, value);
        }

        public T Get<T>(Key<T> key) {
            Dictionary<Key<T>, T> subDictionary = FindDictionary(key);
            if (subDictionary != null)
                return subDictionary[key];
            throw new KeyNotFoundException();
        }

        public bool TryGetValue<T>(Key<T> key, out T value) {
            Dictionary<Key<T>, T> subDictionary = FindDictionary(key);
            if (subDictionary != null)
                return subDictionary.TryGetValue(key, out value);
            else {
                value = default(T);
                return false;
            }
        }

        Dictionary<Key<T>, T> FindDictionary<T>(Key<T> key) {
            Dictionary<Key<T>, T> subDictionary;
            if (!SubDictionaries<T>.Dictionaries.TryGetValue(this, out subDictionary))
                return null;
            return subDictionary;
        }

        Dictionary<Key<T>, T> GetDictionary<T>(Key<T> key) {
            Dictionary<Key<T>, T> subDictionary;
            if (!SubDictionaries<T>.Dictionaries.TryGetValue(this, out subDictionary)) {
                subDictionary = new Dictionary<Key<T>, T>();
                SubDictionaries<T>.Dictionaries.Add(this, subDictionary);
            }
            return subDictionary;
        }
    }

This code has so many problems I don't know where to start. For one, it never frees memory, the dictionaries are in memory and will never be collected. I only include it to show that it can be done. As you can see, sometimes it is better to have a cast. There might be better techniques that eliminate some of the problems but my feeling is, why bother. The cast is not that bad.