Java Reference
In-Depth Information
FIGURE 21-10
Where to insert a new entry into a linked bucket when the
integer search keys are (a) unsorted and possibly duplicate;
(b) unsorted and distinct; (c) sorted and distinct
(a)
When duplicate search keys are allowed,
add an entry to the beginning of an unsorted chain
20
45
20
31
Hash table
(b)
When search keys are distinct,
add an entry to the end of an unsorted chain
37
31
45
20
Hash table
(c)
When search keys are distinct,
add an entry in sorted order to
a sorted chain
37
20
31
45
Hash table
21.25
With distinct search keys and unsorted chains, the algorithms for the dictionary's
add
,
remove
, and
getValue
methods are as follows:
Algorithm
add(key, value)
index = getHashIndex(key)
if
(hashTable[index] ==
null
)
{
hashTable[index] =
new
Node(key, value)
