Java Reference
In-Depth Information
item inserted into the table has a different hash key. This means that there will be no
collisions, so the find operation will require constant, or
O
(1), steps because the target
will always be the first node in the linked list.
We can decrease the chance of collisions by using a better hash function. For
example, the simple hash function that sums each letter of a string ignores the ordering
of the letters. The words
"rat"
and
"tar"
would hash to the same value. A better hash
function for a string
s
is to multiply each letter by an increasing weight depending
upon the position in the word. For example,
int
hash = 0;
for
(int i = 0; i < s.length( ); i++)
{
hash = 31 * hash + s.charAt(i);
}
Another way to decrease the chance of collisions is by making the hash table bigger.
For example, if the hash table array stored 10,000 entries but we are only inserting
1,000 items, then the probability of a collision is much smaller than if the hash table
array stored only 1,000 entries. However, a drawback to creating an extremely large
hash table array is wasted memory. If only 1,000 items are inserted into the 10,000-entry
hash table, then at least 9,000 memory locations will go unused. This illustrates the
time-space tradeoff
. It is usually possible to increase run-time performance at the
expense of memory space, and vice versa.
time-space
tradeoff
Self-Test Exercises
21. Suppose that every student in your university is assigned a unique nine-digit
ID number. You would like to create a hash table that indexes ID numbers to
an object representing a student. The hash table has a size of
N,
where
N
has
less than nine digits. Describe a simple hash function that you can use to map
from a ID number to a hash index.
22. Write an
outputHashTable( )
method for the
HashTable
class that outputs
every item stored in the hash table.
15.6
Sets
There are two classes in good society in England. The equestrian classes and
the neurotic classes.
GEORGE BERNARD SHAW,
Heartbreak House
A set is a collection of elements in which order and multiplicity are ignored. Many
problems in computer science can be solved with the aid of a set data structure.
A variation on linked lists is a straightforward way to implement a set. In this
implementation, the items in each set are stored using a singly linked list. The
data
