HashSet my class doesn't contain issue

Question

I have a class that is similar to this:

public class Int16_2D
{
    public Int16 a, b;

    public override bool Equals(Object other)
    {
        return other is Int16_2D &&
        a == ((Int16_2D)other).a &&
        b == ((Int16_2D)other).b;
    }
}

This works in HashSet<Int16_2D>. However in Dictionary<Int16_2D, myType>, .ContainsKey returns false when it shouldn't. Am I missing something in my implementation of ==?

http://stackoverflow.com/questions/371328/why-is-it-important-to-override-gethashcode-when-equals-method-is-overriden-in-c — Andrew Barrett, Apr 14 '12 at 16:31
Note that you're not actually implementing `==`, `Equals()` is something different. — svick, Apr 14 '12 at 16:33

phoog · Answer 1 · 2012-04-14T17:16:31.747

For a class to work in a hash table or dictionary, you need to implement GetHashCode()! I have no idea why it's working in HashSet; I would guess it was just luck.

Note that it's dangerous to use mutable fields for calculating Equals or GetHashCode(). Why? Consider this:

var x = new Int16_2D { a = 1, b = 2 };
var set = new HashSet<Int16_2D> { x };

var y = new Int16_2D { a = 1, b = 2 };
Console.WriteLine(set.Contains(y));   // True

x.a = 3;
Console.WriteLine(set.Contains(y));   // False
Console.WriteLine(set.Contains(x));   // Also false!

In other words, when you set x.a = 3; you're changing x's hash code. But x's location in the hash table is based on its old hash code, so x is basically lost now. See this in action at http://ideone.com/QQw08

Also, as svick notes, implementing Equals does not implement ==. If you don't implement ==, the == operator will provide a reference comparison, so:

var x = new Int16_2d { a = 1, b = 2 };
var y = new Int16_2d { a = 1, b = 2 };
Console.WriteLine(x.Equals(y));             //True
Console.WriteLine(x == y);                  //False

In conclusion, you're better off making this an immutable type; since it's only 4 bytes long, I'd probably make it an immutable struct.

score 2 · Accepted Answer · answered Apr 14 '12 at 16:32

You need to override GetHashCode(). The fact that it works with HashSet<T> is probably just a lucky coincidence.

Both collections use the hash code obtained from GetHashCode to find a bucket (ie. list of objects), where the object should be placed. Then it searches that bucket to find the object, and uses Equals to ensure equality. This is what gives the nice fast lookup properties of the Dictionary and HashSet. However, this also means, that if GetHashCode is not overridden so that it corresponds to the types Equals method, you will not be able to find such an object in one of the collections.

You should, almost always, implement both GetHashCode and Equals, or none of them.

score 0 · Answer 3 · answered Apr 14 '12 at 16:31

0

You need to override GetHashCode as well for the dictionary to work.

answered Apr 14 '12 at 16:31

Femaref

60,705
7
138
176

score 0 · Answer 4 · answered Apr 14 '12 at 16:32

You have to override GetHashCode() as well - this goes hand in hand with overriding Equals. Dictionary is using GetHashCode() to determine what bin a value would fall into - only if a suitable item is found in that bin it checks on actual equality of the items.

HashSet my class doesn't contain issue

4 Answers4