override GetHashCode

[Guest]

Hi All,
I don't understand very well this part of MSDN:
"Derived classes that override GetHashCode must also override Equals to
guarantee that two objects considered equal have the same hash code;
otherwise, Hashtable might not work correctly."
Does any one know, why we must also override Equals,
Please give my an example

Thanks,
Stoyan

 

[Bart De Boeck]

Hi Stoyan,

The Hashtable type requires that if two objects are equal, they must have
the same hash code value : when a key/value pair is added to a Hashtable,
the Hashtable uses the hash code of the key to determine the bucket that
stores the key. The bucket is then searched for a key which Equals the
given key (there might be more than one key in the bucket). If you wonder
why Equals is needed to find the key in the bucket : hashes can collide
(i.e. two different objects might generate the same hash - a hash
collision).
http://samples.gotdotnet.com/quickstart/howto/doc/hashtable.aspx

Regards,
Bart

 

[Guest]

Hi Bart,
I understand very well, if I override Equals, I must override and
GetHashCode() method.
but I don't understand for example:
I have two classes:
public class SomeType
{
public override int GetHashCode()
{ return 1;}
}
public class AnotherType
{
public override int GetHashCode()
{ return 1;}
}

SomeType a = new SomeType();
AnotherType b = new AnotherType();
Hashtable tbl = new Hashtable();
tbl.Add(a,a);
tbl.Add(b,b);


object a = tbl[a]; // this object is correct (SomeType)
object b = tbl; // this object is correct (AnotherType)

In my case, why must also override Equals()?
I know, if hashcodes are different, Hashtable working better(faster)

Regards,
Stoyan

 

[Helge Jensen]

Hi All,
I don't understand very well this part of MSDN:
"Derived classes that override GetHashCode must also override Equals to
guarantee that two objects considered equal have the same hash code;
otherwise, Hashtable might not work correctly."

For hashtables to operate, the following must be true:

Equals(x,y) -> x.GetHashCode() == y.GetHashCode()
x.GetHashCode() != y.GetHashCode() -> !Equals(x,y)

This effectivly joins the partitioning that Equals imposes on objects
into larger sets, which rather neatly are numbered..., ready to put in
an index'ed array. Cunning thing, hashing

The above makes a constraint on how you can re-define GetHashCode
without redefining Equals.

Stricly speaking, if you use (keep the default) reference-equality the
only constraint on GetHashCode is that it is consistent:

x == y -> x.GetHashCode(x) == y.GetHashCode(y).

Does any one know, why we must also override Equals,

Well, strictly speaking... it's not required, but...

Please give my an example

In short, Hashtables usually does linear comparison, using Equals, of
the lookup key with every entry with the same hash-value modulo the size
of the hashtable. This also shows why choosing a hash-function with good
distribution is very important.

For hashing to be *usefull*, one usually calculates the hashcode on the
basis of the *value* of an object, not the reference, and *that's* why
you need to override Equals.

A minimalistic example:

class Foo {
public readonly int X;
public Foo(int x) { this.X = x; }
public override int GetHashCode() { return X; }
}

If you were to insert Foo's into a hashtable:

IDictionary d = new Hashtable();
Foo foo = new Foo(0);
d.Add(foo, 0);

You would (probably) expect :

Foo foo2 = new Foo(0);
object x = d[foo];
object y = d[foo2];

to both return a boxed 0, but they *dont* foo.GetHashCode() == 0 and
foo2.GetHashCode() == 0, but !Equals(foo, foo2).

So you need to redefine Equals:

public override bool Equals(object other) {
return ((Foo)other).X == X;
}

To do comparison by value, instead of reference.

 

[Guest]

Thank you Helge )

Best Regards,
Stoyan

Hi All,
I don't understand very well this part of MSDN:
"Derived classes that override GetHashCode must also override Equals to
guarantee that two objects considered equal have the same hash code;
otherwise, Hashtable might not work correctly."

For hashtables to operate, the following must be true:

Equals(x,y) -> x.GetHashCode() == y.GetHashCode()
x.GetHashCode() != y.GetHashCode() -> !Equals(x,y)

This effectivly joins the partitioning that Equals imposes on objects
into larger sets, which rather neatly are numbered..., ready to put in
an index'ed array. Cunning thing, hashing

The above makes a constraint on how you can re-define GetHashCode
without redefining Equals.

Stricly speaking, if you use (keep the default) reference-equality the
only constraint on GetHashCode is that it is consistent:

x == y -> x.GetHashCode(x) == y.GetHashCode(y).

Does any one know, why we must also override Equals,

Well, strictly speaking... it's not required, but...

Please give my an example

In short, Hashtables usually does linear comparison, using Equals, of
the lookup key with every entry with the same hash-value modulo the size
of the hashtable. This also shows why choosing a hash-function with good
distribution is very important.

For hashing to be *usefull*, one usually calculates the hashcode on the
basis of the *value* of an object, not the reference, and *that's* why
you need to override Equals.

A minimalistic example:

class Foo {
public readonly int X;
public Foo(int x) { this.X = x; }
public override int GetHashCode() { return X; }
}

If you were to insert Foo's into a hashtable:

IDictionary d = new Hashtable();
Foo foo = new Foo(0);
d.Add(foo, 0);

You would (probably) expect :

Foo foo2 = new Foo(0);
object x = d[foo];
object y = d[foo2];

to both return a boxed 0, but they *dont* foo.GetHashCode() == 0 and
foo2.GetHashCode() == 0, but !Equals(foo, foo2).

So you need to redefine Equals:

public override bool Equals(object other) {
return ((Foo)other).X == X;
}

To do comparison by value, instead of reference.

 

[Bart De Boeck]

as far as I know, one of the reasons that you should override Equals is that
might require that different objects (different references of the same type)
can be equal
so, based on your example :

public class SomeType
{
public override int GetHashCode()
{ return 1;}

int _field = 3;
}

if two instances of SomeType are equal (cause _field equals), you should
override Equals


--
http://www.xenopz.com

Hi Bart,
I understand very well, if I override Equals, I must override and
GetHashCode() method.
but I don't understand for example:
I have two classes:
public class SomeType
{
public override int GetHashCode()
{ return 1;}
}
public class AnotherType
{
public override int GetHashCode()
{ return 1;}
}

SomeType a = new SomeType();
AnotherType b = new AnotherType();
Hashtable tbl = new Hashtable();
tbl.Add(a,a);
tbl.Add(b,b);


object a = tbl[a]; // this object is correct (SomeType)
object b = tbl; // this object is correct (AnotherType)

In my case, why must also override Equals()?
I know, if hashcodes are different, Hashtable working better(faster)

Regards,
Stoyan

Hi Stoyan,

The Hashtable type requires that if two objects are equal, they must
have
the same hash code value : when a key/value pair is added to a Hashtable,
the Hashtable uses the hash code of the key to determine the bucket that
stores the key. The bucket is then searched for a key which Equals the
given key (there might be more than one key in the bucket). If you wonder
why Equals is needed to find the key in the bucket : hashes can collide
(i.e. two different objects might generate the same hash - a hash
collision).
http://samples.gotdotnet.com/quickstart/howto/doc/hashtable.aspx

Regards,
Bart