Java Reference
In-Depth Information
An entry in the table that is used to store key/value pairs is called a
bucket
. The hashcode produced from
a key selects a particular bucket in which the key/value pair should be stored. This is illustrated in
Figure
Note that, although every key must be unique, each key doesn't have to result in a unique hashcode.
When two or more keys produce the same hash value, it's called a
collision
. A
HashMap<>
object deals with
collisions by storing all the key/object pairs that have the same hash value in a linked list. If this occurs of-
ten, it is obviously going to slow down the process of storing and retrieving data. Retrieving an object that
resulted in a collision when it was stored is a two-stage process. The key is hashed to find the location where
the key/object pair should be. The linked list then has to be searched to sort out the key you are searching
on from all the others that have the same hash value. There is therefore a strong incentive to minimize col-
lisions, and the price of reducing the possibility of collisions in a hash table is having plenty of empty space
in the table.
The
Object
class defines the
hashCode()
method so any object can be used as a key and it hashes by
default. The method as it is implemented in
Object
in Java, however, isn't a panacea. Because it usually
uses the memory address where an object is stored to produce the hash value, distinct objects always pro-
duce different hash values. In one sense this is a plus, because the more likely it is that a unique hash value
is produced for each key, the more efficient the operation of the hash map is going to be. The downside is
that different objects that have identical data produce different hash values, so you can't compare them.
This becomes a nuisance if you use the default
hashCode()
method for objects that you're using as keys.
In this case, an object stored in a hash map can never be retrieved using a different key object instance, even
though that key object may be identical in all other respects. Yet this is precisely what you want to do in
many cases.
Consider an application such as a simple address book. You might store map entries keyed on the names
of the people to whom the entries relate, and you would want to search the map based on a name that was
entered from the keyboard. However, the object representing the newly entered name is inevitably going to
be distinct from that used as a key for the entry. Using the former, you won't be able to find the entry cor-
responding to the name.
