Java Reference
In-Depth Information
Efficiency of Hash Tables
The efficiency of our hash table depends on several factors. First, let's examine some
extreme cases. The worst-case run-time performance occurs if every item inserted into
the table has the same hash key. Everything will then be stored in a single linked list.
With
n
items, the find operation will require
O
(
n
) steps. Fortunately, if the items that
we insert are somewhat random, the probability that all of them will hash to the same
key is highly unlikely. In contrast, the best-case run-time performance occurs if every
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 exam-
ple, 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
ID number to a hash index.
22. Write an
outputHashTable( )
method for the
HashTable
class that outputs
every item stored in the hash table.
