using List as dictionary key c#

Question

I have a dictionary the key for which is a list which is as follows

var dict = new Dictionary<List<MyKey>, Emp>(new MyCustomComparer());

I am having trouble implementing the List comparer. Even though the value exists the containskey always returns false. This is code I have written

Program.cs

        var dict = new Dictionary<List<MyKey>, Emp>(new MyCustomComparer());

        var key1 = new List<MyKey>
                       {
                           {new MyKey{ Name = "string1"}}
                       };

        dict.Add(key1, new Emp());
        var key2 = new List<MyKey>
                       {
                           {new MyKey{ Name = "string1"}}
                       };


        if (!dict.ContainsKey(key2))
        {
            dict.Add(key2, new Emp());
        }

Key class

public class MyKey
{
    public string Name { get; set; }

}

public class Emp
{
}

Comparer class

public class MyCustomComparer : IEqualityComparer<List<MyKey>>
{
    public bool Equals(List<MyKey> x, List<MyKey> y)
    {
        return x.SequenceEqual(y);
    }

    public int GetHashCode(List<MyKey> obj)
    {
        return string.Join(",", obj.Select(s => s.Name)).GetHashCode();
    }

}

Any help will be much appreciated.

regards

You have no `GetHashCode` and `Equals` implementations in your `MyKey` class so the comparisons in `SequenceEqual` are going to compare references, not the values of the `Name` property. — Preston Guillot, Nov 26 '14 at 16:49
Your `GetHashCode()` is also a problem, it is getting the hash code of the `IEnumerable` that is returned. But your bigger problem is if you change one of the lists while it is performing the roll as a key it will break the dictionary. Dictionary can not handle objects mutating while they perform the roll of key. — Scott Chamberlain, Nov 26 '14 at 16:50
@PrestonGuillot: It would be about having `Equals` and `GetHashCode` in key type, but yeah, that is what it is. — Jean Hominal, Nov 26 '14 at 16:51
In addition to @ScottChamberlain, you should at least use `ReadOnlyCollection` instead of `List`. Having mutable structures as a dictionary key can bite you... Second, the `GetHashCode` for `MyCustomComparer` is returning the hash code of `IEnumerable`, not from the Name properties. I think you forgot to join the strings? — Ortiga, Nov 26 '14 at 16:55
Also, even if you use an immutable list, and implement `GetHashCode` and `Equals` on `MyKey` to depend on `MyKey.Name`, you still have the issue that `MyKey.Name` is mutable - if the value of that property changes in a list that is used as a key, then the dictionary will break. General Tip: Do not use mutable objects as keys for dictionaries. — Jean Hominal, Nov 26 '14 at 16:58
Thanks all, I have changed the code as per your suggestion and it works now. Although I am not sure if I can get rid of the string in the comparer. It works now — user1131926, Nov 26 '14 at 17:02
@user1131926 Then post an answer showing how you fixed it. Don't edit your question. Now you have a question with working code asking "Why does this code not work". — Scott Chamberlain, Nov 26 '14 at 17:05

score 0 · Answer 1 · answered Nov 26 '14 at 17:14

0

Posting the changed code

    var dict = new Dictionary<List<MyKey>, Emp>(new MyCustomComparer());

    var key1 = new List<MyKey>
                   {
                       {new MyKey{ Name = "string1"}}
                   };

    dict.Add(key1, new Emp());
    var key2 = new List<MyKey>
                   {
                       {new MyKey{ Name = "string1"}}
                   };


    if (!dict.ContainsKey(key2))
    {
        dict.Add(key2, new Emp());
    }


public class MyKey
{
    public string Name { get; set; }

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

    public override bool Equals(object obj)
    {
        var myKey = obj as MyKey;
        if (myKey != null)
        {
            return Name == myKey.Name;
        }
        return false;
    }
}

public class Emp
{
}

comparer class

public class MyCustomComparer : IEqualityComparer<IEnumerable<MyKey>>
{
    public bool Equals(IEnumerable<MyKey> x, IEnumerable<MyKey> y)
    {
        return x.SequenceEqual(y);
    }

    public int GetHashCode(IEnumerable<MyKey> obj)
    {
        return string.Join(",", obj.Select(s => s.Name)).GetHashCode();
    }

}

answered Nov 26 '14 at 17:14

user1131926

1,311
2
18
32

While this does solve your immediate problem you are going to run in to issues if you modify the list after you add it to the dictionary. To see this in action make `key1` a empty list then call `dict.Add(key1, new Emp());` after that do `key1.Add(new MyKey{ Name = "string1"})` then run the rest of your program unmodified. – Scott Chamberlain Nov 26 '14 at 17:18
Your comparer can be easily broken if any of the names have commas in them. You shouldn't be concatting the strings together, but rather combining the hashes of each of the strings. – Servy Nov 26 '14 at 17:18
@Servy I agree that he should not be combining strings but a comma in the name would not break it. In fact he could just as easly do `string.Join("", obj.Select(s => s.Name))` the string is never "looked at" it is only used as a opaque blob for generating the hash code. – Scott Chamberlain Nov 26 '14 at 17:22
@ScottChamberlain In this case his `Equals` check is done properly, so yes, it would only increase his collision rate, rather than cause incorrect behavior. I'm used to seeing people use the same pattern in both places, resulting in possible false positives. – Servy Nov 26 '14 at 17:25
@ScottChamberlain what will be your suggestion ? – user1131926 Nov 26 '14 at 18:22
Well because your keys are really just the string of names change your dictionary to be `Dictionary` and just use `string.Join(",", key1.Select(s => s.Name))` as the key. You could get some false positives for example the list `{"a,b", "c"}` and the list `{"a", "b", "c"}` would be equal but you could get around that by using a non printable character as your separator. Any character would work (except maybe `\0`), I recommend the character "Record Separator" (hex value `1E`) so your join would be `string.Join("\x1E", key1.Select(s => s.Name))` – Scott Chamberlain Nov 26 '14 at 18:50

Jose M. · Answer 2 · 2014-11-26T22:41:14.653

0

Another approach:

    public class MyCustomKey : ReadOnlyCollection<MyKey>
    {
        public override int GetHashCode()
        {
            return this.Aggregate(0, (c, i) => c + i.Name.GetHashCode()*i.Name.Length);
        }

        public override bool Equals(object obj)
        {
            var myKey = obj as MyCustomKey;
            if (myKey!= null && myKey.Count == this.Count)
            {
                return myKey.Zip(this, (i, j) => i.Name == j.Name).All(i=>i);
            }
            return false;
        }
    }

    var dict = new Dictionary<MyCustomKey, Emp>();

    var key1 = new MyCustomKey(new[] {new MyKey {Name = "string1"}});
    dict.Add(key1, new Emp());
    var key2 = new MyCustomKey(new[] {new MyKey {Name = "string1"}});

    if (!dict.ContainsKey(key2))
    {
         dict.Add(key2, new Emp());
    }

edited Nov 26 '14 at 22:41

answered Nov 26 '14 at 17:27

Jose M.

1,296
17
22

@PrestonGuillot Actually the accepted answer for that question says this is the perfect time to inherit from list. All the poster is doing is extending the behavior of List to support generating the hash code and equals to use the members in the list. The list still only represents a list, it just modifies equality behavior. – Scott Chamberlain Nov 26 '14 at 18:57
@ScottChamberlain I'd argue that a key must/should be immutable, and since List isn't, the class doesn't actually represent a list. ReadOnlyCollection I'd buy. – Preston Guillot Nov 26 '14 at 19:13
Thanks, I've edited my answer to make the immutable key – Jose M. Nov 26 '14 at 22:41

using List as dictionary key c#

2 Answers2