Java Reference
In-Depth Information
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 will not be
able to find the entry corresponding to the name.
The solution to this problem is somehow to make a hash of the instance variables of the object. Then,
by comparing the values of the data members of the new name object with those for the name objects
used as keys in the hash map, you'll be able to make a match.
Using Your Own Class Objects as Keys
For objects of one of your own classes to be usable as keys in a hash table, you must override the
equals()
method of the
Object
class. In its default form,
equals()
accepts an object of the same class as an
argument and returns a
boolean
value. The
equals()
method is used by methods in the
HashMap
class to
determine when two keys are equal, so, in order to enable the changes discussed in the previous section, your
version of this method should return
true
when two different objects contain identical data values.
You can also override the default
hashCode()
method, which returns the hash value for the object as
type
int
. The
hashCode()
method is used to generate the
int
value that is the key. Your
hashCode()
method should produce hash codes that are reasonably uniform over the possible range
of keys and generally unique for each key.
Generating Hash Codes
The various techniques for generating hash codes form a big topic, and we can only scratch the surface
here. How you write the
hashCode()
method for your class is up to you, but it needs to meet certain
requirements if it is to be effective. You should aim to return a number of type
int
for an object that
has a strong probability of being unique to that object, and the numbers that you produce for several
different objects should be as widely distributed across the range of
int
values as possible.
To achieve the uniqueness, you will typically want to combine the values of all the data members in an
object to produce the hash code, so the first step is to produce an integer corresponding to each data
member. You must then combine these integers to generate the return value that will be the hash code
for the object. One technique you can use to do this is to multiply each of the integers corresponding to
the data members by a different prime number and then sum the results. This should produce a
reasonable distribution of values that have a good probability of being different for different objects. It
doesn't matter which prime numbers you use as multipliers, as long as:
They aren't so large as to cause the result to fall outside the range of type
int
❑
You use a different one for each data member
❑
So how do you get from a data member of a class to an integer? Generating an integer for data members
of type
String
is easy: you just call the
hashCode()
method for the member. This has been
implemented in the
String
class to produce good hash code values that will be the same for identical
strings (take a look at the source code if you want to see how). You can use integer data members as
they are, but floating point data members need a bit of judgment. If they have a small range in integer
terms, you need to multiply them by a value that's going to result in a unique integer when they are cast
to type
int
. If they have a very large range in integer terms you may need to scale them down.
