hash collision and the HashMap

Thread view:

Wojtek - 26 Mar 2007 20:40 GMT

If I have a HashMap<String,MyObject>, then the HashMap uses the hash of
the String to place MyObject in its internal storage. If the hash for a
String is the same as another String, then what?

I assume that the hash collision mechanism uses toString() to resolve
which String you are specifying.

OK so far.

Now if I have a HashMap<MyKey,MyObject), then the HashMap uses the hash
of MyKey. What if this also produces a collision? If the toString() is
used, and I have not provided a MyKey specific toString(), then the
default toString() is the class name plus the hash.

In that case I over-write the previous MyKey entry.

Or am I missing something....

Signature

Wojtek :-)

Reply to this Message

Christian - 26 Mar 2007 20:54 GMT

Wojtek schrieb:

> Or am I missing something....

indeed..

a Hashmap rather maps the hashcode of the key to a list of key- Value
tuples ..

it then uses the equals method in that list to find what object you are
really searching

so hashmap is kind of an array of lists.. the hashcode helps you to find
the right list in the array then equals is used to find the right key in
the list which has the mapped object in its tuple.

Christian

Reply to this Message

Wojtek - 26 Mar 2007 21:07 GMT

Christian wrote :

> Wojtek schrieb:
>
>> Or am I missing something....
>>
> it then uses the equals method in that list to find what object you are
> really searching

Ah ha. A light dawns...

Thanks

Signature

Wojtek :-)

Reply to this Message

Lew - 26 Mar 2007 22:47 GMT

> Christian wrote :
>> Wojtek schrieb:
[quoted text clipped - 5 lines]
>
> Ah ha. A light dawns...

toString() does not figure into the collision resolution.

-- Lew

Reply to this Message

Patricia Shanahan - 26 Mar 2007 23:14 GMT

> If I have a HashMap<String,MyObject>, then the HashMap uses the hash of
> the String to place MyObject in its internal storage. If the hash for a
> String is the same as another String, then what?

There are several ways of dealing with collisions in hashing structures.
The one the Java developers choose to use for HashMap is to have buckets
that can each contain multiple entries.

Equal hash code entries go in the same bucket, just as they would if
they had different hash codes that mapped to the same bucket.

Each bucket contains zero or more entries. Each entry contains both key
and value, so that equals() can be used to distinguish unequal keys with
equal hash codes.

> I assume that the hash collision mechanism uses toString() to resolve
> which String you are specifying.

You lost me at this point. Why do you think toString() would be any use
for hash collision resolution?

In any case, take a look in your JDK install directory. There should be
a file there called "src.zip". Read java/util/HashMap.java in that zip.

Patricia

Reply to this Message

hash collision and the HashMap

Free Magazines