Getting duplicate keys added to my Dictionary

Question

I'm attempting to port some code from Java to C#. In C# I'm using a Dictionary instead of the Java HashMap. However, I'm finding that when I call Dictionary.Add() I'm getting duplicate keys. I suspect this is because the keys are different reference types but the objects should have equality. I've created a minimal example here:

Abstract Class:

using System;
using System.Text;

public abstract class HandState
{
    public int[] _cards;       // ranks only 
    public int _index;     // into _allStates array
    public char _levelIndex;   // into _levelArrays[n]
    private static String _cardValues = "23456789TJQKA";
    private static int SUIT_COUNT = 4;

    public abstract bool IsFinal();
    public abstract char Value();  // the generated array value

    public override String ToString()
    {
        StringBuilder sb = new StringBuilder();
        sb.Append("[");
        for (int i = 0; i < _cards.Length; i++)
        {
            int card = _cards[i];
            sb.Append(_cardValues[card]);
            if (i != _cards.Length - 1)
                sb.Append(" ");
        }
        sb.Append("]");
        return sb.ToString();
    }
    public bool LegalTransistion(int card)
    {
        int rankCount = 0;
        for (int i = 0; i < _cards.Length; i++)
        {
            if (_cards[i] == card)
            {
                rankCount++;
            }
        }
        return rankCount != SUIT_COUNT;
    }
    public void Init(HandState prev, int card)
    {
        int prevlen = prev._cards.Length;
        _cards = new int[prevlen + 1];
        Array.Copy(prev._cards, 0, _cards, 0, prevlen);
        _cards[prevlen] = card;
        Array.Sort(_cards);
    }
}

Extension Class:

using System;
using System.Collections;
using System.Collections.Generic;

public class NonFinalHandState : HandState //extends
{
    public HandState[] _transistions;

    private static List<HandState> _allStatesVec = new List<HandState>();
    private static int RANK_SIZE = 13;
    public NonFinalHandState(int[] cards)
    {
        _cards = (int[])cards.Clone();
    }
    public NonFinalHandState(NonFinalHandState prev, int card)
    {
        Init(prev, card);
    }
    public NonFinalHandState()
    {
        _cards = new int[0];
        _index = _allStatesVec.Count;
        _transistions = new HandState[RANK_SIZE];
        _allStatesVec.Add(this);
    }
    public override bool IsFinal()
    {
        return false;
    }
    public override char Value()
    {
        return _levelIndex;
    }
    public override bool Equals(Object o)
    {
        if (!(o.GetType() == typeof(NonFinalHandState)))
            return false;
        NonFinalHandState other = (NonFinalHandState)o;
        return Array.Equals(_cards, other._cards);
    }
    public override int GetHashCode()
    {
        return ((IStructuralEquatable)_cards).GetHashCode(EqualityComparer<int>.Default); //JAVA: Arrays.hashCode(_cards);
    }
}

Program:

using System;
using System.Collections.Generic;

namespace ConsoleAppTest
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] cards = { 1, 2, 3, 4 };
            NonFinalHandState nfhs1 = new NonFinalHandState(cards);
            NonFinalHandState nfhs2 = new NonFinalHandState(cards);

            Dictionary<HandState, HandState> dictionary = new Dictionary<HandState, HandState>();
            dictionary.Add(nfhs1, nfhs1);
            //dictionary.Add(nfhs2, nfhs2);

            if (!dictionary.ContainsKey(nfhs2))
            {
                dictionary.Add(nfhs2, nfhs2);
            }
            else
            {
                dictionary[nfhs2] = nfhs2;
            }

            Console.WriteLine(dictionary.Keys.Count);

        }
    }
}

The output is 2 but I need the keys to be recognised as identical. I think that Dictionary.Add() checks for equality of keys but even so, I'm checking for containsKey before adding the new entry. I suspect there could be a problem with my C# implementation of GetHashCode? The Java version is shown as a comment.

Any ideas?

Answer 1

I think that the problem is that your GetHashCodedoes not return equal values for equal arrays:

public override int GetHashCode()
{
    return ((IStructuralEquatable)_cards).GetHashCode(EqualityComparer<int>.Default); //JAVA: Arrays.hashCode(_cards);
}

This will work:

public override int GetHashCode()
{
    if(_cards == null) return int.MinValue;
    unchecked 
    {
        int hash = 17;
        foreach(int c in _cards)
            hash = hash * 23 + c.GetHashCode();
        return hash;
    }
}

You also have to fix the logic in Equals, this is wrong, Array.Equals compares references:

public override bool Equals(Object o)
{
    if (!(o.GetType() == typeof(NonFinalHandState)))
        return false;
    NonFinalHandState other = (NonFinalHandState)o;
    return Array.Equals(_cards, other._cards);
}

Use this:

public override bool Equals(Object o)
{
    NonFinalHandState other = o as NonFinalHandState;
    if(other == null) return false;
    if(this._cards?.Equals(other._cards) == true) return true; // reference comparison
    if(_cards == null || other._cards == null) return false;
    return _cards.SequenceEqual(other._cards); // add using System.Linq
}

---

I will show you another approach, you can use a custom IEqualityComparer<T> that works with any kind of sequences(like arrays or lists):

public class EnumerableComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    private IEqualityComparer<T> m_comparer;

    public EnumerableComparer()
    {
        m_comparer = EqualityComparer<T>.Default;
    }

    public EnumerableComparer(IEqualityComparer<T> comparer)
    {
        m_comparer = comparer ?? EqualityComparer<T>.Default;
    }

    public bool Equals(IEnumerable<T> x, IEnumerable<T> y)
    {
        return Object.ReferenceEquals(x, y) || (x != null && y != null && x.SequenceEqual(y, m_comparer));
    }

    public int GetHashCode(IEnumerable<T> items)
    {
        if(items == null) return 0;
        unchecked
        {
            int hash = 17;
            foreach (T item in items)
                hash = hash * 23 + m_comparer.GetHashCode(t);
            return hash;
        }
    }
}

With this EnumerableComparer you can also "feed" your NonFinalHandState:

public class NonFinalHandState : HandState //extends
{
    private EnumerableComparer<int> _cardsComparer = new EnumerableComparer<int>();
    // ...
    public override bool Equals(Object o) => o is NonFinalHandState nfhs2 && _cardsComparer.Equals(_cards, nfhs2._cards);
    public override int GetHashCode() => _cardsComparer.GetHashCode(_cards);
}