hash collision and the HashMap

W

Wojtek

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....
 
C

Christian

Wojtek said:
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
 
P

Patricia Shanahan

Wojtek said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top