override GetHashCode

[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."
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/quickst...hashtable.aspx

Regards,
Bart

--
http://www.xenopz.com
"Stoyan" <St****@discussions.microsoft.com> wrote in message
news:FF**********************************@microsof t.com...

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

[Stoyan]

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[b]; // 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

"Bart De Boeck" wrote:

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/quickst...hashtable.aspx

Regards,
Bart

--
http://www.xenopz.com
"Stoyan" <St****@discussions.microsoft.com> wrote in message
news:FF**********************************@microsof t.com...

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

[Helge Jensen]

Stoyan wrote:

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.
--
Helge

[Stoyan]

Thank you Helge :))

Best Regards,
Stoyan

"Helge Jensen" wrote:

Stoyan wrote:

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.
--
Helge

[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
"Stoyan" <St****@discussions.microsoft.com> wrote in message
news:5B**********************************@microsof t.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[b]; // 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

"Bart De Boeck" wrote:

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/quickst...hashtable.aspx

Regards,
Bart

--
http://www.xenopz.com
"Stoyan" <St****@discussions.microsoft.com> wrote in message
news:FF**********************************@microsof t.com...

> 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