Java Reference
In-Depth Information
FIGURE 21-1
A hash function indexes its hash table
h
(555-1214)
150 Main Street
Hash table
To later find the street address associated with the number 555-1214, we once again com-
pute
h
(555-1214) and use the result to index
hashTable
. Thus, from
hashTable[1214]
, we get
the desired street address. This operation also is O(1). Notice that we did not search the array
hashTable
.
21.3
Let's summarize what we know so far by writing simple algorithms for the dictionary operations
that add or retrieve entries:
Algorithm
add(key, value)
index = h(key)
hashTable[index] = value
Algorithm
getValue(key)
index = h(key)
return
hashTable[index]
Will these algorithms always work? We can make them work if we know all the possible
search keys. In this example, the search keys range from 555-0000 to 555-9999, so the hash func-
tion will produce indices from 0 to 9999. If the array
hashTable
has 10,000 elements, each tele-
phone number will correspond to one unique element in
hashTable
. That element references the
appropriate street address. This scenario describes the ideal case for hashing, and the hash function
here is a
perfect hash function
.
