Java Reference
In-Depth Information
Next we shall briefly examine more elaborate data structures that are capable of
performing 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
examples for our discussion.
15.5
Hash Tables with Chaining
Seek, and ye shall find.
MATTHEW 7:7
hash table
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 target, regardless of the size of
n
. We saw that a constant-time lookup is written
O
(1). However, 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
intrinsically unique key, then we can use a
hash function
to compute one. In most
cases, the hash function computes a number.
For example, let us 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 10 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 will 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. Because
"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
chaining
, 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"
.
hash map
hash function
collision
chaining
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.
