Re: Hashtables

On Mon, 12 Sep 2005 20:10:32 +0100, Thomas Hawtin wrote:

> JTMOBAP wrote:
>> For any given hashtable, what is the maximum number of collisions in
>> buckets?
>
> The number of entries in the table. Why do you ask?

OK, to be a bit more helpful...

Each hashtable determines what bucket to put an Object in by executing the
method Object.hashCode() or a method that overrides it. This method
returns an integer, but there is no reason at all that it couldn't return
exactly the same integer for everything you put in the hashtable. The
contract for hashCode() only requires that for two Objects that are
equal() it return the same value.

In this case every Object added to the hashtable would end up in the same
bucket.

This isn't the only case in which this happens though.

Every Hashtable has a capacity. This is the number of buckets in the
Hashtable. This capacity is really never the size of
Integer.MAX_VALUE, so some mapping must be made from the hashCode() of
your object to the location in the Hashtable. So maybe all your Objects
just happen to end up in the same bucket.

The more objects in the table and the better the implementation of
hashCode the less likely this is.

--
Kenneth P. Turvey <kt-usenet@xxxxxxxxxxxxxxxxxx>

http://kt.squeakydolphin.com (not much there yet)
Phone: (314) 255-2199
Jabber IM: kpturvey@xxxxxxxxxx

.

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: 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)
  • 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: about Equals and GetHashCode
    ... GetHashCode() does not guarantee uniqueness - for starters, ... the hashcode - i.e. each item goes into the bucket with index ... calculate the modulo of that hashcode - we now know which bucket to ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: need clarification on HashMap storage-retrieval
    ... mapping into a hashmap. ... hashcode and equals come into play. ... 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? ...
    (comp.lang.java.programmer)