Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Inserting and Removing Items

Program gif gives the code for inserting and removing items from a ChainedHashTable.

   program11306
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 tex2html_wrap_inline61985, where tex2html_wrap_inline61987 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 gif 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 tex2html_wrap_inline61997.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.