[Mono-list] mcs compiles on linux. Now what?

[Piers Haken]

Yes, Object.GetHashCode() must be based on immutable instance values
(otherwise you lose objects in hashtables). But the kicker is that if
Object.Equals() returns true then the two object's GetHashCode()s _must_
be the same !!!

some snippits from MSDN:

"A hash function should be based on an immutable data member. The hash
function should return exactly the same value regardless of any changes
that are made to the object. Basing the hash function on a mutable data
member can cause serious problems, including never being able to access
that object in a hash table."

"Furthermore, these methods [Equals, GetHashCode] must produce the same
results when called with the same parameters while the key exists in the
Hashtable.  Key objects must be immutable as long as they are used as
keys in the Hashtable."

So, either:
1) GetHashCode() returns a const, or
2) Equals() is based on immutable instance values.

Piers.

PS.There was a discussion about this on the DOTNET mailing list a while
ago. Here's the 'official' reply:

------
From: Brad Abrams [brada@MICROSOFT.COM]
To: DOTNET@DISCUSS.DEVELOP.COM
Subject:      Re: GetHashCode - is it really this hard

This is a very interesting thread... clearly we need to do a better job
with the documentation.  As someone mentioned earlier we did argue long
and hard about this, unfortunately the outcome was not clear captured in
the docs.  

The problem seems have been well described here, but just to bring it
home the issue with hashcodes that can change over the lifetime of the
instance is using them in a hashtable such as: Changeable o = ...
table.Add (o, "value"); o.Change(); //Then we will not be able to look
up the value.. This will always be false table[o] == "value"

Of course, the other issue is that it is very important that your
Equals() implementation be based off the same instance data as your
GetHashCode implementation so they stay in sync.  A meaningful Equals is
often based off mutable data.  

So, if equals is based on mutable data and gethashcode is based on what
Equals uses then GetHashCode is also based on mutable data.  

When you add a value to Hashtable you have to be aware of this issue and
not change your keys.  People should not use bad hashcodes (such as
returning a constant) to "workaround" this problem.

As was pointed out, we have a bug in our docs for V1 that says that
GetHashCode must be based on immutable state.  That is wrong and I'll
get it fixed (post RTM) as soon as possible.  In the meantime, you can
look at the docs in the ECMA submission.

Thanks

..brad





-----Original Message-----
From: Radek Doulík [mailto:rodo@ximian.com]
Sent: Thursday, March 07, 2002 4:14 PM
To: Dan Lewis
Cc: Paolo Molaro; mono-list@ximian.com
Subject: Re: [Mono-list] mcs compiles on linux. Now what?


On Čt, 2002-03-07 at 17:31, Dan Lewis wrote:
>  --- Paolo Molaro <lupus@ximian.com> wrote:
> > System.Collections.Hashtable::Find() takes more than 40% of the
compile
> > This suggest we may be using bad hash functions or that the
hashtable
> > doesn't resize correctly, since the average compare per lookup is
> > greater than 5 (it should be about 1). So check the sources for
> > bad GetHashCode() implementations, create tests to check that the
> > hashtable behaves correctly when expanding.
> 
> I seem to remember the default GetHashCode() implementation returns 0
(a
> perfect hash function -- if there's only one key :). Would it be
possible to
> implement Object.GetHashCode() as an internal call? (a shallow hash
based on
> the object bits).

Which bits do you mean? As a temporary solution we could have static int
counter in Object class and instance int variable, which will be set by
counter value in constructor? Like this:

class Object {
	static int counter = 0;
	private int key;

	public Object ()
	{
		key = counter;
		counter ++;
	}

	public virtual int GetHashCode ()
	{
		return key;
	}
}

Which could serve before we could find something better. Actually I am
not sure, how this works for boxed objects, maybe we cannot have
instance variable in Object because boxing?

Cheers
Radek



_______________________________________________
Mono-list maillist  -  Mono-list@ximian.com
http://lists.ximian.com/mailman/listinfo/mono-list