C#: Dictionary indexed by List

Question

I try to write a program where Dictionary is indexed by List. (trust me i do, and yes there are option, but i like indexing by list). There is a minimal working (actually not working, only one last line which is a problem) example:

using System;
using System.Collections.Generic;

namespace test
{
    class Program
    {
    static void Main(string[] args)
    {
        Dictionary<List<String>, int> h = new Dictionary<List<string>,int>();

        List<String> w = new List<string> {"a"};
        h.Add(w, 1);

        w = new List<string>{"b"};
        h.Add(w,2);

        w = new List<string>{"a"};

        int value = 0;
        h.TryGetValue(w, out value);
        Console.WriteLine(value+" "+h[w]);
    }
}

if one debugs this program, he will clearly see that there two elements in h, but still these elements are not accessible via correct indexes --- h[w]. Am I wrong or is there something weird going on?

Answer 1

The problem with your app extends from the fact that:

new List<String> { "a" } != new List<String> { "a" }

Equality for lists checks to see if the two references refer to the same instance. In this case, they don't. You've instead created two Lists with the same elements...which doesn't make them equal.

You can fix the problem by creating a custom Equality Comparer:

public class ListEqualityComparer<T> : IEqualityComparer<List<T>>
{
    public bool Equals(List<T> list1, List<T> list2)
    {
        return list1.SequenceEquals(list2);
    }

    public int GetHashCode(List<T> list)
    {
        if(list != null && list.Length > 0)
        {
            var hashcode = list[0].GetHashCode();
            for(var i = 1; i <= list.Length; i++)
                hashcode ^= list[i].GetHashCode();

            return hashcode;
        }

        return 0;
    }
}

And then passing that to the Dictionary constructor:

Dictionary<List<String>, int> h = 
    new Dictionary<List<string>,int>(new ListEqualityComparer<String>());

Answer 2

The problem is the index by List, what you are indexing by isn't the data in the list but you are essentially indexing by the memory pointer to the List (i.e the memory address of where this List is located).

You Created one list at one memory location, you then created a totally different list at a different memory location (ie when you create a new instance). The two lists are different even though they contain the same data, and this means you can add as many as you want to the dictionary.

One solution is Rather than indexing by List would be to index by String and use a comma separated List containing all the data in your list as an index.

Answer 3

This won't ever work for you, because List<T>'s Equals and GetHashCode methods don't consider the contents of the list. If you want to use a collection of objects as a key, you'll need to implement your own collection type that overrides Equals in such a way as to check the equality of the objects in the collection (perhaps using Enumerable.SequenceEqual.)

Answer 4

The Dictionary class uses reference comparison to look for the specified key, that's why even if the lists contain the same items, they are different.