1

I'm trying to use an int array as key in C# and the behaviour I'm seeing is unexpected (for me). 

var result = new Dictionary<int[], int>();
result[new [] {1, 1}] = 100;
result[new [] {1, 1}] = 200;

Assert.AreEqual(1, result.Count); // false is 2

It seems the same with List too.

var result = new Dictionary<List<int>, int>();
result[new List<int> { 1, 1 }] = 100;
result[new List<int> { 1, 1 }] = 200;

Assert.AreEqual(1, result.Count); // false is 2

I'm expecting the Dictionary to use Equals to decide if a Key is present in the map. This doesn't seem to be the case.

Can someone explain why and how I can get this sort of behaviour to work?

joejag
  • 314
  • 1
  • 9
  • 2
    Default equality is instance equality of the array/list itself, not the contents of the data structure. You're passing two different instances with the same contents, which doesn't cause a key collision. You can pass your own `IEqualityComperer` when constructing the dictionary that can use whatever logic you'd like to compare keys for equality. – Preston Guillot Apr 03 '16 at 23:44

3 Answers3

5

.NET lists and arrays do not have a built-in equality comparison, so you need to provide your own:

class ArrayEqComparer : IEqualityComparer<int[]> {

    public static readonly IEqualityComparer<int[]> Instance =
        new ArrayEqComparer();

    public bool Equals(int[] b1, int[] b2) {
        if (b2 == null && b1 == null)
           return true;
        else if (b1 == null | b2 == null)
           return false;
        return b1.SequenceEqual(b2);
    }

    public int GetHashCode(int[] a) {
        return a.Aggregate(37, (p, v) => 31*v + p);
    }
}

Now you can construct your dictionary as follows:

var result = new Dictionary<int[],int>(ArrayEqComparer.Instance);
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • Is there a built-in Dictionary with this behaviour already? Or in a popular library? – joejag Apr 03 '16 at 23:52
  • @joejag Much to my surprise, there isn't a built-in equality comparator for collections, even though the framework has enough "plumbing" to make it work generically. I don't know of any popular library to provide this functionality, either. – Sergey Kalinichenko Apr 03 '16 at 23:54
  • Just out of curiosity, why 37 and 31 in your `GetHasCode`? – devuxer Apr 03 '16 at 23:57
  • 1
    @devuxer I started multiplying by 31 after looking at Java's implementation of `hashCode` in `String`. [Here is a good explanation of why it was done](http://stackoverflow.com/q/299304/335858). I picked 37 as another small prime more or less at random. – Sergey Kalinichenko Apr 04 '16 at 00:00
  • This shows the equality issue: Assert.IsTrue(new[] {1, 1} == new[] { 1, 1 }); // false – joejag Apr 04 '16 at 00:03
1

The Dictionary class allows a custom equality comparer as a dictionary comparer. Implement IEqualityComparer> by providing a GetHashCode(IList obj) by returning the xor (the ^ operator) of all list elements (0 ^ first ^ second...) and Equals(IList x, IList y) by using Linq.Enumerable.SequenceEquals. Then pass an instance of that to the Dictionary constructor.

Paul Pervinkler
  • 162
  • 6
0

You are passing new object (array or list) as a key. As a new object it has a different reference so it is accepted as new key.

Bassem
  • 820
  • 9
  • 17