TopMenu

▼

Using generic List as key in Dictionaries

Dictionaries in CSharp are datastructure which represents hash maps. You can store key value based data easily also it prevents to insert duplicate keys. But sometime it comes as requirement where you have a list of items which you want to use as a key in dictionary. The following wouldn’t be so common and only occur rare but it’s a possibility that you would also face the same situation so I came to share the same with you guys.

Problem: Now here the trouble starts. If you use generic list as key the default equality comparer checks for default has and simple object reference equality in Dictionary for keys. Now for two similar lists with similar underlying items would result in getting those two lists as different items. Which means you can add the two lists with similar items in Dictionary as a key with no objection. But what is benefit of using Dictionary then?

Solution: There’s an overload of constructor of Dictionary which accepts the custom Equality comparer for keys. So I’ve created custom equality comparer and it was also tricky to write that custom comparer.

So implementation of the custom equality comparer would look something like:

public class ListComparer<T> : IEqualityComparer<List<T>> where T:class 
{
    public bool Equals(List<T> x, List<T> y)
    {
        if (x.Count == y.Count)
        {
            for (int i = 0; i < x.Count; i++)
            {
                // Compare the objects based on values
                if (!(x[i] as T).PublicInstancePropertiesEqual(y[i] as T))
                {
                    return false;
                }
            }
        }
 
        return true;
    }
 
    public int GetHashCode(List<T> obj)
    {
        int hash = 19;
 
        foreach (T t in obj)
        {
            foreach (var objProperty in t.GetType().GetProperties())
            {
                if (objProperty.GetType().IsClass)
                {
                    hash ^= (hash * 31) + objProperty.SafeGetHashCode();
                }
                else
                {
                    hash ^= (hash * 31) + objProperty.GetHashCode();
                }
            }
        }
 
        return hash;
    }
}

Now why I have to write so much custom code in the Equals and GetHashCode method. If I use simple and direct solution then these list will always be different. So I have to XOR the hashcode of underlying items in both lists to get the hashcode based on the items rather than list reference. I found dealing with Hashcode from John Skeet’s post on stackoverlflow.


For equals method, I need to compare the values of the public properties of the list items as the reference would be different so again we felt into the same situation. But after comparing the values and hashcode individually for each item of list we can ensure if we’re not adding similar stuff again and again in the dictionary.


Here’s the Extension methods used in the custom Eqality comparer.



public static class EqualityExtension
{
    public static int SafeGetHashCode<T>(this T value) where T : class
    {
        return value == null ? 0 : value.GetHashCode();
    }
 
    public static bool PublicInstancePropertiesEqual<T>(this T self, T to, params string[] ignore) where T : class
    {
        if (self != null && to != null)
        {
            var type = typeof(T);
            var ignoreList = new List<string>(ignore);
            var unequalProperties =
                from pi in type.GetProperties(BindingFlags.Public | BindingFlags.Instance)
                where !ignoreList.Contains(pi.Name)
                let selfValue = type.GetProperty(pi.Name).GetValue(self, null)
                let toValue = type.GetProperty(pi.Name).GetValue(to, null)
                where selfValue != toValue && (selfValue == null || !selfValue.Equals(toValue))
                select selfValue;
            return !unequalProperties.Any();
        }
        return self == to;
    }
}

Hope you enjoyed the article.


For complete code sample download it form here.


References:

No comments: