Average Case Analysis

The previous section has shown that in the worst case, the running time to insert an object into a separately chained hash table is O(1), and the time to find or delete an object is O(n). But these bounds are no better than the same operations on plain lists! Why have we gone to all the trouble inventing hash tables?

The answer lies not in the worst-case performance, but in the average expected performance. Suppose we have a hash table of size M. Let there be exactly n items in the hash table. We call the quantity the load factor   . The load factor is simply the ratio of the number of items in the hash table to the array length.

Let be the number of items in the linked list, for . The average length of a linked list is

The average length of a linked list is exactly the load factor!

If we are given the load factor , we can determine the average running times for the various operations. The average running time of Insert is the same as its worst case time, O(1)--this result does not depend on . On the other hand, the average running time for Withdraw does depend on . It is since the time required to delete an item from a linked list of length is .

To determine the average running time for the Find operation, we need to make an assumption about whether the item that is being sought is in the table. If the item is not found in the table, the search is said to be unsuccessful. The average running time for an unsuccessful search is

On the other hand, if the search target is in the table, the search is said to be successful. The average number of comparisons needed to find an arbitrary item in a linked list of length is

Thus, the average running time for a successful search is

So, while any one search operation can be as bad as O(n), if we do a large number of random searches, we expect that the average running time will be . In fact, if we have a sufficiently good hash function and a reasonable set of objects in the container, we can expect that those objects are distributed throughout the table. Therefore, any one search operation will not be very much worse than the worst case.

Finally, if we know how many objects will be inserted into the hash table a priori, then we can choose a table size M which is larger than the maximum number of items expected. By doing this, we can ensure that . I.e., a linked list contains no more than one item on average. In this case, the average time for Withdraw is and for Find it is .

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