Java Reference
In-Depth Information
/
**
SearchinhashtableHTfortherecordwithkeyk
*
/
EhashSearch(Keyk){
inthome; //Homepositionfork
intpos=home=h(k);//Initialposition
for(inti=1;(HT[pos]!=null)&&
(HT[pos].key().compareTo(k)!=0);i++)
pos=(home+p(k,i))%M; //Nextprobeposition
if(HT[pos]==null)returnnull;//Keynotinhashtable
elsereturnHT[pos].value(); //Foundit
}
Figure9.7
Search method for a dictionary implemented by a hash table.
number of records stored, and refuse to insert into a table that has only one free
slot.
The discussion on bucket hashing presented a simple method of collision reso-
lution. If the home position for the record is occupied, then move down the bucket
until a free slot is found. This is an example of a technique for collision resolution
known as linear probing. The probe function for simple linear probing is
p(K;i) = i:
That is, the ith offset on the probe sequence is just i, meaning that the ith step is
simply to move down i slots in the table.
Once the bottom of the table is reached, the probe sequence wraps around to
the beginning of the table. Linear probing has the virtue that all slots in the table
will be candidates for inserting a new record before the probe sequence returns to
the home position.
While linear probing is probably the first idea that comes to mind when consid-
ering collision resolution policies, it is not the only one possible. Probe function
p
allows us many options for how to do collision resolution. In fact, linear probing is
one of the worst collision resolution methods. The main problem is illustrated by
Figure 9.8. Here, we see a hash table of ten slots used to store four-digit numbers,
with hash function h(K) = K mod 10. In Figure 9.8(a), five numbers have been
placed in the table, leaving five slots remaining.
The ideal behavior for a collision resolution mechanism is that each empty slot
in the table will have equal probability of receiving the next record inserted (assum-
ing that every slot in the table has equal probability of being hashed to initially). In
this example, assume that the hash function gives each slot (roughly) equal proba-
bility of being the home position for the next key. However, consider what happens
to the next record if its key has its home position at slot 0. Linear probing will
send the record to slot 2. The same will happen to records whose home position
is at slot 1. A record with home position at slot 2 will remain in slot 2. Thus, the
probability is 3/10 that the next record inserted will end up in slot 2. In a similar
