Re: about Equals and GetHashCode

Tech Tip: Click here to run a free scan for Windows Errors and optimize PC performance

No; GetHashCode() does not guarantee uniqueness - for starters, it is
an Int32 - it would take a trivial example involving Int64 and i++ to
show that they aren't unique.

The point is that if a.GetHashCode() and b.GetHashCode() are
*different* then a nd b definitely aren't the same. If the hashcodes
are the same, then you need to check a and b. This provides an
efficient way of narrowing down the amount of things we actually need
to check, by first excluding everything that doesn't have the same
hashcode,
leaving a much smaller set.
Further, advanced structures such as hash-tables can use the hash-code
to create "buckets" - so, for example, based on the number of items,
it might decide to split it into 20 "buckets" by taking the modulo of
the hashcode - i.e. each item goes into the bucket with index
GetHashCode() % bucketCount.

Then, to find a given item, it can do:
* get the haschode of the search key
* calculate the modulo of that hashcode - we now know which bucket to
look in [down to 1/20th of the data already]
* look in that bucket for everything with the correct hashcode
[probably down to 1 or 2 items now]
* perform the actual Equals between the search key and the stored
items, to find the one we want

So: GetHashCode() is very rarely used without Equals() [although
Equals() can be used without GetHashCode()]; it is definitely very
important, and underpins all the fast lookups from Dictionary<,>, etc.
Linear search (testing each item) would be very, very slow on a long
list.

Marc
.

Relevant Pages

  • Re: need clarification on HashMap storage-retrieval
    ... keys map to the same hashcode, both apple and orange objects will be ... Do both key and value sit in a bucket or is it only the value? ... Orange have implemented hashCode and equals, ...
    (comp.lang.java.programmer)
  • Re: Generic GetHashCode method
    ... one overrides the GetHashCode() method to provide the hashcode ... public string Name} ... Hash codes are used to insert and retrieve values into and from data ...
    (microsoft.public.dotnet.general)
  • Re: Detecting changes to any object
    ... The "hash-method" seems to work fine (In my tests, ... > instance will always have the same GetHashCode() as long as it lives - ... > wont be sufficient... ... > Danger is that hashcodes are reused, so I risk that an objects hashcode ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Problem with Dictionary.Keys enumerator returning invalid keys
    ... Well, if an object is stored as a key, then GetHashCode is called on it. ... Then, the reference is put into a bucket, and then if there is more than one ... might have added a key with a custom implementation of Equals/GetHashCode ... foreach loops, such that the Key returned in the foreach is not ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Generate hash code
    ... The hashcode is not the same as the key; the hashcode is just used to ... requests both an equality method and a hash method. ... then takes the mod of this with the bucket count to ... checking Equals, or possibly first checking the hash of each item and then ...
    (microsoft.public.dotnet.languages.csharp)