Re: Generate hash code

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

The hashcode is not the same as the key; the hashcode is just used to
partition the items (fairly arbitrarily) - so that it can jump to a subset
of the larger list before doing any real work. This is why IEqualityComparer
requests both an equality method and a hash method.

I've never written a hashtable from scratch, but I *believe* it tends to
work something like the following:

* The hashtable has a number of buckets; lets say 20 (although this is often
dynamic based on the amount of data contained)
* When adding items, it gets the hashcode (lets say it return 342545), and
then takes the mod (remainder on division) of this with the bucket count to
choose a bucket (bucket 5 in this case)
* When you query the hashtable, it
1: gets the hashcode of your argument and does the same operation to
pick the bucket to look within
2: scans the contents of this bucket (a much shorter list), possibly
checking Equals, or possibly first checking the hash of each item and then
checking Equals if the hash matched (i.e. something in bucket 5 could have a
hash of 342545, or it could have a hash of 25)

This raises another implementation point:

If 2 instances share a hash-code, it is *not* necessary for them to count as
equal (via Equals)
HOWEVER: if two instances *should* count as equal, then the hash codes
should be identical

Of course, if you use any of the inbuilt primatives (int, string, etc) for
your key you will be pretty safe

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: Hashing: "blair" == "brainlessness" !! !!
    ... >>what was the greatest number of string which ever produced ... >> bearing in mind that unless they're the same length, Equals doesn't even ... Each bucket has a portion of the ... "roughly" the right hashcode. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: equals and hashCode
    ... >> I understand the purpose of overriding equals() in comparing the data of ... >> hashCode() is a little less clear. ... >> "Equal objects must produce the same hash code as long as they are equal, ...
    (comp.lang.java.programmer)
  • Re: why in class Boolean, hashcode() of "true" is 1231 and of "false" is 1237?
    ... correlations between two hash values, they will remain in the output of this in some transformed and subtler form. ... Actually, since the identities of objects used as keys should not change, there really should have been some notion of immutable objects in Java from the beginning, and equals and hashCode only applicable to those. ...
    (comp.lang.java.programmer)
  • Re: hashCode and equals (again)
    ... Roedy's, etc.), but have not been able to get a good grasp of hashCode ... I thought that it made sense to make an equals method ... In general there will be objects that have the same hash code ...
    (comp.lang.java.programmer)