Understanding behavior & overriding GetHashCode()

Question

I tried to followed the Guidelines from MSDN and also referred to This great question but the following seems to not behave as expected.

I'm trying to represent a structure similar to a FQN where as if P1 was listed before P2, P2 would only exist in the same set as P1. Like how scope works.

---

On the subject of GetHashCode()

I have a class with properties like this.

class data{
   public readonly string p1, p2;
   public data(string p1, string p2) {
       this.p1 = p1;
       this.p2 = p2;
   }
   public override int GetHashCode()
   {
       return this.p1.GetHashCode() ^ this.p2.GetHashCode();
   }
  /*also show the equal for comparison*/
    public override bool Equals(System.Object obj)
    {
        if (obj == null)
            return false;
        data d = obj as data;
        if ((System.Object)d == null)
            return false;
        /*I thought this would be smart*/
        return d.ToString() == this.ToString();
    }
    public override string ToString() {
        return "[" + p1 +"][" + p2+ "]";
    }
}

In a Dictionary (dict) I use data as a key, so this would make the scope look like d1.p1.p2 (or rather p2 of p1 of d1, however you prefer to imagine it)

Dictionary<data,int> dict = new Dictionary<data,int>();

I've examined the behavior when d1.p1 and another d2.p1 are different, the operation resolves correctly. However when d1.p1 and d2.p1 are the same and p2 of d1 and d2 are different I observe the following behavior.

data d1 = new data(){ p1="p1", p2="p2"  };
data d2 = new data(){ p1="p1", p2="XX"  };
dict.add(d1, 0);
dict.add(d2, 1);
dict[d1] = 4;

The result is that both elements are 4

1. Is GetHashCode() overridden correctly?
2. Is Equals overridden correctly?
3. If they are both fine how/why does this behavior happen?

---

On the subject of a Dictionary

In the watch window (VS2013), I have my dictionary's key list show me, instead of a single key per index as I would normally expect, each property of my data object is a key for a single index. So I'm not sure if in there lay the problem or I'm just misunderstanding the Watch window's representation of an object as a key. I know how that is the way VS will display an object but, I'm not certain that's how I would expect it to be displayed for a key in a dictionary.

1. I thought GetHashCode() was a Dictionary's primary "comparison" operation, is this always correct?
2. What's the real "Index" to a Dictionary where the key is an object?

UPDATE

After looking at each hash code directly I noticed that they do repeat. Yet the Dictionary does not determine that the index exists. Below is an example of the data I see.

1132917379      string: [ABC][ABC]   
-565659420      string: [ABC][123]  
-1936108909     string: [123][123]  
//second loop with next set of strings   
1132917379      string: [xxx][xxx]  
-565659420      string: [xxx][yyy]
//...etc

Answer 1

1. Is GetHachCode() overridden correctly?

Sure, for some definition of "correct". It may not be overridden well, but it's not an incorrect implementation (since two instances of the class that are considered equal will hash to the same value). Of course with that requirement you could always just return 0 from GetHashCode and it would be "correct". It certainly wouldn't be good.

That said your particular implementation is not as good as it could be. For example, in your class, the order of the strings matter. I.e. new data( "A", "B" ) != new data( "B", "A" ). However, these will always hash equal because your GetHashCode implementation is symmetric. Better to break the symmetry in some fashion. For example:

public int GetHashCode()
{
    return p1.GetHashCode() ^ ( 13 * p2.GetHashCode() );
}

Now it's less likely that there will be a collision for two instances that are not equal.

1. Is Equal overridden correctly?

Well, it can definitely be improved. For example, the first null check is redundant and so is the cast to object in the second comparison. The whole thing would probably be better written as:

public bool Equals( object obj )
{
    var other = obj as data;
    if( other == null ) return false;
    return p1 == obj.p1 && p2 == obj.p2;
}

I also removed the call to ToString since it doesn't significantly simplify the code or make it more readable. It's also an inefficient way of performing the comparison, since you have to construct two new strings before the comparison even happens. Just comparing the members directly gives you more opportunities for an early out and, more importantly, is a lot easier to read (the actual equality implementation doesn't depend on the string representation).

1. If they are both fine how/why does this behavior happen?

I don't know, because the code you've given won't do this. It also won't compile. Your data class has two readonly fields, you can't assign those using an initializer list as you've shown in your last code snippet.

I can only speculate as to the behavior you're seeing, because nothing you've shown here would result in the behavior as described.

The best advice I can give is to make sure that your key class is not mutable. Mutable types will not play nice with Dictionary. The Dictionary class does not expect the hash codes of objects to change, so if GetHashCode depends on any part of your class that is mutable, it's very possible for things to get very messed up.

1. I thought GetHachCode() was a Dictionary's primary "comparison" operation, is this always correct?

Dictionary only uses GetHashCode as a way to "address" objects (to be specific the hash code is used to identify which bucket an item should be placed in). It doesn't use it directly as a comparison necessarily. And if it does, it can only use it to determine that two objects are not equal, it can't use it to determine if they are equal.

1. What's the real "Index" to a Dictionary where the key is an object?

I'm not entirely sure what you're asking here, but I'm inclined to say that the answer is that it doesn't matter. Where the item goes is unimportant. If you care about that sort of thing, you probably shouldn't be using a Dictionary.

Answer 2

Is GetHashCode() overridden correctly?

No. You allow passing null for p1 or p2 and null.GetHashCode() throws a NullReferenceException which is not allowed in GetHashCode. Either forbid passing null, or make GetHashCode return an int for nulls (zero is OK).

You are also XORing unaltered ints; this means every class you create that contain two of the same values will have a hashCode of zero. This is a very common collision; typically one multiplies each hashcode by a prime number to avoid this.

Is Equals overridden correctly?

No. The page you linked to is the non-generic Equals used by System.Collections.HashTable. You are using the generic System.Collections.Generic.Dictionary, which uses the generic IEquatable<T>. You need to implement IEquatable<data> as explained in the accepted answer to the SO question you posted.

It is true that IEquatable<data> will fall back to Equals(System.Object obj) if not defined, but do not rely on that behavior. Also, converting ints to strings to compare them is not “smart”. Any time you feel you should write a comment excusing something as “smart” you are making a mistake.

A better implementation of 'data` would be:

public class MatPair : IEquatable<MatPair>
{
    public readonly string MatNeedsToExplainWhatThisRepresents;
    public readonly string MatNeedsToExplainThisToo;

    public MatPair(string matNeedsToExplainWhatThisRepresents,
        string matNeedsToExplainThisToo)
    {
        if (matNeedsToExplainWhatThisRepresents == null) throw new ArgumentNullException("matNeedsToExplainWhatThisRepresents");
        if (matNeedsToExplainThisToo == null) throw new ArgumentNullException("matNeedsToExplainThisToo");

        this.MatNeedsToExplainWhatThisRepresents = matNeedsToExplainWhatThisRepresents;
        this.MatNeedsToExplainThisToo = matNeedsToExplainThisToo;
    }

    [Obsolete]
    public override bool Equals(object obj)
    {
        return Equals(obj as MatPair);
    }

    public bool Equals(MatPair matPair)
    {
        return matPair != null
               && matPair.MatNeedsToExplainWhatThisRepresents == MatNeedsToExplainWhatThisRepresents
               && matPair.MatNeedsToExplainThisToo == MatNeedsToExplainThisToo;
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return MatNeedsToExplainWhatThisRepresents.GetHashCode() * 31
                ^ MatNeedsToExplainThisToo.GetHashCode();
        }
    }

    public override string ToString()
    {
        return "{" + MatNeedsToExplainWhatThisRepresents + ", "
            + MatNeedsToExplainThisToo + "}";
    }
}