Java Reference
In-Depth Information
Maps
key
object
key
object
key
object
key
object
hash code
determines
location to search
key
object
keys
compared
get(objectKey)
The key is used to generate a
hash code, which determines where in
memory the key/object pair is stored.
Retrieving an object requires a key to be
supplied. A hash code is generated and the
key (or keys) at the location determined by
the hash code is compared with the
supplied key.
key
object
A key can be any kind of object that you want to use to reference the object stored. Because the key has
to uniquely identify the object, all the keys in a map must be different. To put this in context let's take
an example. Suppose you were creating a program to provide an address book. You might store all the
details of each person - their name, address, phone number, or whatever - in a single object of type
Entry
perhaps, and store a reference to the object in a map. The key is the mechanism for retrieving
objects, so assuming that all names are different, the name of the person would be a natural choice for
the key. Thus the entries in the map in this case would be
Name
/
Entry
pairs. You would supply a
Name
object as the key, and get back the
Entry
object corresponding to the key. You might well have
another map in this application where entries were keyed on the phone number. Then you could
retrieve an entry corresponding to a given number. Of course, in practice, names are not unique -
hence the invention of such delightful attachments to the person as social security numbers.
Hashing
Where a key/object pair is stored in a map is determined from the key by a process known as
hashing
.
Hashing processes the key object to produce an integer value called a
hash code
. The
hashCode()
method
that is defined in the
Object
class produces a hash code of type
int
for an object. The hash code is typically
used as an offset from the start of the memory that has been allocated within the map, to determine the
location where the key/object pair is to be stored. Ideally the hashing process should result in values that are
uniformly distributed within a given range, and every key should produce a different hash code. In general,
this may not be the case, but there are ways around this so it is not a problem. We will look at keys and hash
codes in a little more detail when we discuss using maps later in this chapter.
Now let's look at how we can move through a collection.
Iterators
In the
LinkedList
class that we developed in Chapter 6 you might have thought that the mechanism
for getting the objects from the list was a little cumbersome. It was necessary to obtain the first element
by using one method,
getFirst()
, and successive elements by another method,
getNext()
. This
makes the first element in a list a 'special case' so processing the elements has to take account of this and
is a little more complicated than perhaps it needs to be.
