Java Reference
In-Depth Information
B ecause searching databases is such a widespread application of computers, the dictionary is an
important abstract data type. The implementations that we discussed in the previous chapter are
fine for certain applications, but for others they are inadequate. For example, if locating data is
critical, even an O(log n ) search can be too slow. Such is the case for the emergency telephone
(911) system. If you call 911 from a land line, your telephone number is the key in a search of a
dictionary of street addresses. Obviously, you want this search to find your location immediately!
This chapter introduces a technique called hashing that ideally can result in O(1) search
times. We will complete our exploration of this topic in the next chapter. Hashing can be an
excellent choice for implementing a dictionary when searching is the primary task. But as good
as hashing can be, it is not always appropriate. For example, hashing cannot provide a traversal
of the search keys in sorted order. Later in this topic we will consider other implementations of
the ADT dictionary.
What Is Hashing?
21.1
A place for everything; everything in its place. Do you spend time looking for your keys in the
morning? Or do you know exactly where they are? Some of us spend too much time sequentially
searching our unsorted possessions. Others have a special place for things and know just where to
find each one.
An array can provide a place for a dictionary's entries. Admittedly, arrays have their disad-
vantages, but you can access any entry in an array directly if you know its index. No other array
entry need be involved. Hashing is a technique that determines this index using only an entry's
search key, without searching. The array itself is called a hash table .
A hash function takes a search key and produces the integer index of an element in the hash
table. This array element is where you would either store or look for the search key's associated
value. For example, the 911 emergency system can take your telephone number, convert it to a
suitable integer i , and store a reference to your street address in the array element a[i] . We say
that the telephone number—that is, the search key— maps , or hashes , to the index i . This index
is called a hash index. Sometimes we will say that the search key maps, or hashes, into the table
location at the index i .
VideoNote
Hashing
21.2
Ideal hashing. Consider an emergency system for a small town where everyone's telephone num-
ber begins with 555. Let the hash function h convert a telephone number to its last four digits. For
example,
h (555-1214) = 1214
If hashTable is the hash table, we would place a reference to the street address associated with this
telephone number in hashTable[1214] , as Figure 21-1 illustrates. If the cost of evaluating the hash
function is low, adding an entry to the array hashTable is an O(1) operation.
 
 
Search WWH ::




Custom Search