hash collision and the HashMap

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

 

[Christian]

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

 

[Wojtek]

Christian wrote :

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

Ah ha. A light dawns...

Thanks

 

[Lew]

Christian wrote :

Ah ha. A light dawns...

toString() does not figure into the collision resolution.

-- Lew

 

[Patricia Shanahan]

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