|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Program 
gives the code for
inserting and removing items from a ChainedHashTable.
Program: ChainedHashTable class Insert and Withdraw methods.
The implementations of the Insert
and Withdraw methods are remarkably simple.
For example,
the Insert method first calls the hash method H
to compute an array index which is used to select one of the linked lists.
The Append method provided by the LinkedList class
is used to add the object to the selected linked list.
The total running time for the Insert operation is 
,
where 
is the running time of the GetHashCode method.
Notice that if the hash method runs in constant time,
then so too does hash table insertion operation!
The Withdraw method is almost identical to the Insert method.
Instead of calling the Append,
it calls the linked list Extract method to remove the
specified object from the appropriate linked list.
The running time of Withdraw is determined by the time
of the Extract operation.
In Chapter this was shown to be O(n)
where n is the number of items in the linked list.
In the worst case, all of the items in the ChainedHashTable
have collided with each other and ended up in the same list.
That is, in the worst case if there are n items in the container,
all n of them are in a single linked list.
In this case, the running time of the Withdraw operation
is 
.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.