Java Reference
In-Depth Information
/
**
InsertrecordrwithkeykintoHT
*
/
voidhashInsert(Keyk,Er){
inthome; //Homepositionforr
intpos=home=h(k); //Initialposition
for(inti=1;HT[pos]!=null;i++){
pos=(home+p(k,i))%M; //Nextpobeslot
assertHT[pos].key().compareTo(k)!=0:
"Duplicatesnotallowed";
}
HT[pos]=newKVpair<Key,E>(k,r);//InsertR
}
Figure9.6
Insertion method for a dictionary implemented by a hash table.
Linear Probing
We now turn to the most commonly used form of hashing: closed hashing with no
bucketing, and a collision resolution policy that can potentially use any slot in the
hash table.
During insertion, the goal of collision resolution is to find a free slot in the hash
table when the home position for the record is already occupied. We can view any
collision resolution method as generating a sequence of hash table slots that can
potentially hold the record. The first slot in the sequence will be the home position
for the key. If the home position is occupied, then the collision resolution policy
goes to the next slot in the sequence. If this is occupied as well, then another slot
must be found, and so on. This sequence of slots is known as the probe sequence,
and it is generated by some probe function that we will call p. The insert function
is shown in Figure 9.6.
Method
hashInsert
first checks to see if the home slot for the key is empty.
If the home slot is occupied, then we use the probe function, p(k, i) to locate a free
slot in the table. Function p has two parameters, the key k and a count i for where
in the probe sequence we wish to be. That is, to get the first position in the probe
sequence after the home slot for key K, we call p(K, 1). For the next slot in the
probe sequence, call p(K, 2). Note that the probe function returns an offset from
the original home position, rather than a slot in the hash table. Thus, the
for
loop
in
hashInsert
is computing positions in the table at each iteration by adding
the value returned from the probe function to the home position. The ith call to
p
returns the ith offset to be used.
Searching in a hash table follows the same probe sequence that was followed
when inserting records. In this way, a record not in its home position can be recov-
ered. A Java implementation for the search procedure is shown in Figure 9.7.
The insert and search routines assume that at least one slot on the probe se-
quence of every key will be empty.
Otherwise, they will continue in an infinite
loop on unsuccessful searches.
Thus, the dictionary should keep a count of the
