Java Reference
In-Depth Information
The following pseudocode summarizes the logic of
probe
:
Algorithm
probe(index, key)
//
Searches the probe sequence that begins at
index
. Returns either the index of the entry
//
containing
key
or the index of an available location in the hash table.
while
(key
is not found and
hashTable[index]
is not
null)
{
if
(hashTable[index]
references an entry in the dictionary
)
{
if
(
the entry in
hashTable[index]
contains
key)
Exit loop
else
index
=
next probe index
}
else
// hashTable[index]
references a removed entry
{
if
(
this is the first removed entry encountered
)
removedStateIndex = index
index
=
next probe index
}
}
if
(key
is found or a removed entry was not encountered
)
return
index
else
return
removedStateIndex
//
index of first entry removed
The following method implements this algorithm:
private int
probe(
int
index, K key)
{
boolean
found =
false
;
int
removedStateIndex = -1;
// index of first location in
// removed state
while
( !found && (hashTable[index] !=
null
) )
{
if
(hashTable[index].isIn())
{
if
(key.equals(hashTable[index].getKey()))
found =
true
;
// key found
else
// follow probe sequence
index = (index + 1) % hashTable.length;
// linear probing
}
else
// skip entries that were removed
{
// save index of first location in removed state
if
(removedStateIndex == -1)
removedStateIndex = index;
index = (index + 1) % hashTable.length;
// linear probing
}
// end if
}
// end while
// Assertion: either key or null is found at hashTable[index]
if
(found || (removedStateIndex == -1) )
return
index;
// index of either key or null
else
return
removedStateIndex;
// index of an available location
}
// end probe
