Java Reference
In-Depth Information
Next we shall briefly examine more elaborate data structures that are capable of per-
forming find operations in fewer steps. However, a detailed treatment of these more
advanced data structures is beyond the scope of this chapter. The goal of this chapter is to
teach you the basic techniques for constructing and manipulating data structures based
on nodes and links (that is, nodes and references). The linked lists served as good exam-
ples for our discussion.
15.5
Hash Tables with Chaining
Seek, and ye shall find.
MATTHEW 7:7
hash table
hash map
A
hash table
or
hash map
is a data structure that efficiently stores and retrieves data
from memory. There are many ways to construct a hash table; in this section we will use
an array in combination with singly linked lists. In the previous section we saw that a
linked list generally requires linear, or
O
(
n
), steps to determine if a target is in the list. In
contrast, a hash table has the potential to execute a fixed number of steps to look up a tar-
get, regardless of the size of
n
. We saw that a constant-time lookup is written
O
(1). How-
ever, the hash table we will present may still require
n
steps, but such a case is unlikely.
An object is stored in a hash table by associating it with a
key
. Given the key, we can
retrieve the object. Ideally, the key is unique to each object. If the object has no intrin-
sically unique key, then we can use a
hash function
to compute one. In most cases the
hash function computes a number.
For example, let's use a hash table to store a dictionary of words. Such a hash table
might be useful to make a spell checker—words missing from the hash table might not be
spelled correctly. We will construct the hash table with a fixed array in which each array
element references a linked list. The key computed by the hash function will map to the
index of the array. The actual data will be stored in a linked list at the hash value's index.
Display 15.33 illustrates the idea with a fixed array of ten entries. Initially each entry of
the array
hashArray
contains a reference to an empty singly linked list. First we add the
word
"cat"
, which has been assigned the key or hash value of 2 (we'll show how this was
computed shortly). Next we add
"dog"
and
"bird"
, which are assigned hash values of 4
and 7, respectively. Each of these strings is inserted as the head of the linked list using the
hash value as the index in the array. Finally, we add
"turtle"
, which also has a hash of 2.
Since
"cat"
is already stored at index 2, we now have a
collision
. Both
"turtle"
and
"cat"
map to the same index in the array. When this occurs in a hash table with
chain-
ing
, we simply insert the new node onto the existing linked list. In our example there are
now two nodes at index 2:
"turtle"
and
"cat"
.
To retrieve a value from the hash table, we first compute the hash value of the target.
Next we search the linked list that is stored at
hashArray[hashValue]
for the target,
using an iterator to sequentially search the linked list. If the target is not found in this
linked list, then the target is not stored in the hash table. If the size of the linked list is
small then the retrieval process will be quick.
hash function
collision
chaining
