Java Reference
In-Depth Information
numberOfEntries++
return null
}
else
{
Search the chain that begins at
hashTable[index]
for a node that contains
key
if
(
key
is found
)
{ //
assume
currentNode
references the node that contains
key
oldValue = currentNode.getValue()
currentNode.setValue(value)
return
oldValue
}
else
//
add new node to end of chain
{ //
assume
nodeBefore
references the last node
newNode =
new
Node(key, value)
nodeBefore.setNextNode(newNode)
numberOfEntries++
return null
}
}
Algorithm
remove(key)
index = getHashIndex(key)
Search the chain that begins at
hashTable[index]
for a node that contains
key
if
(
key
is found
)
{
Remove the node that contains
key
from the chain
numberOfEntries--
return
value in removed node
}
else
return null
Algorithm
getValue(key)
index = getHashIndex(key)
Search the chain that begins at
hashTable[index]
for a node that contains
key
if
(key
is found
)
return
value in found node
else
return null
All three operations search a chain of nodes. Each chain should contain only a few entries, if
the hash table is sufficiently large and the hash function distributes the entries uniformly through-
out the table. Thus, these operations should be time efficient. For a dictionary of
n
entries, the
operations certainly are faster than O(
n
). In the worst case, however, all entries are in one chain, so
the efficiency degenerates to O(
n
). We will discuss the efficiency of hashing in more detail in the
next chapter.
Note:
Separate chaining
provides an efficient and simple way to resolve collisions.
Because the structure of the hash table is altered, however, separate chaining requires more
memory than open addressing.
